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