6.3遍歷二叉樹和線索二叉樹一、遍歷二叉樹（TraversingBinaryTree）遍歷定義——指按某條搜索路線遍訪每個結(jié)點且不重復（又稱周游）。遍歷用途——它是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運算的前提，是二叉樹一切運算的基礎和核心。

遍歷方法——牢記一種約定，對每個結(jié)點的查看都是“先左后右”。1遍歷規(guī)則———二叉樹由根、左子樹、右子樹構(gòu)成，定義為D、

L、RD、L、R的組合定義了六種可能的遍歷方案：LDR,LRD,DLR,DRL,RDL,RLD若限定先左后右，則有三種實現(xiàn)方案：

DLRLDRLRD先(根)序遍歷中(根)序遍歷后(根)序遍歷

注：“先、中、后”的意思是指訪問的結(jié)點D是先于子樹出現(xiàn)還是后于子樹出現(xiàn)。2例1：先序遍歷的結(jié)果是：中序遍歷的結(jié)果是：后序遍歷的結(jié)果是：ABCDEABDECDBEACDEBCA口訣：DLR—先序遍歷，即先根再左再右LDR—中序遍歷，即先左再根再右LRD—后序遍歷，即先左再右再根3遍歷的算法實現(xiàn)：用遞歸形式格外簡單！回憶1：二叉樹結(jié)點的數(shù)據(jù)類型定義：typedefstructnode*tree_pointer;typedefstructnode{intdata;tree_pointerleft_child,right_child;}node;則三種遍歷算法可寫出:回憶2：第1章自測卷4.2題：longintfact(n)//求n!intn;{longf;if(n>1)f=n*fact(n-1);elsef=1;return(f);}5先序遍歷算法DLR(liuyu*root){if(root!=NULL)//非空二叉樹

{printf(“%d”,root->data);//訪問DDLR(root->lchild);//遞歸遍歷左子樹DLR(root->rchild);//遞歸遍歷右子樹}return(0);}中序遍歷算法LDR(x*root){if(root!=NULL){LDR(root->lchild);printf(“%d”,root->data);

LDR(root->rchild);}return(0);}后序遍歷算法LRD(x*root){if(root!=NULL)

{LRD(root->lchild);LRD(root->rchild);printf(“%d”,root->data);}return(0);}結(jié)點數(shù)據(jù)類型自定義typedefstructliuyu{intdata;structliuyu*lchild,*rchild；}liuyu;liuyu*root;

6對遍歷的分析：1.從前面的三種遍歷算法可以知道：如果將print語句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍歷算法的訪問路徑是相同的，只是訪問結(jié)點的時機不同。從虛線的出發(fā)點到終點的路徑上，每個結(jié)點經(jīng)過3次。AFEDCBG第1次經(jīng)過時訪問＝先序遍歷第2次經(jīng)過時訪問＝中序遍歷第3次經(jīng)過時訪問＝后序遍歷2.二叉樹遍歷的時間效率和空間效率時間效率:O(n)

//每個結(jié)點只訪問一次空間效率:O(n)

//棧占用的最大輔助空間（精確值：樹深為k的遞歸遍歷需要k+1個輔助單元?。?例：【嚴題集6.42③】編寫遞歸算法，計算二叉樹中葉子結(jié)點的數(shù)目。

思路：輸出葉子結(jié)點比較簡單，用任何一種遍歷算法，凡是左右指針均空者，則為葉子，將其統(tǒng)計并打印出來。DLR(liuyu*root)//采用中序遍歷的遞歸算法{if(root!=NULL)//非空二叉樹條件，還可寫成if(root){if(!root->lchild&&!root->rchild)//是葉子結(jié)點則統(tǒng)計并打印{sum++;printf("%d\n",root->data);}

DLR(root->lchild);//遞歸遍歷左子樹，直到葉子處；

DLR(root->rchild);}//遞歸遍歷右子樹，直到葉子處；}return(0);}8習題討論：1.求二叉樹深度，或從x結(jié)點開始的子樹深度。

算法思路：只查各結(jié)點后繼鏈表指針，若左(右)孩子的左(右)指針非空，則層次數(shù)加1；否則函數(shù)返回。技巧：遞歸時應當從葉子開始向上計數(shù)，層深者保留。否則不易確定層數(shù)。2.按層次輸出二叉樹中所有結(jié)點。

算法思路：既然要求從上到下，從左到右，則利用隊列存放各子樹結(jié)點的指針是個好辦法，而不必拘泥于遞歸算法。技巧：當根結(jié)點入隊后，令其左、右孩子結(jié)點入隊，而左孩子出隊時又令它的左右孩子結(jié)點入隊，……由此便可產(chǎn)生按層次輸出的效果。ABCDE10特別討論：若已知先序/后序遍歷結(jié)果和中序遍歷結(jié)果，能否“恢復”出二叉樹？【嚴題集6.31④】

證明：由一棵二叉樹的先序序列和中序序列可唯一確定這棵二叉樹。

例：已知一棵二叉樹的中序序列和后序序列分別是BDCEAFHG和DECBHGFA，請畫出這棵二叉樹。分析：①由后序遍歷特征，根結(jié)點必在后序序列尾部（即A）；②由中序遍歷特征，根結(jié)點必在其中間，而且其左部必全部是左子樹子孫（即BDCE），其右部必全部是右子樹子孫（即FHG）；③繼而，根據(jù)后序中的DECB子樹可確定B為A的左孩子，根據(jù)HGF子串可確定F為A的右孩子；以此類推。12問：用二叉鏈表法（l_child,r_child）存儲包含n個結(jié)點的二叉樹，結(jié)點的指針區(qū)域中會有多少個空指針？分析：用二叉鏈表存儲包含n個結(jié)點的二叉樹，結(jié)點必有2n個鏈域（見二叉鏈表數(shù)據(jù)類型說明）。 除根結(jié)點外，二叉樹中每一個結(jié)點有且僅有一個雙親（直接前驅(qū)），所以只會有n－1個結(jié)點的鏈域存放指針，指向非空子女結(jié)點（即直接后繼）。思考：二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放有用的信息或線索？——我們可以用它來存放當前結(jié)點的直接前驅(qū)和后繼等線索，以加快查找速度。所以，空指針數(shù)目＝2n－(n-1)=n+1個。n+114二、線索二叉樹（ThreadedBinaryTree）普通二叉樹只能找到結(jié)點的左右孩子信息，而該結(jié)點的直接前驅(qū)和直接后繼只能在遍歷過程中獲得。若將遍歷后對應的有關前驅(qū)和后繼預存起來，則從第一個結(jié)點開始就能很快“順藤摸瓜”而遍歷整個樹了。兩種解決方法增加兩個域：fwd和bwd；利用空鏈域（n+1個空鏈域）存放前驅(qū)指針存放后繼指針如何預存這類信息？例如中序遍歷結(jié)果：BDCEAFHG，實際上已將二叉樹轉(zhuǎn)為線性排列，顯然具有唯一前驅(qū)和唯一后繼！可能是根、或最左（右）葉子15規(guī)定：1）若結(jié)點有左子樹，則lchild指向其左孩子；否則，lchild指向其直接前驅(qū)(即線索)；2）若結(jié)點有右子樹，則rchild指向其右孩子；否則，rchild指向其直接后繼(即線索)。為了避免混淆，增加兩個標志域，如下圖所示：lchildLTagdataRTagrchild約定:當Tag域為0時,表示正常情況;當Tag域為1時,表示線索情況.16有關線索二叉樹的幾個術語：線索鏈表：用前頁結(jié)點結(jié)構(gòu)所構(gòu)成的二叉鏈表線索：指向結(jié)點前驅(qū)和后繼的指針線索二叉樹：加上線索的二叉樹（圖形式樣）線索化：對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程注：在線索化二叉樹中，并不是每個結(jié)點都能直接找到其后繼的，當標志為0時，則需要通過一定運算才能找到它的后繼。17dataAGEIDJHCFBltag0011110101rtag0001010111AGEIDJHCFB例1：帶了兩個標志的某先序遍歷結(jié)果如表所示，請畫出對應二叉樹。18對應的中序線索二叉樹存儲結(jié)構(gòu)如圖所示：00A00C00B11E11F11G00D11I11H注：此圖中序遍歷結(jié)果為:H,D,I,B,E,A,F,C,G0--root0204.【2000年計算機系考研題】給定如圖所示二叉樹T，請畫出與其對應的中序線索二叉樹。

2825405560330854解:因為中序遍歷序列是：5540256028083354對應線索樹應當按此規(guī)律連線，即在原二叉樹中添加虛線。NILNIL21voiditer_inorder(tree_pointernode){inttop=-1;/*initializestack*/tree_pointerstack[MAX_STACK_SIZE];for(;;){for(;node;node=node->left_child)add(&top,node);/*addtostack*/node=delete(&top);/*deletefromstack*/if(!node)break;/*emptystack*/printf(“%D”,node->data);node=node->right_child;}}時間復雜度O(n)附：中序遍歷迭代算法(利用堆棧)23voidlevel_order(tree_pointerptr)/*lev