數(shù)據(jù)結(jié)構(gòu)-樹(shù)PPT

1、引言引言:在前面幾章里討論的數(shù)據(jù)結(jié)構(gòu)都屬于線性結(jié)構(gòu)，線在前面幾章里討論的數(shù)據(jù)結(jié)構(gòu)都屬于線性結(jié)構(gòu)，線性結(jié)構(gòu)的特點(diǎn)是邏輯結(jié)構(gòu)簡(jiǎn)單，易于進(jìn)行查找、插性結(jié)構(gòu)的特點(diǎn)是邏輯結(jié)構(gòu)簡(jiǎn)單，易于進(jìn)行查找、插入和刪除等操作，主要用于對(duì)客觀世界中具有單一入和刪除等操作，主要用于對(duì)客觀世界中具有單一的前驅(qū)和后繼的數(shù)據(jù)關(guān)系進(jìn)行描述。而現(xiàn)實(shí)中的許的前驅(qū)和后繼的數(shù)據(jù)關(guān)系進(jìn)行描述。而現(xiàn)實(shí)中的許多事物的關(guān)系并非如此簡(jiǎn)單，如人類社會(huì)的族譜、多事物的關(guān)系并非如此簡(jiǎn)單，如人類社會(huì)的族譜、各種社會(huì)組織機(jī)構(gòu)以及城市交通、通訊等，這些事各種社會(huì)組織機(jī)構(gòu)以及城市交通、通訊等，這些事物中的聯(lián)系都是非線性的，采用非線性結(jié)構(gòu)進(jìn)行描物中的聯(lián)系都是非線

2、性的，采用非線性結(jié)構(gòu)進(jìn)行描繪會(huì)更明確和便利。繪會(huì)更明確和便利。:所謂非線性結(jié)構(gòu)，是指在該結(jié)構(gòu)中至少存在一個(gè)數(shù)所謂非線性結(jié)構(gòu)，是指在該結(jié)構(gòu)中至少存在一個(gè)數(shù)據(jù)元素，有兩個(gè)或兩個(gè)以上的直接前驅(qū)（或直接后據(jù)元素，有兩個(gè)或兩個(gè)以上的直接前驅(qū)（或直接后繼）元素。樹(shù)結(jié)構(gòu)和圖結(jié)構(gòu)是非常重要的非線性結(jié)繼）元素。樹(shù)結(jié)構(gòu)和圖結(jié)構(gòu)是非常重要的非線性結(jié)構(gòu)。構(gòu)。 第六章第六章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)F本章內(nèi)容本章內(nèi)容6.1 樹(shù)的定義和基本術(shù)語(yǔ)6.2 二叉樹(shù)6.2.1 二叉樹(shù)的定義及基本運(yùn)算6.2.2 二叉樹(shù)的性質(zhì)6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)6.3 遍歷二叉樹(shù)和線索二叉樹(shù)6.3.1 遍歷二叉樹(shù)6.3.2 線索二叉樹(shù)6.4 樹(shù)

3、和森林6.4.1 樹(shù)的存儲(chǔ)結(jié)構(gòu)6.4.2 森林與二叉樹(shù)的轉(zhuǎn)換及遍歷6.6 赫夫曼樹(shù)及應(yīng)用6.6.1 赫夫曼樹(shù)（最優(yōu)二叉樹(shù)）6.6.2 赫夫曼編碼6.1 樹(shù)樹(shù)樹(shù)樹(shù)是n個(gè)結(jié)點(diǎn)的有限集合(可以是空集)，在任一棵非空樹(shù)中：（1）有且僅有一個(gè)稱為根根的結(jié)點(diǎn)。（2）其余結(jié)點(diǎn)可分為互不相交的子集，而且這些子集本身又是一棵樹(shù)，稱為根的子樹(shù)子樹(shù)。JIACBDHGFEKLM從邏輯結(jié)構(gòu)看：從邏輯結(jié)構(gòu)看：1）樹(shù)中只有）樹(shù)中只有樹(shù)根沒(méi)有父結(jié)點(diǎn)樹(shù)根沒(méi)有父結(jié)點(diǎn)；2）除根外，其余結(jié)點(diǎn)都有且僅一個(gè)父結(jié)點(diǎn)；）除根外，其余結(jié)點(diǎn)都有且僅一個(gè)父結(jié)點(diǎn)； 3）樹(shù)中的結(jié)點(diǎn)，可以有零個(gè)或多個(gè)）樹(shù)中的結(jié)點(diǎn)，可以有零個(gè)或多個(gè)孩子結(jié)點(diǎn)孩子結(jié)點(diǎn)； 4

4、) 沒(méi)有孩子的結(jié)點(diǎn)稱為沒(méi)有孩子的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)，或終端結(jié)點(diǎn)；，或終端結(jié)點(diǎn)； 5）除根外的其他結(jié)點(diǎn)，都存在唯一一條從根到該結(jié)點(diǎn)的路徑；）除根外的其他結(jié)點(diǎn)，都存在唯一一條從根到該結(jié)點(diǎn)的路徑；JIACBDHGFEKLM樹(shù)的基本術(shù)語(yǔ)樹(shù)的基本術(shù)語(yǔ)樹(shù)的結(jié)點(diǎn)：樹(shù)的結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向子樹(shù)的分支；包含一個(gè)數(shù)據(jù)元素及若干指向子樹(shù)的分支；孩子結(jié)點(diǎn)：孩子結(jié)點(diǎn)：結(jié)點(diǎn)的子樹(shù)的根稱為該結(jié)點(diǎn)的孩子；結(jié)點(diǎn)的子樹(shù)的根稱為該結(jié)點(diǎn)的孩子；父結(jié)點(diǎn)：父結(jié)點(diǎn)：B 是是A的孩子，則的孩子，則A是是B的父親；的父親；兄弟結(jié)點(diǎn)：兄弟結(jié)點(diǎn)：同一雙親的孩子結(jié)點(diǎn)；同一雙親的孩子結(jié)點(diǎn)；堂兄弟結(jié)點(diǎn)：堂兄弟結(jié)點(diǎn)：其父結(jié)點(diǎn)在同一層上的

5、結(jié)點(diǎn)；其父結(jié)點(diǎn)在同一層上的結(jié)點(diǎn)；祖先結(jié)點(diǎn)祖先結(jié)點(diǎn): 從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)；從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)；子孫結(jié)點(diǎn)：子孫結(jié)點(diǎn)：以某結(jié)點(diǎn)為根的子樹(shù)中任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫；以某結(jié)點(diǎn)為根的子樹(shù)中任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫；結(jié)點(diǎn)的度結(jié)點(diǎn)的度: 結(jié)點(diǎn)的孩子數(shù)目結(jié)點(diǎn)的孩子數(shù)目JIACBDHGFEKLM樹(shù)的基本運(yùn)算樹(shù)的基本運(yùn)算n找樹(shù)的根結(jié)點(diǎn)找樹(shù)的根結(jié)點(diǎn)n求樹(shù)的高度求樹(shù)的高度n找指定結(jié)點(diǎn)的父結(jié)點(diǎn)找指定結(jié)點(diǎn)的父結(jié)點(diǎn)n找指定結(jié)點(diǎn)的孩子結(jié)點(diǎn)找指定結(jié)點(diǎn)的孩子結(jié)點(diǎn)n在樹(shù)中插入、刪除一個(gè)結(jié)點(diǎn)在樹(shù)中插入、刪除一個(gè)結(jié)點(diǎn)n遍歷樹(shù)遍歷樹(shù)n.JIACBDHGFEKLM樹(shù)的表示樹(shù)的表示JIACBDHGFEKLMG

6、CKLEFBMHJIDA(a)(A(B(E(k,L),F),C(G),D(H(M),I(),J()(b)6.2 二叉樹(shù)二叉樹(shù)n二叉樹(shù)的定義：二叉樹(shù)要么為空，要么由根結(jié)二叉樹(shù)的定義：二叉樹(shù)要么為空，要么由根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)組成。左、右子樹(shù)本身也點(diǎn)、左子樹(shù)和右子樹(shù)組成。左、右子樹(shù)本身也是二叉樹(shù)。是二叉樹(shù)。n注意：二叉樹(shù)的子樹(shù)有嚴(yán)格的左右之分，而樹(shù)沒(méi)有。ACBFEDG二叉樹(shù)的子樹(shù)要區(qū)分左子樹(shù)和右子樹(shù)，即使只有一棵子樹(shù)也要進(jìn)行區(qū)分。這是二叉樹(shù)與樹(shù)的最主要的差別。下面列出了二叉樹(shù)的5種基本形態(tài)， (c)和（d）是不同的兩棵二叉樹(shù)。(a)空二叉樹(shù)AABABACB(b)只有根的二叉樹(shù)(c)根和左子樹(shù)(d

7、)根和右子樹(shù)(e)根和左右子樹(shù)二叉樹(shù)的5種基本形式6.2.2 二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì) 性質(zhì)性質(zhì)1 在二叉樹(shù)的第在二叉樹(shù)的第i層上至多有層上至多有2i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) 性質(zhì)性質(zhì)2 深度為深度為k的二叉樹(shù)至多有的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) 性質(zhì)性質(zhì)3任何一個(gè)二叉樹(shù)中度為任何一個(gè)二叉樹(shù)中度為2的結(jié)點(diǎn)數(shù)目的結(jié)點(diǎn)數(shù)目(n2)比度為比度為0的結(jié)點(diǎn)的結(jié)點(diǎn)數(shù)目數(shù)目(n0)少少1，即，即n2 n0-1。KJCFABIHD6.2.2 二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì) 性質(zhì)性質(zhì)3 任何一個(gè)二叉樹(shù)中度為任何一個(gè)二叉樹(shù)中度為2的結(jié)點(diǎn)數(shù)目的結(jié)點(diǎn)數(shù)目(n2)比比度為度為0的結(jié)點(diǎn)數(shù)目的結(jié)點(diǎn)數(shù)目(n0)少少1，即，即n2 n0

8、-1。 證明：設(shè)二叉樹(shù)上葉結(jié)點(diǎn)數(shù)為證明：設(shè)二叉樹(shù)上葉結(jié)點(diǎn)數(shù)為n0，單分支結(jié)點(diǎn)數(shù)，單分支結(jié)點(diǎn)數(shù)為為n1，雙分支結(jié)點(diǎn)數(shù)為，雙分支結(jié)點(diǎn)數(shù)為n2，則總結(jié)點(diǎn)數(shù)，則總結(jié)點(diǎn)數(shù)=n0+n1+n2。 在一棵二叉樹(shù)中，所有結(jié)點(diǎn)的分支數(shù)在一棵二叉樹(shù)中，所有結(jié)點(diǎn)的分支數(shù)(即度數(shù)即度數(shù))應(yīng)應(yīng)等于單分支結(jié)點(diǎn)數(shù)加上雙分支結(jié)點(diǎn)數(shù)的等于單分支結(jié)點(diǎn)數(shù)加上雙分支結(jié)點(diǎn)數(shù)的2倍，即總的倍，即總的分支數(shù)分支數(shù)=n1+2n2。 由于二叉樹(shù)中除根結(jié)點(diǎn)以外，每個(gè)結(jié)點(diǎn)都有惟一由于二叉樹(shù)中除根結(jié)點(diǎn)以外，每個(gè)結(jié)點(diǎn)都有惟一的一個(gè)分支指向它，因此二叉樹(shù)中：總的分支數(shù)的一個(gè)分支指向它，因此二叉樹(shù)中：總的分支數(shù)=總總結(jié)點(diǎn)數(shù)結(jié)點(diǎn)數(shù)-1。 由上述三個(gè)等式可得：

9、由上述三個(gè)等式可得：n1+2n2=n0+n1+n2-1 即：即：n0=n2+1滿二叉樹(shù)和完全二叉樹(shù)滿二叉樹(shù)和完全二叉樹(shù)高度為3的滿二叉樹(shù)高度為3的一個(gè)完全二叉樹(shù)高度為3的一個(gè)完全二叉樹(shù)完全二叉樹(shù)完全二叉樹(shù)高度為3的完全二叉樹(shù)(a)(b)(c)(d)滿二叉樹(shù)和完全二叉樹(shù)滿二叉樹(shù)和完全二叉樹(shù)高度為3的滿二叉樹(shù)高度為3的一個(gè)完全二叉樹(shù)123456712345二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì)(續(xù)續(xù))性質(zhì)性質(zhì)4一個(gè)有一個(gè)有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度Hlog(n)+1。證明：證明： 設(shè)具有設(shè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為h ，則根據(jù)性質(zhì)，則根據(jù)性質(zhì)3：深度為深度

10、為h的二叉樹(shù)至多有的二叉樹(shù)至多有2h-1個(gè)結(jié)點(diǎn)，因此，個(gè)結(jié)點(diǎn)，因此，n =2h-1綜上，綜上， 2h-1 = n 2h，或，或 h-1 = log2n h即即 h = log2n +1 或或 log2n+1 證畢。證畢。二叉樹(shù)的性質(zhì)二叉樹(shù)的性質(zhì)(續(xù)續(xù))性質(zhì)性質(zhì)5完全二叉樹(shù)中的某結(jié)點(diǎn)編號(hào)為完全二叉樹(shù)中的某結(jié)點(diǎn)編號(hào)為i，則，則1) 1) 若有左孩子，則左孩編號(hào)為若有左孩子，則左孩編號(hào)為2i2i2 2）若有右孩子，則右孩子結(jié)點(diǎn)編號(hào)為）若有右孩子，則右孩子結(jié)點(diǎn)編號(hào)為2i+12i+13 3）若有雙親，則雙親結(jié)點(diǎn)編號(hào)為）若有雙親，則雙親結(jié)點(diǎn)編號(hào)為i/2i/2 1 2 3 4 5 8 9 10 11 6 7

11、 完全二叉樹(shù)完全二叉樹(shù) 6.2.3 二叉樹(shù)的順序存儲(chǔ)二叉樹(shù)的順序存儲(chǔ)n二叉樹(shù)的順序存儲(chǔ)指的是用元素在數(shù)組中的下標(biāo)表二叉樹(shù)的順序存儲(chǔ)指的是用元素在數(shù)組中的下標(biāo)表示一個(gè)結(jié)點(diǎn)與其孩子和父結(jié)點(diǎn)的關(guān)系示一個(gè)結(jié)點(diǎn)與其孩子和父結(jié)點(diǎn)的關(guān)系.n完全二叉樹(shù)的順序存儲(chǔ)完全二叉樹(shù)的順序存儲(chǔ)DCFABA B C D E F12345678910 11 12#define MAX_TREE_SIZE 100typedef TelemType SqBiTreeMAX_TREE_SIZE;SqBiTree bt;二叉樹(shù)的順序存儲(chǔ)二叉樹(shù)的順序存儲(chǔ)n非完全二叉樹(shù)的順序存儲(chǔ)非完全二叉樹(shù)的順序存儲(chǔ)GFCDABA B CD EF G1

12、2345678910 11 12 13 14 15 16F非完全二叉樹(shù)不適合進(jìn)行順序存儲(chǔ)非完全二叉樹(shù)不適合進(jìn)行順序存儲(chǔ)二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)n一般用二叉鏈表存儲(chǔ)二叉樹(shù)一般用二叉鏈表存儲(chǔ)二叉樹(shù)(每個(gè)結(jié)點(diǎn)有兩個(gè)指針域每個(gè)結(jié)點(diǎn)有兩個(gè)指針域)GFCDABABCEDFGrootLchilddataRchildtypedef struct BiTNode TElemType data; struct BiTNode *Lchild,*Rchild;BiTNode, *BiTree;二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)n三叉鏈表存儲(chǔ)三叉鏈表存儲(chǔ)(每個(gè)節(jié)點(diǎn)有三個(gè)指針域每個(gè)節(jié)點(diǎn)有三個(gè)指針域)GFCDABA

13、BCEDFGrootLchilddataRchildParent6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)n任何一個(gè)非空的二叉樹(shù)都由三部分構(gòu)成任何一個(gè)非空的二叉樹(shù)都由三部分構(gòu)成DLR根結(jié)點(diǎn)根的左子樹(shù)根的右子樹(shù)F樹(shù)的遍歷是訪問(wèn)樹(shù)中每個(gè)結(jié)點(diǎn)僅一次的過(guò)程。遍歷可以被樹(shù)的遍歷是訪問(wèn)樹(shù)中每個(gè)結(jié)點(diǎn)僅一次的過(guò)程。遍歷可以被認(rèn)為是把所有的結(jié)點(diǎn)放在一條線上，或者將一棵樹(shù)進(jìn)行線認(rèn)為是把所有的結(jié)點(diǎn)放在一條線上，或者將一棵樹(shù)進(jìn)行線性化的處理。性化的處理。6.3.1 二叉樹(shù)的遍歷二叉樹(shù)的遍歷先左后右：DLR，LDR，LRDDLR根結(jié)點(diǎn)根的左子樹(shù)根的右子樹(shù)v先右后左：DRL，RDL，RLD先序遍歷先序遍歷nDL

14、R：訪問(wèn)根結(jié)點(diǎn)、先序遍歷左子樹(shù)、先序遍歷右子樹(shù)DLR123先序遍歷先序遍歷nDLR：訪問(wèn)根結(jié)點(diǎn)、先序遍歷左子樹(shù)、先序遍歷右子樹(shù)若二叉樹(shù)非空 （1）訪問(wèn)根結(jié)點(diǎn)； （2）先序遍歷左子樹(shù)； （3）先序遍歷右子樹(shù)；若二叉樹(shù)為空，結(jié)束 基本項(xiàng)（也叫終止項(xiàng)）若二叉樹(shù)非空 遞歸項(xiàng) （1）訪問(wèn)根結(jié)點(diǎn)； （2）先序遍歷左子樹(shù)； （3）先序遍歷右子樹(shù)；DLR void preorder (BiTNode *root) /先序遍歷root指向根的二叉樹(shù) if (root!=NULL) coutdata；/訪問(wèn)根結(jié)點(diǎn) preorder(root-Lchild); /先序遍歷根的左子樹(shù) preorder(root-Rc

15、hild); /先序遍歷根的右子樹(shù) /if /preorder先序遍歷先序遍歷LchilddataRchildCDABABCEDroot void preorder (BiTNode *root) if (root!=NULL) coutdata；/訪問(wèn)根結(jié)點(diǎn) preorder(root-Lchild); /先序遍歷根的左子樹(shù) preorder(root-Rchild); /先序遍歷根的右子樹(shù) /if /preorderBACEDGFroot先序遍歷序列：root: A void preorder (BiTNode *root) if (root!=NULL) coutdata；/訪問(wèn)根結(jié)點(diǎn)

16、preorder(root-Lchild); /先序遍歷根的左子樹(shù) preorder(root-Rchild); /先序遍歷根的右子樹(shù) /if /preorderBACEDGFroot先序遍歷序列： Aroot: A void preorder (BiTNode *root) if (root!=NULL) coutdata；/訪問(wèn)根結(jié)點(diǎn) preorder(root-Lchild); /先序遍歷根的左子樹(shù) preorder(root-Rchild); /先序遍歷根的右子樹(shù) /if /preorderBACEDGFrootroot: Broot: A先序遍歷序列： A B void preord

17、er (BiTNode *root) if (root!=NULL) coutdata；/訪問(wèn)根結(jié)點(diǎn) preorder(root-Lchild); /先序遍歷根的左子樹(shù) preorder(root-Rchild); /先序遍歷根的右子樹(shù) /if /preorderBACEDGFrootroot: Broot: A先序遍歷序列： A Broot: DD void preorder (BiTNode *root) if (root!=NULL) coutdata；/訪問(wèn)根結(jié)點(diǎn) preorder(root-Lchild); /先序遍歷根的左子樹(shù) preorder(root-Rchild); /先序遍

18、歷根的右子樹(shù) /if /preorderBACEDGFrootroot: Broot: A先序遍歷序列： A Broot: DD root: NULLD void preorder (BiTNode *root) if (root!=NULL) coutdata；/訪問(wèn)根結(jié)點(diǎn) preorder(root-Lchild); /先序遍歷根的左子樹(shù) preorder(root-Rchild); /先序遍歷根的右子樹(shù) /if /preorderBACEDGFrootroot: Broot: A先序遍歷序列： A Broot: DD void preorder (BiTNode *root) if (r

19、oot!=NULL) coutdata；/訪問(wèn)根結(jié)點(diǎn) preorder(root-Lchild); /先序遍歷根的左子樹(shù) preorder(root-Rchild); /先序遍歷根的右子樹(shù) /if /preorderBACEDGFrootroot: Broot: A先序遍歷序列： A Broot: DD root: NULLD void preorder (BiTNode *root) if (root!=NULL) coutdata；/訪問(wèn)根結(jié)點(diǎn) preorder(root-Lchild); /先序遍歷根的左子樹(shù) preorder(root-Rchild); /先序遍歷根的右子樹(shù) /if /

20、preorderBACEDGFrootroot: Broot: A先序遍歷序列： A Broot: DD E E void preorder (BiTNode *root) if (root!=NULL) coutdata；/訪問(wèn)根結(jié)點(diǎn) preorder(root-Lchild); /先序遍歷根的左子樹(shù) preorder(root-Rchild); /先序遍歷根的右子樹(shù) /if /preorderBACDGFrootroot: Broot: A先序遍歷序列： A B Droot: EEG void preorder (BiTNode *root) if (root!=NULL) coutdat

21、a；/訪問(wèn)根結(jié)點(diǎn) preorder(root-Lchild); /先序遍歷根的左子樹(shù) preorder(root-Rchild); /先序遍歷根的右子樹(shù) /if /preorderBACEDGFrootroot: Broot: A先序遍歷序列： A B Droot: EEGroot: GE void preorder (BiTNode *root) if (root!=NULL) coutdata；/訪問(wèn)根結(jié)點(diǎn) preorder(root-Lchild); /先序遍歷根的左子樹(shù) preorder(root-Rchild); /先序遍歷根的右子樹(shù) /if /preorderBACEDGFroot

22、root: Broot: A先序遍歷序列： A B Droot: EEGB void preorder (BiTNode *root) if (root!=NULL) coutdata；/訪問(wèn)根結(jié)點(diǎn) preorder(root-Lchild); /先序遍歷根的左子樹(shù) preorder(root-Rchild); /先序遍歷根的右子樹(shù) /if /preorderBACEDGFrootroot: Broot: A先序遍歷序列： A B DEGA void preorder (BiTNode *root) if (root!=NULL) coutdata；/訪問(wèn)根結(jié)點(diǎn) preorder(root-L

23、child); /先序遍歷根的左子樹(shù) preorder(root-Rchild); /先序遍歷根的右子樹(shù) /if /preorderBACEDGFrootroot: A先序遍歷序列： A B DEGC void preorder (BiTNode *root) if (root!=NULL) coutdata；/訪問(wèn)根結(jié)點(diǎn) preorder(root-Lchild); /先序遍歷根的左子樹(shù) preorder(root-Rchild); /先序遍歷根的右子樹(shù) /if /preorderBACEDGFrootroot: A先序遍歷序列： A B DEGroot: CC void preorder

24、(BiTNode *root) if (root!=NULL) coutdata；/訪問(wèn)根結(jié)點(diǎn) preorder(root-Lchild); /先序遍歷根的左子樹(shù) preorder(root-Rchild); /先序遍歷根的右子樹(shù) /if /preorderBACEDGFrootroot: A先序遍歷序列： A B DEGroot: CCroot: NULLC void preorder (BiTNode *root) if (root!=NULL) coutdata；/訪問(wèn)根結(jié)點(diǎn) preorder(root-Lchild); /先序遍歷根的左子樹(shù) preorder(root-Rchild);

25、 /先序遍歷根的右子樹(shù) /if /preorderBACEDGFrootroot: A先序遍歷序列： A B DEGroot: CCF void preorder (BiTNode *root) if (root!=NULL) coutdata；/訪問(wèn)根結(jié)點(diǎn) preorder(root-Lchild); /先序遍歷根的左子樹(shù) preorder(root-Rchild); /先序遍歷根的右子樹(shù) /if /preorderBACEDGFrootroot: A先序遍歷序列： A B DEGroot: CCroot: FFC void preorder (BiTNode *root) if (root

26、!=NULL) coutdata；/訪問(wèn)根結(jié)點(diǎn) preorder(root-Lchild); /先序遍歷根的左子樹(shù) preorder(root-Rchild); /先序遍歷根的右子樹(shù) /if /preorderBACEDGFrootroot: A先序遍歷序列： A B DEGroot: CCFA void preorder (BiTNode *root) if (root!=NULL) coutdata；/訪問(wèn)根結(jié)點(diǎn) preorder(root-Lchild); /先序遍歷根的左子樹(shù) preorder(root-Rchild); /先序遍歷根的右子樹(shù) /if /preorderBACEDGFr

27、ootroot: A先序遍歷序列： A B DEGCF void preorder (BiTNode *root) if (root!=NULL) coutdata；/訪問(wèn)根結(jié)點(diǎn) preorder(root-Lchild); /先序遍歷根的左子樹(shù) preorder(root-Rchild); /先序遍歷根的右子樹(shù) /if /preorderBACEDGFroot先序遍歷序列： A B DEGCF先序遍歷過(guò)程先序遍歷過(guò)程BACEDGF先序遍歷序列：先序遍歷序列： A B DEG C FABDEGCF遞歸調(diào)用遞歸調(diào)用返回返回 void preorder (BiTNode *root) if (ro

28、ot!=NULL) coutdata；/訪問(wèn)根結(jié)點(diǎn) preorder(root-Lchild); /先序遍歷根的左子樹(shù) preorder(root-Rchild); /先序遍歷根的右子樹(shù) /if /preorderroot: Aroot: Broot: Eroot: G棧在先序遍歷中的作用棧在先序遍歷中的作用BACEDGFroot先序遍歷序列： A B DEGn棧用于保存當(dāng)前結(jié)點(diǎn)的祖先結(jié)點(diǎn)棧用于保存當(dāng)前結(jié)點(diǎn)的祖先結(jié)點(diǎn)中序遍歷中序遍歷nLDR：中序遍歷左子樹(shù)、訪問(wèn)根結(jié)點(diǎn)、中序遍歷右子樹(shù)DLR213中序遍歷中序遍歷nLDR：中序遍歷左子樹(shù)、訪問(wèn)根結(jié)點(diǎn)、中序遍歷右子樹(shù)若二叉樹(shù)非空 （1）中序遍歷左子

29、樹(shù)； （2）訪問(wèn)根結(jié)點(diǎn)； （3）中序遍歷右子樹(shù)；若二叉樹(shù)為空，結(jié)束 基本項(xiàng)（也叫終止項(xiàng)）若二叉樹(shù)非空 遞歸項(xiàng) （1）中序遍歷左子樹(shù)； （2）訪問(wèn)根結(jié)點(diǎn)； （3）中序遍歷右子樹(shù)；DLR void inorder (BiTNode *root) /中序遍歷root指向根的二叉樹(shù) if (root!=NULL) inorder(root-Lchild); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn) inorder(root-Rchild); /中序遍歷根的右子樹(shù) /if /inorder中序遍歷中序遍歷LchilddataRchild void inorder (BiTNode *root

30、) if (root!=NULL) inorder(root-Lchild); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn) inorder(root-Rchild); /中序遍歷根的右子樹(shù) /if /inorderBACEDGFroot中序遍歷序列：root: A void inorder (BiTNode *root) if (root!=NULL) inorder(root-Lchild); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn) inorder(root-Rchild); /中序遍歷根的右子樹(shù) /if /inorderBACEDGFroot中序遍歷序列：root:

31、 Aroot: B void inorder (BiTNode *root) if (root!=NULL) inorder(root-Lchild); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn) inorder(root-Rchild); /中序遍歷根的右子樹(shù) /if /inorderBACEDGFroot中序遍歷序列：root: Aroot: Broot: D void inorder (BiTNode *root) if (root!=NULL) inorder(root-Lchild); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn) inorder(root-Rchi

32、ld); /中序遍歷根的右子樹(shù) /if /inorderBACEDGFroot中序遍歷序列：root: Aroot: Broot: D root: NULL void inorder (BiTNode *root) if (root!=NULL) inorder(root-Lchild); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn) inorder(root-Rchild); /中序遍歷根的右子樹(shù) /if /inorderBACEDGFroot中序遍歷序列：root: Aroot: Broot: D D void inorder (BiTNode *root) if (root!=N

33、ULL) inorder(root-Lchild); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn) inorder(root-Rchild); /中序遍歷根的右子樹(shù) /if /inorderBACEDGFroot中序遍歷序列：root: Aroot: Broot: D Droot: NULL void inorder (BiTNode *root) if (root!=NULL) inorder(root-Lchild); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn) inorder(root-Rchild); /中序遍歷根的右子樹(shù) /if /inorderBACEDGFroo

34、t中序遍歷序列：root: Aroot: Broot: D D void inorder (BiTNode *root) if (root!=NULL) inorder(root-Lchild); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn) inorder(root-Rchild); /中序遍歷根的右子樹(shù) /if /inorderBACEDGFroot中序遍歷序列：root: Aroot: BD B void inorder (BiTNode *root) if (root!=NULL) inorder(root-Lchild); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn)

35、 inorder(root-Rchild); /中序遍歷根的右子樹(shù) /if /inorderBACEDGFroot中序遍歷序列：root: Aroot: BD Broot: E void inorder (BiTNode *root) if (root!=NULL) inorder(root-Lchild); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn) inorder(root-Rchild); /中序遍歷根的右子樹(shù) /if /inorderBACEDGFroot中序遍歷序列：root: Aroot: BD Broot: Eroot: G void inorder (BiTNode

36、*root) if (root!=NULL) inorder(root-Lchild); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn) inorder(root-Rchild); /中序遍歷根的右子樹(shù) /if /inorderBACEDGFroot中序遍歷序列：root: Aroot: BD Broot: Eroot: Groot: NULL void inorder (BiTNode *root) if (root!=NULL) inorder(root-Lchild); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn) inorder(root-Rchild); /中序遍歷根的

37、右子樹(shù) /if /inorderBACEDGFroot中序遍歷序列：root: Aroot: BD Broot: Eroot: GG void inorder (BiTNode *root) if (root!=NULL) inorder(root-Lchild); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn) inorder(root-Rchild); /中序遍歷根的右子樹(shù) /if /inorderBACEDGFroot中序遍歷序列：root: Aroot: BD Broot: EG E void inorder (BiTNode *root) if (root!=NULL) ino

38、rder(root-Lchild); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn) inorder(root-Rchild); /中序遍歷根的右子樹(shù) /if /inorderBACEDGFroot中序遍歷序列：root: Aroot: BD B G E void inorder (BiTNode *root) if (root!=NULL) inorder(root-Lchild); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn) inorder(root-Rchild); /中序遍歷根的右子樹(shù) /if /inorderBACEDGFroot中序遍歷序列：root: AD B G

39、 E A void inorder (BiTNode *root) if (root!=NULL) inorder(root-Lchild); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn) inorder(root-Rchild); /中序遍歷根的右子樹(shù) /if /inorderBACEDGFroot中序遍歷序列：root: AD B G E Aroot: C void inorder (BiTNode *root) if (root!=NULL) inorder(root-Lchild); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn) inorder(root-Rchild)

40、; /中序遍歷根的右子樹(shù) /if /inorderBACEDGFroot中序遍歷序列：root: AD B G E Aroot: Croot: NULL void inorder (BiTNode *root) if (root!=NULL) inorder(root-Lchild); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn) inorder(root-Rchild); /中序遍歷根的右子樹(shù) /if /inorderBACEDGFroot中序遍歷序列：root: AD B G E Aroot: CC void inorder (BiTNode *root) if (root!=NU

41、LL) inorder(root-Lchild); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn) inorder(root-Rchild); /中序遍歷根的右子樹(shù) /if /inorderBACEDGFroot中序遍歷序列：root: AD B G E Aroot: CCroot: F void inorder (BiTNode *root) if (root!=NULL) inorder(root-Lchild); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn) inorder(root-Rchild); /中序遍歷根的右子樹(shù) /if /inorderBACEDGFroot中序

42、遍歷序列：root: AD B G E Aroot: CCroot: Froot: NULL void inorder (BiTNode *root) if (root!=NULL) inorder(root-Lchild); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn) inorder(root-Rchild); /中序遍歷根的右子樹(shù) /if /inorderBACEDGFroot中序遍歷序列：root: AD B G E Aroot: CCroot: FF void inorder (BiTNode *root) if (root!=NULL) inorder(root-Lchil

43、d); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn) inorder(root-Rchild); /中序遍歷根的右子樹(shù) /if /inorderBACEDGFroot中序遍歷序列：root: AD B G E Aroot: CC F void inorder (BiTNode *root) if (root!=NULL) inorder(root-Lchild); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn) inorder(root-Rchild); /中序遍歷根的右子樹(shù) /if /inorderBACEDGFroot中序遍歷序列：root: AD B G E A C F v

44、oid inorder (BiTNode *root) if (root!=NULL) inorder(root-Lchild); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn) inorder(root-Rchild); /中序遍歷根的右子樹(shù) /if /inorderBACEDGFroot中序遍歷序列：D B G E A C FBACEDGFrootroot: Aroot: Broot: Eroot: G棧在中序遍歷中的作用棧在中序遍歷中的作用中序遍歷序列： D B Gn棧用于保存當(dāng)前結(jié)點(diǎn)的祖先結(jié)點(diǎn)棧用于保存當(dāng)前結(jié)點(diǎn)的祖先結(jié)點(diǎn)后序遍歷后序遍歷nLRD：后序遍歷左子樹(shù)、后序遍歷右子樹(shù)、訪

45、問(wèn)根結(jié)點(diǎn)DLR312GFCDAB后序后序遍歷序列:BDFGECA void inorder (BiTNode *root) if (root!=NULL) inorder(root-Lchild); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn) inorder(root-Rchild); /中序遍歷根的右子樹(shù) /if /inordervoid preorder (BiTNode *root) if (root!=NULL) coutdata；/訪問(wèn)根結(jié)點(diǎn) preorder(root-Lchild); /先序遍歷根的左子樹(shù) preorder(root-Rchild); /先序遍歷根的右子

46、樹(shù) /if/preordervoid postorder (BiTNode *root) if (root!=NULL) postorder(root-Lchild); /后序遍歷根的左子樹(shù)后序遍歷根的左子樹(shù) postorder(root-Rchild); /后序遍歷根的右子樹(shù)后序遍歷根的右子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn)訪問(wèn)根結(jié)點(diǎn) /if/postorder void inorder (BiTNode *root) if (root!=NULL) inorder(root-Lchild); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn) inorder(root-Rchild);

47、/中序遍歷根的右子樹(shù)中序遍歷根的右子樹(shù) /if /inorderBACEDGFrootroot: Aroot: Broot: EE中序遍歷序列：中序遍歷序列：D B Gvoid InOrder (BiTNode *root) InitStack(S); Push(S,root); /根指針進(jìn)棧 while (!StackEmpty(S) while(GetTop(S,p)&p) Push(S,p-Lchild); /向左走到頭向左走到頭 Pop(S,p); /空指針退棧空指針退棧 if (!StackEmpty(S) Pop(S,p); cout data; /訪問(wèn)結(jié)點(diǎn)訪問(wèn)結(jié)點(diǎn) Pus

48、h(S,p-Rchild); /向右向右 /if /while /InOrder void inorder (BiTNode *root) if (root!=NULL) inorder(root-Lchild); /中序遍歷根的左子樹(shù) coutdata；/訪問(wèn)根結(jié)點(diǎn) inorder(root-Rchild); /中序遍歷根的右子樹(shù)中序遍歷根的右子樹(shù) /if /inorderBACEDGFrootroot: Aroot: Broot: EE中序遍歷序列：中序遍歷序列：D B Gvoid InOrder (BiTNode *root) InitStack(S); p = root; /根指針進(jìn)棧

49、 while (p | !StackEmpty(S) if (p) Push(S, p); p = p-Lchild; else /根指針退棧，訪問(wèn)根結(jié)點(diǎn)，遍歷右子樹(shù)根指針退棧，訪問(wèn)根結(jié)點(diǎn)，遍歷右子樹(shù) Pop(S,p); cout data; p = p-Rchild; /if-else /while /InOrder用二叉樹(shù)表示表達(dá)式用二叉樹(shù)表示表達(dá)式na + b * ( c d ) e / f/e-+*abc先序先序遍歷序列: + a * b c d / e f中序中序遍歷序列: a + b * c d e / f后序后序遍歷序列: a b c d * + e f / F 表達(dá)式的前綴、中

50、綴和后綴表示表達(dá)式的前綴、中綴和后綴表示用棧對(duì)后綴表達(dá)式求值用棧對(duì)后綴表達(dá)式求值表達(dá)式的表達(dá)式的后綴表示后綴表示: a b c d * + e f / bacdbat1t2at1 = c dt2 = b * t1t3 = a + t2t3et3ft4 = e / ft4t3t5t5 = t3 t4層序遍歷層序遍歷n先根，后子樹(shù)；先左子樹(shù)，后右子樹(shù)GFCDAB隊(duì)列隊(duì)頭樹(shù)根結(jié)點(diǎn)A入隊(duì)層序?qū)有虮闅v序列:層序遍歷層序遍歷GFCDAB隊(duì)列隊(duì)頭A層序?qū)有虮闅v序列:A出隊(duì)n先根，后子樹(shù)；先左子樹(shù)，后右子樹(shù)層序遍歷層序遍歷n先根，后子樹(shù)；先左子樹(shù)，后右子樹(shù)GFCDAB隊(duì)列隊(duì)頭根結(jié)點(diǎn)B、C入隊(duì)A的子樹(shù)層序?qū)有虮?/p>

51、歷序列: A層序遍歷層序遍歷n先根，后子樹(shù)；先左子樹(shù)，后右子樹(shù)GFCDAB隊(duì)列隊(duì)頭BB出隊(duì)C層序?qū)有虮闅v序列: A層序遍歷層序遍歷n先根，后子樹(shù)；先左子樹(shù)，后右子樹(shù)GFCDAB隊(duì)列隊(duì)頭C根結(jié)點(diǎn)入隊(duì)B的子樹(shù)層序?qū)有虮闅v序列: AB層序遍歷層序遍歷n先根，后子樹(shù)；先左子樹(shù)，后右子樹(shù)GFCDAB隊(duì)列隊(duì)頭CC出隊(duì)層序?qū)有虮闅v序列: AB層序遍歷層序遍歷n先根，后子樹(shù)；先左子樹(shù)，后右子樹(shù)GFCDAB隊(duì)列隊(duì)頭根結(jié)點(diǎn)入隊(duì)C的子樹(shù)層序?qū)有虮闅v序列: ABC層序遍歷層序遍歷n先根，后子樹(shù)；先左子樹(shù)，后右子樹(shù)GFCDAB隊(duì)列隊(duì)頭DED出隊(duì)層序?qū)有虮闅v序列: ABC層序遍歷層序遍歷n先根，后子樹(shù)；先左子樹(shù)，后右子樹(shù)

52、GFCDAB隊(duì)列隊(duì)頭E根結(jié)點(diǎn)入隊(duì)D的子樹(shù)層序?qū)有虮闅v序列: ABCD層序遍歷層序遍歷n先根，后子樹(shù)；先左子樹(shù)，后右子樹(shù)GFCDAB隊(duì)列隊(duì)頭EE出隊(duì)層序?qū)有虮闅v序列: ABCD層序遍歷層序遍歷n先根，后子樹(shù)；先左子樹(shù)，后右子樹(shù)GFCDAB隊(duì)列隊(duì)頭根結(jié)點(diǎn)F、G入隊(duì)E的子樹(shù)層序?qū)有虮闅v序列: ABCDE層序遍歷層序遍歷n先根，后子樹(shù)；先左子樹(shù)，后右子樹(shù)GFCDAB隊(duì)列隊(duì)頭FGF出隊(duì)層序?qū)有虮闅v序列: ABCDE層序遍歷層序遍歷n先根，后子樹(shù)；先左子樹(shù)，后右子樹(shù)GFCDAB隊(duì)列隊(duì)頭G根結(jié)點(diǎn)入隊(duì)F的子樹(shù)層序?qū)有虮闅v序列: ABCDEF層序遍歷層序遍歷n先根，后子樹(shù)；先左子樹(shù)，后右子樹(shù)GFCDAB隊(duì)列隊(duì)頭

53、GG出隊(duì)層序?qū)有虮闅v序列: ABCDEF層序遍歷層序遍歷n先根，后子樹(shù)；先左子樹(shù)，后右子樹(shù)GFCDAB層序?qū)有虮闅v序列: ABCDEFG利用隊(duì)列實(shí)現(xiàn)二叉樹(shù)的層序遍歷：構(gòu)造一個(gè)空隊(duì)列；樹(shù)根結(jié)點(diǎn)入隊(duì)列；while （隊(duì)列不空） 隊(duì)頭元素出隊(duì)列； 訪問(wèn)結(jié)點(diǎn)； 剛出隊(duì)的結(jié)點(diǎn)的左孩子、右孩子結(jié)點(diǎn)先后入隊(duì)列； 6.3.2 線索二叉樹(shù)線索二叉樹(shù)Ltag=LchilddataRchildLchilddataRchildRtagLtag0 Lchild指向左子樹(shù)根結(jié)點(diǎn)1 Lchild指向前驅(qū)結(jié)點(diǎn)Rtag=0 Rchild指向右子樹(shù)根結(jié)點(diǎn)1 Rchild指向后繼結(jié)點(diǎn)typedef enum PointerTag

54、Link=0,Thread=1;typedef struct BiThrNode ElemType data; struct BiThrNode *Lchild,*Rchild; PointerTag Ltag, Rtag;*BiThrTree;BACEDGFrootBACEDGFroot中序線索二叉樹(shù)中序線索二叉樹(shù)NULL中序序列：DBGEACFNULLBACEDGFroot中序線索二叉樹(shù)中序線索二叉樹(shù)NULL中序序列：DBGEACFNULLn在中序線索化二叉樹(shù)上查找給定結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn)中序線索二叉樹(shù)中序線索二叉樹(shù)在中序線索二叉樹(shù)上，查找p所指結(jié)點(diǎn)的后繼分為兩種情況：(1) 若p-Rta

55、g=1，則p-Rchild指向其后繼結(jié)點(diǎn)； (2) 若p-Rtag=0，則p所指結(jié)點(diǎn)的中序后繼必為其右子樹(shù)中序遍歷得到的第一個(gè)結(jié)點(diǎn)，即從p所指結(jié)點(diǎn)的右子樹(shù)根出發(fā)，沿左指針鏈向下找，直到找到一個(gè)沒(méi)有左孩子的結(jié)點(diǎn)為止，這個(gè)結(jié)點(diǎn)稱為p的右子樹(shù)中“最左下”的結(jié)點(diǎn)。BACEDGFroot中序線索二叉樹(shù)中序線索二叉樹(shù)NULLNULLIH中序線索二叉樹(shù)中序線索二叉樹(shù)n中序線索二叉樹(shù)上找指定結(jié)點(diǎn)的后繼： BiThrTree inordernext(BiThrTree p) if （p-rtag=1） return(p-Rchild); else q=p-Rchild; while (q-ltag=0) q=q

56、-Lchild; return(q); typedef struct BiThrNode ElemType data;struct BiThrNode *Lchild,*Rchild; PointerTag Ltag,Rtag;*BiThrTree;建立中序線索二叉樹(shù)建立中序線索二叉樹(shù)n線索化的實(shí)質(zhì)是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索，而前驅(qū)或后繼的信息只有在遍歷時(shí)才能得到，因此線索化的過(guò)程就是在遍歷過(guò)程中修改空指針的過(guò)程。 void InOrderThreading(BiThrTree &Thrt, BiThrTree root) /Thrt指向中序線索化鏈表的頭結(jié)點(diǎn)指向中

57、序線索化鏈表的頭結(jié)點(diǎn) if (!Thrt = (BiThrTriTree)malloc(sizeof(BiThrNode) exit(OVERFLOW); Thrt-Ltag = Link; Thrt-Rtag = Thread; Thrt-Rchild = Thrt; if (root = NULL) Thrt-Lchild = Thrt; else Thrt-Lchild = root; pre = Thrt; InThreading(root); /中序遍歷進(jìn)行中序線索化中序遍歷進(jìn)行中序線索化 pre-Rchild = Thrt; pre-Rtag = Thread; Thrt-Rchi

58、ld = pre; /InOrderThreadingLchilddataRchildRtagLtagvoid InThreading(BiThrTree p) if (p) InThreading(p-Lchild); /左子樹(shù)線索化左子樹(shù)線索化 if (!p-Lchild) /前驅(qū)線索前驅(qū)線索 p-Ltag = Thread; p-Lchild = pre; if (!pre-Rchild) /后繼線索后繼線索 pre-Rtag = Thread; pre-Rchild = p; pre = p; InThreading(p-Rchild); /右子樹(shù)線索化右子樹(shù)線索化 /InThread

59、ingBACEDGFroot后序線索二叉樹(shù)后序線索二叉樹(shù)后序序列：IDGHEBFCANULLn在后序線索化二叉樹(shù)上查找給定結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn)HI后序線索二叉樹(shù)后序線索二叉樹(shù)在后序線索二叉樹(shù)上，查找p所指結(jié)點(diǎn)的后繼分為兩種情況：(1) 若p所指結(jié)點(diǎn)是整棵二叉樹(shù)的根結(jié)點(diǎn)，則無(wú)后繼結(jié)點(diǎn)；(3) 若p-Rtag=0：/P所指結(jié)點(diǎn)有右子樹(shù) 若p所指結(jié)點(diǎn)是其父結(jié)點(diǎn)f的右孩子，則其父結(jié)點(diǎn)f是其后繼； 若p所指結(jié)點(diǎn)是其父結(jié)點(diǎn)f的左孩子： 若p所指結(jié)點(diǎn)沒(méi)有右兄弟，則其父結(jié)點(diǎn)f是其后繼； 若P有右兄弟，則其后繼結(jié)點(diǎn)是其父的右子樹(shù)上后序遍歷得到的第一個(gè)結(jié)點(diǎn)。 (2) 若p-Rtag=1，則p-Rchild指向其后

60、繼結(jié)點(diǎn)；后序線索二叉樹(shù)后序線索二叉樹(shù)后序線索二叉樹(shù)上找指定結(jié)點(diǎn)的后繼 BiThrTree postorder_next(BiThrTree p) if (p-Rtag = 1) return(p-Rchild); else 查找p所指節(jié)點(diǎn)的父結(jié)點(diǎn)f; if (p = f-Rchild) return f; if (p = f-Lchild & f-Rtag = 1) return f; q = f-Rchild; while (q-Ltag = 0 | q -Rtag = 0) if (q-Ltag = 0) q = q-Lchild; else q = q-Rchild; /*end of while*/