【正文】 二叉樹的最大結(jié)點數(shù) typedef TElemType SqBiTree[MAX_ TREE_SIZE]。 // 0號單元存儲根結(jié)點 SqBiTree bt。 一、 二叉樹的順序存儲表示 例如 : A B C D E F A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 13 1 4 0 13 2 6 二、二叉樹的鏈?zhǔn)酱鎯Ρ硎? 1. 二叉鏈表 2． 三叉鏈表 A D E B C F ? ? ? ? ? ? ? root lchild data rchild 結(jié)點結(jié)構(gòu) : 1. 二叉鏈表 typedef struct BiTNode { // 結(jié)點結(jié)構(gòu) TElemType data。 struct BiTNode *lchild, *rchild。 // 左右孩子指針 } BiTNode, *BiTree。 lchild data rchild 結(jié)點結(jié)構(gòu) : C 語言的類型描述如下 : A D E B C F ? ? ? ? ? ? ? root ? 2． 三叉鏈表 parent lchild data rchild 結(jié)點結(jié)構(gòu) : typedef struct TriTNode { // 結(jié)點結(jié)構(gòu) TElemType data。 struct TriTNode *lchild, *rchild。 // 左右孩子指針 struct TriTNode *parent。 //雙親指針 } TriTNode, *TriTree。 parent lchild data rchild 結(jié)點結(jié)構(gòu) : C 語言的類型描述如下 : 二叉樹的遍歷 一、問題的提出 三、先左后右的遍歷算法 四、中序遍歷算法的非遞歸描述 五 、 遍歷算法的應(yīng)用舉例 二、按層次遍歷二叉樹 順著某一條搜索路徑 巡訪 二叉樹 中的結(jié)點，使得每個結(jié)點 均被訪問一 次 ，而且 僅被訪問一次 。 一、問題的提出 “訪問 ”的含義可以很廣，如：輸出結(jié) 點的信息等。 “遍歷 ”是任何類型均有的操作， 對線性結(jié)構(gòu)而言，只有一條搜索路 徑 (因為每個結(jié)點均只有一個后繼 )， 故不需要另加討論。而二叉樹是非 線性結(jié)構(gòu)， 每個結(jié)點有兩個后繼 ， 則 存在如何遍歷 即按什么樣的 搜索 路徑 遍歷的問題。 對 “ 二叉樹 ” 而言 ， 可以有三條搜索路徑： ? 1． 先上后下 的按層次遍歷； ? 2． 先左 （ 子樹 ） 后右 （ 子樹 ）的遍歷； ? 3． 先右 （ 子樹 ） 后左 （ 子樹 ）的遍歷 。 二、按層次遍歷二叉樹 實現(xiàn)方法為從上層到下層，每層中從左側(cè)到右側(cè)依次訪問每個結(jié)點。下面我們將給出一棵二叉樹及其按層次順序訪問其中每個結(jié)點的遍歷序列。 按層次遍歷該二叉樹的序列為： A B E C F D G H K A B C D E F G H K 三、先左后右的遍歷算法 先 （根）序的遍歷算法 中 （根）序的遍歷算法 后 （根）序的遍歷算法 若二叉樹為空樹，則空操作；否則， （ 1）訪問根結(jié)點； （ 2）先序遍歷左子樹； （ 3）先序遍歷右子樹。 先（根）序的遍歷算法： 四、算法的遞歸描述 void Preorder (BiTree T, void( *visit)(TElemTypeamp。 e)) { // 先序遍歷二叉樹 if (T) { visit(Tdata)。 // 訪問結(jié)點 Preorder(Tlchild, visit)。 // 遍歷左子樹 Preorder(Trchild, visit)。// 遍歷右子樹 } } A B C D E F G D L R T D L R D L R A B E D L R D L R DLR DLR C F D G 中序遍歷結(jié)果 : A B C D E F G T 若二叉樹為空樹，則空操作；否則， （ 1）中序遍歷左子樹； （ 2）訪問根結(jié)點； （ 3）中序遍歷右子樹。 中（根）序的遍歷算法： void Inorder (BiTree T, void( *visit)(TElemTypeamp。 e)) { // 中序遍歷二叉樹 if (T) { Inreorder(Tlchild, visit)。 // 遍歷左子樹 visit(Tdata)。 // 訪問結(jié)點 Inreorder(Trchild, visit)。// 遍歷右子樹 } } A B C D E F G L D R T L D R L D R A B E L D R L D R LDR LDR C F D G 中序遍歷結(jié)果 : B D C A G F E T 若二叉樹為空樹，則空操作；否則， （ 1）后序遍歷左子樹； （ 2）后序遍歷右子樹； （ 3）訪問根結(jié)點。 后（根）序的遍歷算法： void Postorder (BiTree T, void( *visit)(TElemTypeamp。 e)) { // 后序遍歷二叉樹 if (T) { Postreorder(Tlchild, visit)。 // 遍歷左子樹 Postreorder(Trchild, visit)。// 遍歷右子樹 visit(Tdata)。 // 訪問結(jié)點 } } A B C D E F G H K 例如 : 先序 序列 : A B C D E F G H K 中序 序列 : B D C A H G K F E 后序 序列 : D C B H K G F E A 五、中序遍歷算法的非遞歸描述 中序遍歷示意圖 算法一： Status InorderTraverse(Bitree T, Status(*Visit)(TElemType e)) { InitStack(S)。 Push(S,T)。 while(!StackEmpty(S)) { while(GetTop(S,p) amp。amp。 p) Push(S,plchild)。 Pop(S,p)。 if (!StackEmpty(S)) { Pop(S,p)。 if(!Visit(pdata)) return ERROR。 Push(S,prchild)。 } } return OK。 } Status InorderTraverse(Bitree T, Status(*Visit)(TElemType e)) { InitStack(S)。 p=T。 while(p||!StackEmpty(S)){ if(p) {Push(S,p)。 p=plchild。} else { Pop(S,p)。 if(!Visit(pdata)) return ERROR。 p=prchild。 } } return OK。 } 算法二： 六 、 遍歷算法的應(yīng)用舉例 統(tǒng)計二叉樹中葉子結(jié)點的個數(shù) (先序遍歷 ) 求二叉樹的深度 (后序遍歷 ) 輸入結(jié)點值，構(gòu)造二叉樹 (先序遍歷 ） 輸入結(jié)點值，構(gòu)造二叉樹 算法基本思想 : 先序 (或中序或后序 )遍歷二叉樹， 讀入一個字符，若讀入字符為空，則二叉樹為空 ,若讀入字符非空，則生成一個結(jié)點。將算法中“ 訪問結(jié)點 ”的操作改為： 生成一個結(jié)點，輸入結(jié)點的值 。 Status CreateBiTree (BiTree amp。T){ scanf( amp。ch ) 。 if (ch＝＝’’ ) T=NULL。 else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode))) exit(OVERFLOW)。 Tdata=ch。 //生成根結(jié)點 CreateB