【正文】 樹、森林的遍歷和二叉樹遍歷的對應(yīng)關(guān)系 ？ 先根遍歷 后根遍歷 樹 二叉樹 森林 先序遍歷 先序遍歷 中序遍歷 中序遍歷 A B C D E F G H I J K L M N O 先序遍歷： 后序遍歷： 層次遍歷： A B E F I G C D H J K L N O M E I F G B C J K N O L M H D A A B C D E F G H I J K L M N O ? 作業(yè)：寫出下面樹的先根、后根及按層次遍歷的遍歷序列。 中序遍歷 森林中 (除第一棵樹之外 )其 余樹構(gòu)成的森林。 若森林不空，則 中序遍歷 森林中第一棵樹的子樹森林 。 先序遍歷 森林中 (除第一棵樹之外 )其 余樹構(gòu)成的森林。 可以分解成三部分： 森林 若森林不空，則 訪問 森林中第一棵樹的根結(jié)點(diǎn) 。 若樹不空，則自上而下、自左至右訪問樹中每個(gè)結(jié)點(diǎn)。 一、樹的遍歷 二、森林的遍歷 三、樹的遍歷的應(yīng)用 樹和森林的遍歷 樹的遍歷 可有三條搜索路徑 : 按層次遍歷 : 先根 (次序 )遍歷 : 后根 (次序 )遍歷 : 若樹不空，則先訪問根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹。 作業(yè)： 。 T1 T11,T12,…,T 1m T2,…,T n LBT root 森林 二叉樹 RBT 由此，樹和森林的各種操作均可與二叉樹的操作相對應(yīng)。 否則， 由 root對應(yīng)得到 ROOT( T1 )。 由二叉樹轉(zhuǎn)換為森林 的轉(zhuǎn)換規(guī)則為 : 由 LB 對應(yīng)得到 ( t11, t12, … , t 1m)。 否則， 由 ( t11, t12, …, t 1m ) 對應(yīng)得到二叉樹的左子樹 LB。 ? 可以給上述轉(zhuǎn)換方法作如下形式定義： 由森林轉(zhuǎn)換成二叉樹 的 轉(zhuǎn)換規(guī)則為 : 若 F = Φ，則 B = Φ。 T1 = ( root， t11, t12, …, t 1m )。最后作適當(dāng)?shù)恼{(diào)整即可。 森林轉(zhuǎn)換成二叉樹的規(guī)則 H D G F C I E B J 如： J H D G F C I E B J H D G F I E B C H D G F C I E B J 以上我們給出了：樹和森林轉(zhuǎn)化為二叉樹的規(guī)則， 那么二叉樹如何轉(zhuǎn)化為樹或森林？看下面例子： 二叉樹轉(zhuǎn)換成樹或森林的規(guī)則 若結(jié)點(diǎn) x是其雙親 p的左孩子，則把 x的右孩子、右孩子的右孩子、 …… 都與 p用線連起來。 (因?yàn)闃涓鶝]有兄弟 ) (二 ) 森林與二叉樹之間的轉(zhuǎn)換 在把森林轉(zhuǎn)換為二叉樹時(shí)，可以把森林中除第一棵樹以外的其它所有樹的根結(jié)點(diǎn)看作第一棵樹根結(jié)點(diǎn)的 兄弟 結(jié)點(diǎn)。 A B C D E F G A B C E D F G root A B C E D F G root A B C D E F G root A B C D E F G 樹 二叉樹 孩子兄弟表示法 二叉鏈表表 示法 內(nèi)存中的表示 樹轉(zhuǎn)換成二叉樹的規(guī)則 要把一棵樹轉(zhuǎn)換為二叉樹，只要： 兄弟 之間加一條連線； ，除 保留 其與第一個(gè)孩子之間的 連線外， 去掉 該結(jié)點(diǎn)與其它孩子的連線； ，把右孩子順時(shí)針 旋轉(zhuǎn) 45度。這樣就可以得到二叉樹與樹之間的對應(yīng)關(guān)系。 練習(xí)： A B C E D F G I H 孩子 兄弟表示法 樹、森林和二叉樹的對應(yīng)關(guān)系 (一 ) 樹與二叉樹之間的轉(zhuǎn)換 二叉樹和樹都可以用二叉鏈表作為存儲結(jié)構(gòu)。 } CSNode, *CSTree。 樹結(jié)構(gòu) : typedef struct CSNode{ TElemType data。 int n, r。 // 孩子鏈的頭指針 } CTBox。 孩子結(jié)點(diǎn)結(jié)構(gòu) : child nextchild 孩子鏈表 C語言的類型描述 : typedef struct { TElemType data。 struct CTNode *nextchild。 Ⅳ. 為了方便各種操作，可以把雙親表示法和孩子表示法結(jié)合起來，即 帶雙親的孩子鏈表 。較實(shí)用的方法是 為樹中每個(gè)結(jié)點(diǎn)建立一個(gè)孩子鏈表 ，而 n個(gè)頭指針又組成一個(gè)線性表，為了便于查找，可采用順序存儲結(jié)構(gòu)。雖然節(jié)省了空間，但給運(yùn)算帶來了不便。 Ⅱ. 若每個(gè)結(jié)點(diǎn)按其實(shí)際的孩子數(shù)來設(shè)置指針域的個(gè)數(shù)，并在結(jié)點(diǎn)內(nèi)設(shè)置度數(shù)域“ degree”指出結(jié)點(diǎn)所包含的指針的數(shù)目。但由于樹中很多結(jié)點(diǎn)的度都小于 d，一棵度為 d且含有 n個(gè)結(jié)點(diǎn)的樹必有 ？ 個(gè)空指針域。 樹結(jié)構(gòu) : r=0 n=7 0 A 1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 A B C D E F G 二、孩子鏈表表示法 : 樹中每個(gè)結(jié)點(diǎn)可能包含多棵子樹， 所以可以采用 多叉鏈表 表示。 int r, n。 // 雙親位置域 } PTNode。 typedef struct PTNode { TElemType data。 樹和森林 樹的三種存儲結(jié)構(gòu) 樹、森林和二叉樹的對應(yīng)關(guān)系 樹和森林的遍歷 樹的三種存儲結(jié)構(gòu) 一、 雙親表示法 （順序存儲） 二、 孩子鏈表表示法 三、 孩子 兄弟表示法 (二叉鏈表存儲） A B C D E F G 0 A 1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 data parent 一、雙親表示法 : (順序存儲結(jié)構(gòu) ) 利用每個(gè)結(jié)點(diǎn)至多有一個(gè)雙親的性質(zhì)。 線索樹的優(yōu)缺點(diǎn)： 優(yōu)點(diǎn)： 線索樹由于含有其前驅(qū)、后繼的 信息，因此在進(jìn)行各種操作時(shí)顯 得比較方便。amp。 prchild=q。 qrchild=prchild。 qlchild=p。 算法片斷： s=InOrderNext(p)。 ！注意： 若 *p不是中序序列的最后一個(gè)結(jié)點(diǎn)，則其必有一個(gè)中序后繼結(jié)點(diǎn) *s，插入 *q后， *s將變成 *q的后繼結(jié)點(diǎn)。 P L R P L R Q p p q 空 P L R Q p q 空 插入 *q后， *q的左子樹為空，所以，它是 *p右子樹中最左下的結(jié)點(diǎn)。 // 右子樹線索化 } // if } // InThreading 練習(xí)：中序線索化二叉樹： c d e f + / a b 中序遍歷序列： a+b*cde/f nil nil 提高： 中序線索樹中插入結(jié)點(diǎn)。 } pre = p。 } if (!prerchild) // 建后繼線索 { preRTag = Thread。 // 左子樹線索化 if (!plchild) // 建前驅(qū)線索 { pLTag = Thread。把中序遞歸遍歷算法中的Visit(pdata)改為 設(shè)置線索 的語句。 // p進(jìn)至其右子樹根 } } // InOrderTraverse_Thr c d e f + / a b nil nil 中序遍歷序列： a+b*cde/f 思考： 在后序線索二叉樹中，如何找結(jié)點(diǎn) *x 的后繼結(jié)點(diǎn)？ 分三種情況： *x是根結(jié)點(diǎn) ，則其 后繼 為空； *x是其雙親的右孩子 或 *x是其雙親的左孩子但其雙親無右子樹， 則 后繼 為其雙親結(jié)點(diǎn)； *x是其雙親的左孩子且其雙親有右子樹， 則 后繼 為： 其雙親結(jié)點(diǎn)的右子樹 ” 后序序列 ” 中的第一個(gè)結(jié)點(diǎn)； 如： A B H F C G E D 后序線索化 1. A空 2. G E E B F C 3. B H 后序序列： DGEBHFCA 進(jìn)行后序后繼線索化 在中序遍歷過程中修改結(jié)點(diǎn)的左、右指針域，以保存當(dāng)前訪問結(jié)點(diǎn)的“ 前驅(qū) ”和“ 后繼 ”信息。 Visit(pdata)。amp。 //最左下的結(jié)點(diǎn)是中序遍歷的 Visit(pdata)。 } while (p!=T) } } 有右子樹 無右子樹 對新子樹 void InOrderTraverse_Thr(BiThrTree T, //中序遍歷帶頭結(jié)點(diǎn)二叉線索樹 T的非遞歸算法 void (*Visit)(TElemType e)) { //T指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的左鏈 lchild指向根結(jié)點(diǎn) p = Tlchild。 do{ Visit (pdata)。 最左下結(jié)點(diǎn)時(shí)，繼續(xù)查找 } //else } void InOrderTraverse (BiThrTree T, void (*Visit)(TElemType e)) { //基于 next(p)函數(shù)的中序遍歷二叉線索樹 T的非遞歸算法 //T指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的左鏈 lchild指向根結(jié)點(diǎn) p = Tlchild。 //從 *p的右孩子開始查找 while (!qltag) q=qlchild。 作業(yè) ： 寫出中序線索二叉樹中找指針 p所指結(jié)點(diǎn)后繼的算法。 p。 若 *p無右子樹， 則為 *p后繼線索 所指結(jié)點(diǎn)， 否則為 對 *p右子樹 進(jìn)行 中序遍歷 時(shí)訪問的第一個(gè)結(jié)點(diǎn)。 例如 : 對中序線索化鏈表的遍歷算法。 p = Next(p) ) Visit (p)。 // Link==0:指針， Thread==1:線索 二、線索鏈表的遍歷算法 : for ( p = firstNode(T)。 // 左右標(biāo)志 } BiThrNode, *BiThrTree。 struct BiThrNode *lchild, *rchild。 如此定義的二叉樹的存儲結(jié)構(gòu)稱作“ 線索鏈表 ”。 與其相應(yīng)的二叉樹，稱作 “ 線索二叉樹 ” 包含 “線索” 的存儲結(jié)構(gòu)，稱作 “ 線索鏈表 ” A B C D E F G H K （先序序列） ^ D ^ C ^ ^ B E ^ A B C D E