第5章二叉樹與樹ppt課件

1、kikkiiimM010122ADT BinTree isoperations BinTree createEmptyBinTree(void) 創(chuàng)建一棵空的二叉樹。創(chuàng)建一棵空的二叉樹。 BinTree consBinTree(BinTreeNode root, BinTree left, BinTree right) 返回一棵二叉樹，其根結點是返回一棵二叉樹，其根結點是root，左右二叉樹分別為，左右二叉樹分別為left和和right。 int isNull ( BinTree t ) 判斷二叉樹判斷二叉樹t是否為空。是否為空。 BinTreeNode root ( BinTree t )

2、返回二叉樹返回二叉樹t的根結點。若為空二叉樹，則返回一特殊值。的根結點。若為空二叉樹，則返回一特殊值。acbd先根次序周游： void preOrder( BinTree t) 中根次序周游： void inOrder(BinTree t) 后根次序周游： void postOrder(BinTree t) 注意是抽象算法，需要根據(jù)二叉樹的實現(xiàn)方式進行修改。在數(shù)組溢出時，通過程序擴充空間。struct BinTreeNode;/ 二叉樹中結點typedef struct BinTreeNode * PBinTreeNode; /結點的指針類型struct BinTreeNode DataTyp

3、e info;/ 數(shù)據(jù)域 PBinTreeNode llink;/ 指向左子結點 PBinTreeNode rlink;/ 指向右子結點 ; 由于遞歸是二叉樹的固有特性，二叉樹的許多處理都可以用遞歸算法來描述，因而，為了運算和參數(shù)傳遞的方便，不再對二叉樹進行封裝，直接將二叉樹定義為指向結點的指針類型：typedef struct BinTreeNode *BinTree;在實際應用中，將二叉樹作為參數(shù)傳遞時，可能需要傳遞二叉樹根結點指針的地址避免被調用函數(shù)中修改根節(jié)點位置）。因而，為了說明方便，可以引入二叉樹類型的指針類型：typedef BinTree *PBinTree;為區(qū)分左右指針和線

4、索，需要在每個結點里增加兩個標志位ltag和rtag，令：ltag=0，則llink是指針，指向結點的左子結點；ltag =1，則llink是線索，指向結點的對稱序的前驅結點；rtag=0，則rlink是指針，指向結點的右子結點；rtag =1，則rlink是線索，指向結點的對稱序的后繼結點。struct ThrTreeNode;/ 線索二叉樹中的結點 */typedef struct ThrTreeNode * PThrTreeNode; / 指向線索二叉樹結點的指針類型struct ThrTreeNode/ 線索二叉樹中結點的定義 DataType info;PThrTreeNode ll

5、ink, rlink;int ltag, rtag;typedef struct ThrTreeNode * ThrTree; / 線索二叉樹類型的定義typedef ThrTree * PThrTree; / 線索二叉樹類型的指針類型根堆。本節(jié)主要討論小根堆。根堆。本節(jié)主要討論小根堆。2212) 1 (iiiikkkk2212)2(iiiikkkk 2 3 5 9 10 7 8 14 12 11 16 n刪除S中的最小元素。nend ADT PriorityQueue 2 3 9 10 5 8 14 12 11 16 7 4 3 4 9 10 5 8 14 12 11 16 7 nstruc

6、t HtNode *ht; /存放2*m-1個結點的數(shù)組n;ntypedef struct HtTree *PHtTree; / /哈夫曼樹類型的指針類型ADT Tree isoperations Tree createEmptyTree (void) 創(chuàng)建一棵空樹。創(chuàng)建一棵空樹。 Tree consTree(Node p ,Tree t1, Tree ti) 以以P為根，為根，t1 ti 為子樹為子樹 創(chuàng)建一棵樹。創(chuàng)建一棵樹。 int isNull ( Tree t ) 判斷樹判斷樹t是否為空樹。是否為空樹。 Node root ( Tree t ) 返回樹返回樹t的根結點。若為空樹，則返回

7、一特殊值。的根結點。若為空樹，則返回一特殊值。 Node parent (Node p ) 返回結點返回結點p的父結點。當指定的結點為根時，它沒有父結點，返回一個特殊值。的父結點。當指定的結點為根時，它沒有父結點，返回一個特殊值。 Tree leftChild (Tree t ) 返回樹返回樹t的長子樹。當指定樹沒有子樹時，返回一特殊值。的長子樹。當指定樹沒有子樹時，返回一特殊值。 Tree rightSibling (Tree t ) 返回樹返回樹t的右兄弟樹。當指定樹沒有右兄弟子樹時，返回一特殊值。的右兄弟樹。當指定樹沒有右兄弟子樹時，返回一特殊值。end ADT Treen程序實現(xiàn)遞程序

8、實現(xiàn)遞歸）：歸）：void postOrder( Tree t )n程序實現(xiàn)非遞歸）：void levelOrder(Tree t)ntypedef struct ParTree * PParTree; /樹類型的指針類型struct EdgeNode /子表中結點的結構 int nodeposition; /子結點在結點表中的位置 struct EdgeNode *link; / 指向下一個子表中的結點; struct ChiTreeNode /結點表中結點的結構 DataType info; / 結點本身的信息 struct EdgeNode *children; / 本結點子表的頭指針 ； struct ChiTree / 樹結構 int MAXNUM / 樹中最大結點個數(shù) int root; / 根結點的下標 int n; / 實際結點個數(shù) struct ChiTreeNode * nodelist; /結點表 ;typedef struct C