【文章內容簡介】 Node**） malloc（ sizeof（ BiTNode*） *NUM） 。 /* NUM為預定義的常數(shù) */ while(p!=NULL || top!=0) { while(p!=NULL) { top=++。 s[top]=p。 p=pLChild。 } /* 左子樹遍歷 */ if(top0) { p=s[top]。 if((pRChild==NULL) ||(pRChild==q)) /* 無右孩子 ， 或右孩子已遍歷過 */ { visit(pdata)。 /* 訪問根結點 * / q=p。 /* 保存到 q， 為下一次已處理結點前驅 */ top。 p=NULL。 } else p=pRChild。 } } free(s)。 } 遍歷算法應用 二叉樹的遍歷運算是一個重要的基礎。在實際應用中，一是重點理解訪問根結點操作的含義，二是注意對具體的實現(xiàn)問題是否需要考慮遍歷的次序問題。 1. 輸出二叉樹中的結點 遍歷算法將走遍二叉樹中的每一個結點，故輸出二叉樹中結點并無次序要求，因此可用任一種算法來完成。 先序遍歷輸出二叉樹中的結點 void PreOrder(BiTree root) /* 先序遍歷輸出二叉樹結點 , root為指向二叉樹根結點的指針 */ { if (root!=NULL) { printf (root data)。 /* 輸出根結點 */ PreOrder(root LChild)。 /* 先序遍歷左子樹 */ PreOrder(root RChild)。 /* 先序遍歷右子樹 */ } } 問題思考： 若要求統(tǒng)計二叉樹中結點個數(shù)應如何去實現(xiàn)？ 2. 輸出二叉樹中的葉子結點 條件：判斷結點既沒有左孩子，又沒有右孩子時，則輸出該結點。 void PreOrder(BiTree root) /* 先序遍歷輸出二叉樹中葉結點 , root為指向二叉樹根結點的指針 */ { if (root!=NULL) { if (root LChild==NULL amp。amp。 root RChild==NULL) printf (root data)。 /* 輸出葉結點 */ PreOrder(root LChild)。 /* 先序遍歷左子樹 */ PreOrder(root RChild)。 /* 先序遍歷右子樹 */ } } 3. 統(tǒng)計葉子結點數(shù)目 /* LeafCount保存葉子結點數(shù)目的全局變量 ,調用之前初始化值為 0 */ void leaf(BiTree root) { if(root!=NULL) { leaf(rootLChild)。 leaf(rootRChild)。 if (root LChild==NULL amp。amp。 root RChild==NULL) LeafCount++。 } } 方法一： int leaf(BiTree root) { int LeafCount。 if(root==NULL) LeafCount =0。 else if((rootLChild==NULL)amp。amp。(rootRChild==NULL)) LeafCount =1。 else LeafCount =leaf(rootLChild)+leaf(rootRChild)。 /* 葉子數(shù)為左右子樹的葉子數(shù)目之和 */ return LeafCount。 } 方法二 : /* 采用遞歸算法，如果是空樹，返回 0；如果只有一個結點， 返回 1；否則為左右子樹的葉子結點數(shù)之和 */ 4. 建立二叉鏈表方式存儲的二叉樹 給定一棵二叉樹，可以得到它的遍歷序列；反過來，給定一個遍歷序列，也可以創(chuàng)建相應的二叉鏈表。在這里所說的遍歷序列是一種“擴展的遍歷序列”，通常用特定的元素表示空子樹。例如： A B C D F G E H 右圖中的二叉樹的“擴展的遍歷序列”為： ..G.... 其中用小圓點表示空子樹 利用“擴展先序遍歷序列”創(chuàng)建二叉鏈表的算法為： void CreateBiTree(BiTree *bt) { char ch。 ch=getchar()。 if(ch==39。.39。) *bt=NULL。 else { *bt=(BiTree)malloc(sizeof(BiTNode))。 (*bt)data=ch。 CreateBiTree(amp。((*bt)LChild))。 CreateBiTree(amp。((*bt)RChild))。 } } 5. 求二叉樹的高度 設函數(shù)表示二叉樹 bt的高度，則遞歸定義如下 : 若 bt為空，則高度為 0 若 bt非空，其高度應為其左右子樹高度的最大值加 1 左 子 樹 右 子 樹 bt hl hr High=max(hl+hr)+1 后序遍歷求二叉樹的高度遞歸算法： int PostTreeDepth(BiTree bt) /* 后序遍歷求二叉樹的高度遞歸算法 */ { if(bt!=NULL) { hl=PostTreeDepth(btLChild)。 /* 求左子樹的深度 */ hr=PostTreeDepth(btRChild)。 /* 求右子樹的深度 */ max=hlhr?hl:hr。 /* 得到左 、 右子樹深度較大者 */ return(max+1)。 /* 返回樹的深度 */ } else return(0)。 /* 如果是空樹 ， 則返回 0 */ } 問題思考： 求二叉樹的深度是否可用先序遍歷的方式實現(xiàn)？若能，請寫出實現(xiàn)算法，若不能，請說明原因。 6. 按樹狀打印的二叉樹 假設以二叉鏈表存儲的二叉樹中，每個結點所含數(shù)據(jù)元素均為單字母，要求實現(xiàn)如下圖的打印結果。 A B C D E F 輸出 C F A E D B 分析：這是二叉樹的橫向顯示問題，橫向顯示應是豎向顯示的 900旋轉，又由于二叉樹的橫向顯示算法一定是中序遍歷算法，所以把橫向顯示的二叉樹算法改為 RDL結構，實現(xiàn)算法為： void PrintTree(TreeNode Root,int nLayer) /* 豎向樹狀打印的二叉樹 */ { if(Root= =NULL) return。 PrintTree(RootRChild,nLayer+1)。 for(int i=0。inLayer。i++) printf(“ ”)。 printf(“%c\n”,Rootch)。 PrintTree(RootLChild,nLayer+1)。 } 線索二叉樹 1. 基本概念 二叉樹的遍歷運算是將二叉樹中結點按一定規(guī)律 線性化 的過程。當以二叉鏈表作為存儲結構時，只能找到結點的左、右孩子信息，而不能直接得到結點在遍歷序列中的前驅和后繼信息。要得到這些信息，第一種方法是將二叉樹遍歷一遍，在遍歷過程中便可得到結點的前驅和后繼，但這種動態(tài)訪問浪費時間；第二種方法是充分利用二叉鏈表中的空鏈域，將遍歷過程中結點的前驅、后繼信息保存下來。 在有 n個結點的二叉鏈表中共有 2n個鏈域，但只有 n1個有用非空鏈域，其余 n+1個鏈域是空的。我們可以利用剩下的 n+1個空鏈域來存放遍歷過程中結點的前驅和后繼信息。 現(xiàn)作如下規(guī)定： 若結點有左子樹，則其 LChild域指向其左孩子，否則 LChild域指向其前驅結點；若結點有右子樹，則其 RChild域指向其右孩子，否則 RChild域指向其后繼結點。 LChild Ltag Data Rtag RChild 為了區(qū)分孩子結點和前驅、后繼結點，為結點結構增設兩個標志域，如下圖所示： 其中： Ltag= 0 LChild域指示結點的左孩子 1 LChild域指示結點的遍歷前驅 Rtag= 0 RChild域指示結點的右孩子 1 RChild域指示結點的遍歷后繼 線索： 在這種存儲結構中，指向前驅和后繼結點的指針叫做 線索 。 線索鏈表： 以這種結構組成的二叉鏈表作為二叉樹的存儲結構，叫做 線索鏈表 。 線索化： 對二叉樹以某種次序進行遍歷并且加上線索的過程叫做 線索化 。 線索二叉樹： 線索化了的二叉樹稱為 線索二叉樹 。 2.