【文章內(nèi)容簡(jiǎn)介】 op1。 Visit(pdata)。 /*訪問(wèn)根結(jié)點(diǎn) */ p=pRchild。 } /*遍歷右子樹(shù) */ } }while(p!=NULL||top!=0) } 中序遍歷二叉樹(shù)的非遞歸算法（調(diào)用棧操作的函數(shù)） void InOrder（ BiTree root） /* 中序遍歷二叉樹(shù)的非遞歸算法 */ { InitStack (amp。S)。 p=root。 while(p!=NULL || !IsEmpty(S)) { if (p!=NULL) /* 根指針進(jìn)棧 ， 遍歷左子樹(shù) */ { Push(amp。S,p)。 p=pLChild。 } else { /*根指針退棧 ， 訪問(wèn)根結(jié)點(diǎn) ， 遍歷右子樹(shù) */ Pop(amp。S,amp。p)。 Visit(pdata)。 p=pRChild。} } } 2) 后序遍歷的二叉樹(shù)的非遞歸算法 void PostOrder（ BiTree root） { BiTNode * p,*q； BiTNode **S； int top=0。 q=NULL。 p=root。 S=（ BiTNode**） malloc（ sizeof（ BiTNode*） *NUM） 。 /* NUM為預(yù)定義的常數(shù) */ while(p!=NULL || top!=0) { while(p!=NULL) { top++。 s[top]=p。 p=pLChild。 } /* 左子樹(shù)遍歷 */ if(top0) { p=s[top]。 if((pRChild==NULL) ||(pRChild==q)) /* 無(wú)右孩子 ， 或右孩子已遍歷過(guò) */ { visit(pdata)。 /* 訪問(wèn)根結(jié)點(diǎn) * / q=p。 /* 保存到 q， 為下一次已處理結(jié)點(diǎn)前驅(qū) */ top。 p=NULL。 // p=NULL防止再次遍歷左子樹(shù) } else //右孩子不為空且每訪問(wèn)過(guò) p=pRChild。 } } free(s)。 } 遍歷算法應(yīng)用 二叉樹(shù)的遍歷運(yùn)算是一個(gè)重要的基礎(chǔ)。在實(shí)際應(yīng)用中，一是重點(diǎn)理解訪問(wèn)根結(jié)點(diǎn)操作的含義，二是注意對(duì)具體的實(shí)現(xiàn)問(wèn)題是否需要考慮遍歷的次序問(wèn)題。 1. 輸出二叉樹(shù)中的結(jié)點(diǎn) 遍歷算法將走遍二叉樹(shù)中的每一個(gè)結(jié)點(diǎn)，故輸出二叉樹(shù)中結(jié)點(diǎn)并無(wú)次序要求，因此可用任一種算法來(lái)完成。 先序遍歷輸出二叉樹(shù)中的結(jié)點(diǎn) void PreOrder(BiTree root) /* 先序遍歷輸出二叉樹(shù)結(jié)點(diǎn) , root為指向二叉樹(shù)根結(jié)點(diǎn)的指針 */ { if (root!=NULL) { printf (root data)。 /* 輸出根結(jié)點(diǎn) */ PreOrder(root LChild)。 /* 先序遍歷左子樹(shù) */ PreOrder(root RChild)。 /* 先序遍歷右子樹(shù) */ } } 問(wèn)題思考： 若要求統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)應(yīng)如何去實(shí)現(xiàn)？ 2. 輸出二叉樹(shù)中的葉子結(jié)點(diǎn) 條件：判斷結(jié)點(diǎn)既沒(méi)有左孩子，又沒(méi)有右孩子時(shí)，則輸出該結(jié)點(diǎn)。 void PreOrder(BiTree root) /* 先序遍歷輸出二叉樹(shù)中葉結(jié)點(diǎn) , root為指向二叉樹(shù)根結(jié)點(diǎn)的指針 */ { if (root!=NULL) { if (root LChild==NULL amp。amp。 root RChild==NULL) printf (root data)。 /* 輸出葉結(jié)點(diǎn) */ PreOrder(root LChild)。 /* 先序遍歷左子樹(shù) */ PreOrder(root RChild)。 /* 先序遍歷右子樹(shù) */ } } 3. 統(tǒng)計(jì)葉子結(jié)點(diǎn)數(shù)目 /* LeafCount保存葉子結(jié)點(diǎn)數(shù)目的全局變量 ,調(diào)用之前初始化值為 0 */ void leaf(BiTree root) { if(root!=NULL) { if (root LChild==NULL amp。amp。 root RChild==NULL) LeafCount++。 leaf(rootLChild)。 leaf(rootRChild)。 } } 方法一： 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ù)的葉子數(shù)目之和 */ return LeafCount。 } 方法二 /* 采用遞歸算法，如果是空樹(shù)，返回 0；如果只有一個(gè)結(jié)點(diǎn)， 返回 1；否則為左右子樹(shù)的葉子結(jié)點(diǎn)數(shù)之和 */ 4. 建立二叉鏈表方式存儲(chǔ)的二叉樹(shù) 給定一棵二叉樹(shù)，可以得到它的遍歷序列；反過(guò)來(lái)，給定一個(gè)遍歷序列，也可以創(chuàng)建相應(yīng)的二叉鏈表。在這里所說(shuō)的遍歷序列是一種“擴(kuò)展的遍歷序列”，通常用特定的元素表示空子樹(shù)。例如： A B C D F G E H 右圖中的二叉樹(shù)的“擴(kuò)展的先序遍歷序列”為： ..G.... 其中用小圓點(diǎn)表示空子樹(shù) 利用“擴(kuò)展先序遍歷序列”創(chuàng)建二叉鏈表的算法為： void CreateBiTree(BiTree *bt) //注意此處的指向結(jié)點(diǎn)的指針的指針 { char ch。 //傳遞指針的地址 ， 否則結(jié)點(diǎn)之間無(wú) ch=getchar()。 //法進(jìn)行連接 。 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è)函數(shù)表示二叉樹(shù) bt的高度，則遞歸定義如下 : 若 bt為空，則高度為 0 若 bt非空，其高度應(yīng)為其左右子樹(shù)高度的最大值加 1 左 子 樹(shù) 右 子 樹(shù) bt hl hr High=max(hl+hr)+1 后序遍歷求二叉樹(shù)的高度遞歸算法： int PostTreeDepth(BiTree bt) /* 后序遍歷求二叉樹(shù)的高度遞歸算法 */ { int hl,hr,max。 if(bt!=NULL) { hl=PostTreeDepth(btLChild)。 /* 求左子樹(shù)的深度 */ hr=PostTreeDepth(btRChild)。 /* 求右子樹(shù)的深度 */ max=hlhr?hl:hr。 /* 得到左 、 右子樹(shù)深度較大者 */ return(max+1)。 /* 返回樹(shù)的深度 */ } else return(0)。 /* 如果是空樹(shù) ， 則返回 0 */ } 線索二叉樹(shù) 1. 基本概念 二叉樹(shù)的遍歷運(yùn)算是將二叉樹(shù)中結(jié)點(diǎn)按一定規(guī)律 線性化 的過(guò)程。當(dāng)以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí)，只能找到結(jié)點(diǎn)的左、右孩子信息，而不能直接得到結(jié)點(diǎn)在遍歷序列中的前驅(qū)和后繼信息。要得到這些信息，第一種方法是將二叉樹(shù)遍歷一遍，在遍歷過(guò)程中便可得到結(jié)點(diǎn)的前驅(qū)和后繼，但這種動(dòng)態(tài)訪問(wèn)浪費(fèi)時(shí)間；第二種方法是充分利用二叉鏈表中的空鏈域，將遍歷過(guò)程中結(jié)點(diǎn)的前驅(qū)、后繼信息保存下來(lái)。 在有 n個(gè)結(jié)點(diǎn)的二叉鏈表中共有 2n個(gè)鏈域，但只有 n1個(gè)有用非空鏈域，其余 n+1個(gè)鏈域是空的。我們可以利用剩下的 n+1個(gè)空鏈域來(lái)存放遍歷過(guò)程中結(jié)點(diǎn)的前驅(qū)和后繼信息。 現(xiàn)作如下規(guī)定： 若結(jié)點(diǎn)有左子樹(shù)，則其 LChild域指向其左孩子，否則 LChild域指向其前驅(qū)結(jié)點(diǎn)；若結(jié)點(diǎn)有右子樹(shù)，則