【正文】 truct { datatype data； /*數(shù)據(jù)域 */ struct BTlink3 *lch， *parent， *rch； /*parent是雙親指針域 */ } Bnode3。 這就涉及到一個遍歷二叉樹的問題 。 所謂訪問結(jié)點 ， 就是指對結(jié)點進行各種操作 。 遍歷二叉樹的過程實質(zhì)是把二叉樹的結(jié)點進行線性排列的過程 。 但二叉樹是非線性結(jié)構(gòu) ， 遍歷時是先訪問根結(jié)點還是先訪問子樹 ， 是先訪問左子樹還是先訪問右子樹必須有所規(guī)定 ， 這就是遍歷規(guī)則 。 數(shù)據(jù)結(jié)構(gòu)（ C語言版） 由于一棵非空二叉樹是由根結(jié)點 、 左子樹和右子樹三個基本部分組成的 ， 遍歷二叉樹時只要按順序依次遍歷這三部分即可 。 先序遍歷的遞歸算法如下 : 數(shù)據(jù)結(jié)構(gòu)（ C語言版） /*算法描述 先序遍歷的遞歸算法 */ void preorder(BTlink * p) { if(p!=NULL) {printf(%c\n， pdata)； /*訪問根結(jié)點 */ preorder(plch)； /*按先根次序遍歷左子樹 */ preorder(prch)； /*按先根次序遍歷右子樹 */ } } /*preorder*/ 數(shù)據(jù)結(jié)構(gòu)（ C語言版） E FDCBACBA( a ) ( b)圖 遍歷序列示例 數(shù)據(jù)結(jié)構(gòu)（ C語言版） 中序遍歷 中序遍歷可以遞歸地描述如下： 如果二叉樹為空 ， 則空操作 ， 否則： ① 按中序次序遍歷左子樹 ， ② 訪問根結(jié)點 ， ③ 按中序次序遍歷右子樹 。 數(shù)據(jù)結(jié)構(gòu)（ C語言版） 后根遍歷 后根遍歷可以遞歸地描述如下： 如果二叉樹為空 ， 則空操作 ， 否則： ① 后序遍歷左子樹； ② 后序遍歷右子樹； ③ 訪問根結(jié)點 。 /*后序遍歷左子樹 */ postorder ( prch )。 /*訪問根結(jié)點 */ } } /*postorder*/ 例如，圖 (a)所示二叉樹的后序遍歷序列為 BCA, 圖 (b)所示二叉樹的后根遍歷序列為 CBEFDA。 T是指向根指針的指針，故修改 *T就修改了實參 (根指針 )本身 char ch； if((ch=getchar())==39。) T=NULL； //讀人空格，將相應(yīng)指針置空 else{ //讀人非空格 *T=(BinTNode *)malloc(sizeof(BinTNode))； //生成結(jié)點 (*T)data=ch； CreateBinTree(amp。(*T)rchild)； //構(gòu)造右子樹 } } 數(shù)據(jù)結(jié)構(gòu)（ C語言版） 線索二叉樹 線索二叉樹的基本概念 我們發(fā)現(xiàn) ， 具有 n個結(jié)點的二叉樹中有 n – 1條邊指向其左 、右孩子 ， 這意味著在二叉鏈表中的 2n個孩子指針域中只用到了 n –1 個域 ， 還有另外 n+1個指針域是空的 。 試作如下規(guī)定：若結(jié)點有左子樹，則其 lch域指示其左孩子，否則令 lch域指示其直接前驅(qū)；若結(jié)點有右子樹，則其 rch域指示其右孩子，否則令 rch域指示其直接后繼。新的結(jié)點結(jié)構(gòu)為： 數(shù)據(jù)結(jié)構(gòu)（ C語言版） lch ltag data rtag rch 其中： ltag=0 表示 lch指示結(jié)點的左孩子 ltag=1 表示 lch指示結(jié)點的直接前驅(qū) rtag=0 表示 rch指示結(jié)點的右孩子 rtag=1 表示 rch指示結(jié)點的直接后繼 算法描述為： struct xtreenode {char data。 int ltag,rtag。 對二叉樹以某種次序進行遍歷并且加上線索的過程稱做線索化 。 對一個已建好的二叉樹的二叉鏈表進行線索化時規(guī)定 (對 p結(jié)點 )： (1) ?p有左孩子時 ， 則令左特征域 pltag = 0。 (3) ?p有右孩子時 ， 令 prtag = 0。 數(shù)據(jù)結(jié)構(gòu)（ C語言版） 1 B 0 0 C 11 D 1ECDBA1 E 10 A 0( a ) ( b)圖 中根次序線索樹 (a) 二叉樹； (b) 中根次序線索樹 數(shù)據(jù)結(jié)構(gòu)（ C語言版） 線索二叉樹的邏輯表示圖 按照不同的次序進行線索化，可得到不同的線索二叉樹，即先根線索二叉樹、中根線索二叉樹和后根線索二叉樹。 數(shù)據(jù)結(jié)構(gòu)（ C語言版） F H IECGABD( c)N U L LF H IECGABD( d )N U L LF H ICGABD( b )EF H ICGABD E( a)圖 線索二叉樹的邏輯表示圖 (a) 二叉樹； (b) 先根線索二叉樹； (c) 中根線索二叉樹； (d) 后根線索二叉樹 數(shù)據(jù)結(jié)構(gòu)（ C語言版） 中根次序線索化算法 這里重點介紹中根次序線索化的算法 。 中根次序線索化遞歸算法如下： /*算法描述 中根次序線索化遞歸算法 */ void inthread(struct xtreenode *p) {if (p!=NULL) {inthread(plch)。 if(plch!=NULL)pltag=0。 plch=pr。 else{ prrtag=1。 } /*前驅(qū)結(jié)點 pr建右線索，指向結(jié)點 p*/ } pr=p。 ?} }/*inthread*/ 數(shù)據(jù)結(jié)構(gòu)（ C語言版） 此算法中 pr是全局變量 ， 在主程序中置初值為空 。 在線索化過程中 ， 邊判斷二叉樹的結(jié)點有無左 、 右孩子 ， 邊給相應(yīng)標(biāo)志域置 0或 1， 邊建立線索 。 在遞歸調(diào)用結(jié)束時 p為空 ， 這表明 pr已是最后一個結(jié)點 ， 應(yīng)該沒有后繼結(jié)點 。 主函數(shù)語句示意如下： 數(shù)據(jù)結(jié)構(gòu)（ C語言版） main() { pr=NULL。 /*建立二叉樹 */ inthread(t)。這樣每遞歸調(diào)用一次， pr就置一次空，無法記下 p的前驅(qū)結(jié)點。因此，在描述遞歸算法時，提倡同時寫出主函數(shù)來示意遞歸調(diào)用前的初始化處理和遞歸調(diào)用結(jié)束后的善后處理。當(dāng) qltag=0時，表明 q有左孩子。圖 (b)中，結(jié)點 D是 A的左子樹的最右尾結(jié)點，它就是 A的前驅(qū)結(jié)點。若用 p記錄 q的前趨，則算法如下： 數(shù)據(jù)結(jié)構(gòu)（ C語言版） /*算法描述 已知 q結(jié)點，找出它的前驅(qū)結(jié)點 */ struct xtreenode *inpre(struct xtreenode *q) { if(qltag==1) p=qlch。 while (rrtag!==1) r=rrch。 } return(p)。順序存儲結(jié)構(gòu)即向量，一般將樹結(jié)點按自上而下、自左至右的順序一一存放。對于一般樹結(jié)構(gòu)更適合使用鏈表存儲結(jié)構(gòu)。 數(shù)據(jù)結(jié)構(gòu)（ C語言版） 圖 ，可用三重鏈表來存儲，其結(jié)點結(jié)構(gòu)為：有一個數(shù)據(jù)域和三個指針域，指針域用于指向該結(jié)點的各個孩子。如果用孩子 － 兄弟鏈表作存儲結(jié)構(gòu)，其結(jié)點結(jié)構(gòu)為：有一個數(shù)據(jù)域和兩個指針域，一個指針指向它的長子，另一指針指向它的一個兄弟。 數(shù)據(jù)結(jié)構(gòu)（ C語言版） E FCBAG H ID圖 樹 數(shù)據(jù)結(jié)構(gòu)（ C語言版） G H ID E FB CA ABDCEGFH I( a ) ( b)圖 樹的存儲結(jié)構(gòu) (a) 多重鏈表； (b) 孩子 兄弟鏈表 數(shù)據(jù)結(jié)構(gòu)（ C語言版） 樹與二叉樹之間的轉(zhuǎn)換 對于一般樹，樹中孩子的次序并不重要，只要雙親與孩子的關(guān)系正確即可。所以在討論二叉樹與一般樹之間的轉(zhuǎn)換時，為了不引起混淆，就約定按樹上現(xiàn)有結(jié)點次序進行轉(zhuǎn)換。 可理解為每個結(jié)點的兄弟指針指向它的一個兄弟 。 可理解為每個結(jié)點僅有一個孩子指針 ， 讓它指向自己的長子 。 ，成右斜下方向。這樣就形成一棵二叉樹。在所生成的二叉樹中某一結(jié)點的左孩子仍是原來樹中該結(jié)點的長子，并且是它的最左孩子。 數(shù)據(jù)結(jié)構(gòu)（ C語言版） GHFCB D