第6章樹(shù)和二叉樹(shù)6.1樹(shù)的定義和基本術(shù)語(yǔ)6.2二叉樹(shù)6.3遍歷二叉樹(shù)和線索二叉樹(shù)6.4樹(shù)和森林6.6赫夫曼樹(shù)及其應(yīng)用特點(diǎn)：非線性結(jié)構(gòu)，一個(gè)直接前驅(qū)，但可能有多個(gè)直接后繼（1：n）16.1

樹(shù)的定義和基本術(shù)語(yǔ)1.樹(shù)的定義2.若干術(shù)語(yǔ)3.邏輯結(jié)構(gòu)4.存儲(chǔ)結(jié)構(gòu)5.樹(shù)的運(yùn)算21.樹(shù)的定義注1：過(guò)去許多書(shū)籍中都定義樹(shù)為n≥1，曾經(jīng)有“空樹(shù)不是樹(shù)”的說(shuō)法，但現(xiàn)在樹(shù)的定義已修改。注2：樹(shù)的定義具有遞歸性，即樹(shù)的定義中還有樹(shù)。樹(shù)（Tree）是n個(gè)(n≥0)結(jié)點(diǎn)組成的有限集合T。在任何一棵非空樹(shù)中：（1）有且僅有一個(gè)結(jié)點(diǎn)稱(chēng)為根（root）；（2）當(dāng)n>1時(shí)，其余的結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集合T1,T2，…，Tm。其中，每個(gè)集合本身又是一棵樹(shù)，被稱(chēng)作這個(gè)根的子樹(shù)（SubTree）。3A只有根結(jié)點(diǎn)的樹(shù)ABCDEFGHIJKLM有子樹(shù)的樹(shù)根子樹(shù)4樹(shù)的抽象數(shù)據(jù)類(lèi)型定義（見(jiàn)教材P118-119）ADTTree{數(shù)據(jù)對(duì)象D:數(shù)據(jù)關(guān)系R:基本操作P：}ADTTree若D為空集，則稱(chēng)為空樹(shù)；//允許n=0若D中僅含一個(gè)數(shù)據(jù)元素，則R為空集；否則R={H}，H是如下二元關(guān)系：

①在D中存在唯一根元素root，在H下無(wú)前驅(qū)

②若D-{root}≠Φ，則存在對(duì)D-{root}的一個(gè)劃分，對(duì)任意j≠k，有Dj∩Dk=Φ，且<>∈H...

③對(duì)應(yīng)于D-{root}

的劃分，H-……有唯一一個(gè)劃分，對(duì)任意j≠k，有Hj∩Hk=Φ。(Di,{Hi})D是具有相同特性的數(shù)據(jù)元素的集合。//至少有15個(gè)5

基本操作：查找類(lèi)插入類(lèi)刪除類(lèi)6

Root(T)//求樹(shù)的根結(jié)點(diǎn)

查找類(lèi)：Value(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的元素值

Parent(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)LeftChild(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的最左孩子RightSibling(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的右兄弟TreeEmpty(T)//判定樹(shù)是否為空樹(shù)TreeDepth(T)//求樹(shù)的深度TraverseTree(T,Visit())//遍歷7InitTree(&T)//初始化置空樹(shù)

插入類(lèi)：CreateTree(&T,definition)//按定義構(gòu)造樹(shù)Assign(T,cur_e,value)//給當(dāng)前結(jié)點(diǎn)賦值InsertChild(&T,&p,i,c)//將以c為根的樹(shù)插入為結(jié)點(diǎn)p的第i棵子樹(shù)8

ClearTree(&T)//將樹(shù)清空

刪除類(lèi)：DestroyTree(&T)//銷(xiāo)毀樹(shù)的結(jié)構(gòu)DeleteChild(&T,&p,i)//刪除結(jié)點(diǎn)p的第i棵子樹(shù)9樹(shù)的表示法有幾種：圖形表示法嵌套集合表示法廣義表表示法凹入表示法左孩子－右兄弟表示法這些表示法的示意圖參見(jiàn)教材P120圖6.210廣義表表示法(A(B(E(K,L),F),C(G),D(H(M),I,J)))根作為由子樹(shù)森林組成的表的名字寫(xiě)在表的左邊11左孩子－右兄弟表示法ABCDEFGHIJKLM數(shù)據(jù)左孩子

右兄弟(A(B(E(K,L),F),C(G),D(H(M),I,J)))122.若干術(shù)語(yǔ)——即上層的那個(gè)結(jié)點(diǎn)(直接前驅(qū))——即下層結(jié)點(diǎn)的子樹(shù)的根(直接后繼)——同一雙親下的同層結(jié)點(diǎn)（孩子之間互稱(chēng)兄弟）——即雙親位于同一層的結(jié)點(diǎn)（但并非同一雙親）——即從根到該結(jié)點(diǎn)所經(jīng)分支的所有結(jié)點(diǎn)——即該結(jié)點(diǎn)下層子樹(shù)中的任一結(jié)點(diǎn)ABCGEIDHFJMLK

根葉子森林有序樹(shù)無(wú)序樹(shù)——即根結(jié)點(diǎn)(沒(méi)有前驅(qū))——即終端結(jié)點(diǎn)(沒(méi)有后繼)——指m棵不相交的樹(shù)的集合(例如刪除A后的子樹(shù)個(gè)數(shù))雙親孩子兄弟堂兄弟祖先子孫——結(jié)點(diǎn)各子樹(shù)從左至右有序，不能互換（左為第一）——結(jié)點(diǎn)各子樹(shù)可互換位置。132.若干術(shù)語(yǔ)（續(xù)）——即樹(shù)的數(shù)據(jù)元素及其分支——結(jié)點(diǎn)掛接的子樹(shù)數(shù)（有幾個(gè)直接后繼就是幾度。）結(jié)點(diǎn)結(jié)點(diǎn)的度結(jié)點(diǎn)的層次終端結(jié)點(diǎn)分支結(jié)點(diǎn)樹(shù)的度樹(shù)的深度(或高度)ABCGEIDHFJMLK——從根到該結(jié)點(diǎn)的層數(shù)（根結(jié)點(diǎn)算第一層）——即度為0的結(jié)點(diǎn)，即葉子——即度不為0的結(jié)點(diǎn)（也稱(chēng)為內(nèi)部結(jié)點(diǎn)）——所有結(jié)點(diǎn)度中的最大值（Max{各結(jié)點(diǎn)的度}）——指所有結(jié)點(diǎn)中最大的層數(shù)（Max{各結(jié)點(diǎn)的層次}）問(wèn)：右上圖中的結(jié)點(diǎn)數(shù)＝；樹(shù)的度＝；樹(shù)的深度＝133414ABCDEFGHIJKLM結(jié)點(diǎn)A的度：3結(jié)點(diǎn)B的度：2結(jié)點(diǎn)M的度：0葉子：K，L，F(xiàn)，G，M，I，J結(jié)點(diǎn)A的孩子：B，C，D結(jié)點(diǎn)B的孩子：E，F(xiàn)結(jié)點(diǎn)I的雙親：D結(jié)點(diǎn)L的雙親：E結(jié)點(diǎn)B，C，D為兄弟結(jié)點(diǎn)K，L為兄弟樹(shù)的度：3結(jié)點(diǎn)A的層次：1結(jié)點(diǎn)M的層次：4樹(shù)的深度：4結(jié)點(diǎn)F，G為堂兄弟結(jié)點(diǎn)A是結(jié)點(diǎn)F，G的祖先153.樹(shù)的邏輯結(jié)構(gòu)

(特點(diǎn))：一對(duì)多（1:n），有多個(gè)直接后繼（如家譜樹(shù)、目錄樹(shù)等等），但只有一個(gè)根結(jié)點(diǎn)，且子樹(shù)之間互不相交。4.樹(shù)的存儲(chǔ)結(jié)構(gòu)

討論1：樹(shù)是非線性結(jié)構(gòu)，該怎樣存儲(chǔ)？————仍然有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)等方式。

16討論3：樹(shù)的鏈?zhǔn)酱鎯?chǔ)方案應(yīng)該怎樣制定？可規(guī)定為：從上至下、從左至右將樹(shù)的結(jié)點(diǎn)依次存入內(nèi)存。重大缺陷：復(fù)原困難（不能唯一復(fù)原就沒(méi)有實(shí)用價(jià)值）。討論2：樹(shù)的順序存儲(chǔ)方案應(yīng)該怎樣制定？可用多重鏈表：一個(gè)前驅(qū)指針，n個(gè)后繼指針。細(xì)節(jié)問(wèn)題：樹(shù)中結(jié)點(diǎn)的結(jié)構(gòu)類(lèi)型樣式該如何設(shè)計(jì)？

即應(yīng)該設(shè)計(jì)成“等長(zhǎng)”還是“不等長(zhǎng)”？缺點(diǎn)：等長(zhǎng)結(jié)構(gòu)太浪費(fèi)（每個(gè)結(jié)點(diǎn)的度不一定相同）；不等長(zhǎng)結(jié)構(gòu)太復(fù)雜（要定義好多種結(jié)構(gòu)類(lèi)型）。解決思路：先研究最簡(jiǎn)單、最有規(guī)律的樹(shù)狀結(jié)構(gòu)，然后設(shè)法把一般的樹(shù)轉(zhuǎn)化為簡(jiǎn)單樹(shù)。二叉樹(shù)175.樹(shù)的運(yùn)算

要明確：1.普通樹(shù)（即多叉樹(shù)）若不轉(zhuǎn)化為二叉樹(shù)，則運(yùn)算很難實(shí)現(xiàn)。2.二叉樹(shù)的運(yùn)算仍然是插入、刪除、修改、查找、排序等，但這些操作必須建立在對(duì)樹(shù)結(jié)點(diǎn)能夠“遍歷”的基礎(chǔ)上！（遍歷——指每個(gè)結(jié)點(diǎn)都被訪問(wèn)且僅訪問(wèn)一次，不遺漏不重復(fù)）。本章重點(diǎn)：二叉樹(shù)的定義、性質(zhì)、表示和實(shí)現(xiàn)18~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結(jié)構(gòu)樹(shù)型結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素(無(wú)前驅(qū))

根結(jié)點(diǎn)(無(wú)前驅(qū))最后一個(gè)數(shù)據(jù)元素(無(wú)后繼)多個(gè)葉子結(jié)點(diǎn)(無(wú)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、一個(gè)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、多個(gè)后繼)196.2二叉樹(shù)為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè)“叉”的樹(shù)？二叉樹(shù)的結(jié)構(gòu)最簡(jiǎn)單，規(guī)律性最強(qiáng)；可以證明，所有樹(shù)都能轉(zhuǎn)換為唯一的一棵二叉樹(shù)與其對(duì)應(yīng)，不失一般性。6.2.1二叉樹(shù)的定義6.2.2二叉樹(shù)的性質(zhì)6.2.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)（二叉樹(shù)的運(yùn)算見(jiàn)6.3節(jié)）206.2.1二叉樹(shù)的定義定義：是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合，由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的、分別稱(chēng)為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。邏輯結(jié)構(gòu)：

一對(duì)二（1：2）

基本特征:①每個(gè)結(jié)點(diǎn)最多可有兩棵子樹(shù)（不存在度大于2的結(jié)點(diǎn)）；②左子樹(shù)和右子樹(shù)次序不能顛倒（有序樹(shù)）。21二叉樹(shù)的五種基本形態(tài)：root空樹(shù)只含根結(jié)點(diǎn)rootrootrootLRR右子樹(shù)為空樹(shù)L左子樹(shù)為空樹(shù)左右子樹(shù)均不為空樹(shù)22二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型定義（見(jiàn)教材P121-122）ADTBinaryTree{數(shù)據(jù)對(duì)象D:數(shù)據(jù)關(guān)系R:基本操作P：}ADTBinaryTree若D=Φ，則R=Φ；若D≠Φ，則R={H}；存在二元關(guān)系：①root唯一//關(guān)于根的說(shuō)明②Dl∩Dr=Φ//關(guān)于子樹(shù)不相交的說(shuō)明③……//關(guān)于二元關(guān)系的說(shuō)明

④……

//關(guān)于左子樹(shù)和右子樹(shù)的說(shuō)明D是具有相同特性的數(shù)據(jù)元素的集合。//至少有20個(gè)23

二叉樹(shù)的主要基本操作：查找類(lèi)插入類(lèi)刪除類(lèi)24

Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);

PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());25

InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);26ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);276.2.2二叉樹(shù)的性質(zhì)(3+2)討論1：第i層的結(jié)點(diǎn)數(shù)至多是多少？

（利用二叉樹(shù)的特性可輕松求出）

性質(zhì)1:

在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i>0）。性質(zhì)2:

深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)（k>0）。2i-1個(gè)提問(wèn)：第i層上至少有

個(gè)結(jié)點(diǎn)？1討論2：深度為k的二叉樹(shù)，至多有多少個(gè)結(jié)點(diǎn)？

（利用二叉樹(shù)的特性可輕松求出）2k-1提問(wèn)：深度為k時(shí)至少有

個(gè)結(jié)點(diǎn)？k28討論3：二叉樹(shù)的葉子數(shù)n0和度為2的結(jié)點(diǎn)數(shù)n2之間有關(guān)系嗎？性質(zhì)3:

對(duì)于任何一棵二叉樹(shù)，若2度的結(jié)點(diǎn)數(shù)有n2個(gè)，則葉子數(shù)（n0）必定為n2＋1（即n0=n2+1）證明：∵二叉樹(shù)中全部結(jié)點(diǎn)數(shù)n＝n0+n1+n2(葉子數(shù)＋1度結(jié)點(diǎn)數(shù)＋2度結(jié)點(diǎn)數(shù))又∵二叉樹(shù)中全部結(jié)點(diǎn)數(shù)n＝B+1

(總分支數(shù)＋根結(jié)點(diǎn))（除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)必有且僅有一個(gè)直接前趨，即一個(gè)分支進(jìn)入）而

總分支數(shù)B=n1+2n2(1度結(jié)點(diǎn)必有1個(gè)直接后繼，2度結(jié)點(diǎn)必有2個(gè))三式聯(lián)立可得：

n0+n1+n2=

n1+2n2+1,即n0=n2+1實(shí)際意義：葉子數(shù)＝2度結(jié)點(diǎn)數(shù)＋1ABCGEIDHFJ29滿(mǎn)二叉樹(shù)：一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)。

（特點(diǎn)：每層都“充滿(mǎn)”了結(jié)點(diǎn)）完全二叉樹(shù)：深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿(mǎn)二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)。AOBCGEKDJFIHNML深度為4的滿(mǎn)二叉樹(shù)深度為4的完全二叉樹(shù)ABCGEIDHFJ為何要研究這兩種特殊形式？因?yàn)樗鼈冊(cè)陧樞虼鎯?chǔ)方式下可以復(fù)原！解釋?zhuān)和耆鏄?shù)的特點(diǎn)就是，只有最后一層葉子不滿(mǎn)，且全部集中在左邊。

這其實(shí)是順序二叉樹(shù)的含義。在圖論概念中的“完全二叉樹(shù)”是指n1=0的情況。303.深度為9的完全二叉樹(shù)中至少有

個(gè)結(jié)點(diǎn)。最多呢？

Ａ)２9Ｂ)２8Ｃ)９Ｄ)２9－12.深度為k的二叉樹(shù)的結(jié)點(diǎn)總數(shù)，最多為

個(gè)。

Ａ)２k-1Ｂ)log2kＣ)２k－１Ｄ)２k課堂練習(xí)：1.樹(shù)Ｔ中各結(jié)點(diǎn)的度的最大值稱(chēng)為樹(shù)Ｔ的

。

Ａ)高度Ｂ)層次Ｃ)深度Ｄ)度復(fù)習(xí)討論：①二叉樹(shù)是不是樹(shù)的特殊情況？答：不是！雖然二叉樹(shù)也屬于一種樹(shù)結(jié)構(gòu)，但它是另外單獨(dú)定義的一種樹(shù)狀結(jié)構(gòu)，并非一般樹(shù)的特例。它的子樹(shù)有順序規(guī)定，分為左子樹(shù)和右子樹(shù)。不能隨意顛倒。②：滿(mǎn)二叉樹(shù)和完全二叉樹(shù)有什么區(qū)別？答：滿(mǎn)二叉樹(shù)是每一層都是滿(mǎn)的二叉樹(shù)，而完全二叉樹(shù)雖然前n-1層是滿(mǎn)的，但最底層卻允許在右邊缺少連續(xù)若干個(gè)結(jié)點(diǎn)。滿(mǎn)二叉樹(shù)是完全二叉樹(shù)的一個(gè)特例。√√√31

性質(zhì)4：

具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2n+1證明：設(shè)完全二叉樹(shù)的深度為k則根據(jù)第二條性質(zhì)得2k-1≤n<2k

即k-1≤log2n<k

因?yàn)閗只能是整數(shù)，因此，k=log2n

+132課堂討論：?jiǎn)?設(shè)一棵完全二叉樹(shù)具有1000個(gè)結(jié)點(diǎn)，則它有

個(gè)葉子結(jié)點(diǎn)，有

個(gè)度為2的結(jié)點(diǎn)，有

個(gè)結(jié)點(diǎn)只有非空左子樹(shù)，有

個(gè)結(jié)點(diǎn)只有非空右子樹(shù)。48948810由于最后一層葉子數(shù)為489個(gè)，是奇數(shù)，說(shuō)明有1個(gè)結(jié)點(diǎn)只有非空左子樹(shù)；而完全二叉樹(shù)中不可能出現(xiàn)只有非空右子樹(shù)的結(jié)點(diǎn)(0個(gè))。答：易求出總層數(shù)和末層葉子數(shù)。總層數(shù)k=log2n＋1=10;且前9層總結(jié)點(diǎn)數(shù)為29-1=511

(完全二叉樹(shù)的前k-1層肯定是滿(mǎn)的)所以末層葉子數(shù)為1000-511=489個(gè)。33請(qǐng)注意葉子結(jié)點(diǎn)總數(shù)≠末層葉子數(shù)！還應(yīng)當(dāng)加上第k-1層（靠右邊）的0度結(jié)點(diǎn)個(gè)數(shù)。分析：k層的489個(gè)葉子的父結(jié)點(diǎn)占上層的245個(gè)結(jié)點(diǎn)（489/2)上層（k=9)右邊的0度結(jié)點(diǎn)數(shù)還有29-1-245=11個(gè)！另一法：可先求2度結(jié)點(diǎn)數(shù),再由此得到葉子總數(shù)。首先，k-2層的28-1（255）個(gè)結(jié)點(diǎn)肯定都是2度的（完全二叉）另外，末層葉子（剛才已求出為489）所對(duì)應(yīng)的雙親也是度＝2，（共有489/2＝244個(gè)）。所以，全部2度結(jié)點(diǎn)數(shù)為255(k-2層)＋244(k-1層)=499個(gè)；總?cè)~子數(shù)＝2度結(jié)點(diǎn)數(shù)＋1=500個(gè)。第i層上的滿(mǎn)結(jié)點(diǎn)數(shù)為2i-1所以，全部葉子數(shù)＝489(末層)＋11(k-1層)=500個(gè)。度為2的結(jié)點(diǎn)＝葉子總數(shù)－1=499個(gè)。34討論：完全二叉樹(shù)中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)編號(hào)之間有關(guān)系嗎？12345678910111213141535性質(zhì)5：若對(duì)含n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從上到下且從左至右進(jìn)行1至n的編號(hào)，則對(duì)完全二叉樹(shù)中任意一個(gè)編號(hào)為i的結(jié)點(diǎn)：

(1)若i=1，則該結(jié)點(diǎn)是二叉樹(shù)的根，無(wú)雙親；否則，編號(hào)為i/2的結(jié)點(diǎn)為其雙親結(jié)點(diǎn);

(2)若2i>n，則該結(jié)點(diǎn)無(wú)左孩子，

否則，編號(hào)為2i的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)；

(3)若2i+1>n，則該結(jié)點(diǎn)無(wú)右孩子結(jié)點(diǎn)，

否則，編號(hào)為2i+1的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。366.2.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)一、順序存儲(chǔ)結(jié)構(gòu)按二叉樹(shù)的結(jié)點(diǎn)“自上而下、從左至右”編號(hào)，用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)。ABCDEFGHI[1][2][3][4][5][6][7][8][9]ABCGEIDHF問(wèn)：順序存儲(chǔ)后能否復(fù)原成唯一對(duì)應(yīng)的二叉樹(shù)形狀？答：若是完全/滿(mǎn)二叉樹(shù)則可以做到唯一復(fù)原。而且有規(guī)律：下標(biāo)值為i的雙親，其左孩子的下標(biāo)值必為2i，其右孩子的下標(biāo)值必為2i＋1（即性質(zhì)5）例如，對(duì)應(yīng)[2]的兩個(gè)孩子必為[4]和[5],即B的左孩子必是D,右孩子必為E。T[0]這里沒(méi)用37#defineMAX_TREE_SIZE100

//二叉樹(shù)的最大結(jié)點(diǎn)數(shù)typedefTElemTypeSqBiTree[MAX_TREE_SIZE];

//0號(hào)單元存儲(chǔ)根結(jié)點(diǎn)SqBiTreebt;二叉樹(shù)的順序存儲(chǔ)表示38討論：不是完全二叉樹(shù)怎么辦？答：一律轉(zhuǎn)為完全二叉樹(shù)！方法很簡(jiǎn)單，將各層空缺處統(tǒng)統(tǒng)補(bǔ)上“虛結(jié)點(diǎn)”，其內(nèi)容為空。AB^C^^^D^…E[1][2][3][4][5][6][7][8][9].[16]ABECD缺點(diǎn)：①浪費(fèi)空間；②插入、刪除不便

39例如:

ABDCEF

012345678910111213ABCDEF140132640二、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

用二叉鏈表即可方便表示。dataleft_childright_childdataleft_childright_child1、二叉鏈表2、三叉鏈表3、線索鏈表一般從根結(jié)點(diǎn)開(kāi)始存儲(chǔ)。（相應(yīng)地，訪問(wèn)樹(shù)中結(jié)點(diǎn)時(shí)也只能從根開(kāi)始）注：如果需要倒查某結(jié)點(diǎn)的雙親，可以再增加一個(gè)雙親域（直接前趨）指針，將二叉鏈表變成三叉鏈表。41ADEBCFrootlchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):1.二叉鏈表ABDCEF42討論：有n個(gè)結(jié)點(diǎn)二叉樹(shù)的二叉鏈表有多少空鏈域？

解釋1:

2*n-（n-1）=n+1解釋2:

2*n0+n1=n0+n1+n2+1=n+1n+1個(gè)43typedefstructBiTNode{//結(jié)點(diǎn)結(jié)構(gòu)TElemTypedata;

structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;lchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):C語(yǔ)言的類(lèi)型描述如下:44rootADEBCF2．三叉鏈表parentlchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):ABDCEF45

typedefstructTriTNode{//結(jié)點(diǎn)結(jié)構(gòu)TElemTypedata;

structTriTNode*lchild,*rchild;//左右孩子指針

structTriTNode

*parent;//雙親指針

}TriTNode,*TriTree;parent

lchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):C語(yǔ)言的類(lèi)型描述如下:466.3遍歷二叉樹(shù)和線索二叉樹(shù)一、遍歷二叉樹(shù)（TraversingBinaryTree）遍歷定義——指按某條搜索路線遍訪每個(gè)結(jié)點(diǎn)且不重復(fù)（又稱(chēng)周游）。遍歷用途——它是樹(shù)結(jié)構(gòu)插入、刪除、修改、查找和排序運(yùn)算的前提，是二叉樹(shù)一切運(yùn)算的基礎(chǔ)和核心。

遍歷方法——牢記一種約定，對(duì)每個(gè)結(jié)點(diǎn)的查看都是“先左后右”。47遍歷規(guī)則———二叉樹(shù)由根、左子樹(shù)、右子樹(shù)構(gòu)成，定義為D、L、RD、L、R的組合定義了六種可能的遍歷方案：

DLR,LDR,LRD,DRL,RDL,RLD若限定先左后右，則有三種實(shí)現(xiàn)方案：

DLRLDRLRD先

(根)序遍歷中

(根)序遍歷后(根)序遍歷

注：“先、中、后”的意思是指訪問(wèn)的結(jié)點(diǎn)D是先于子樹(shù)出現(xiàn)還是后于子樹(shù)出現(xiàn)。DLR48例1：先序遍歷的結(jié)果是：中序遍歷的結(jié)果是：后序遍歷的結(jié)果是：ABCDEABDECDBEACDEBCA口訣：DLR—先序遍歷，即先根再左再右LDR—中序遍歷，即先左再根再右LRD—后序遍歷，即先左再右再根49+*A*/EDCB先序遍歷+**/ABCDE前綴表示中序遍歷A/B*C*D+E中綴表示后序遍歷AB/C*D*E+后綴表示層序遍歷+*E*D/CAB例2：用二叉樹(shù)表示算術(shù)表達(dá)式50二、遍歷的遞歸算法實(shí)現(xiàn)：用遞歸形式格外簡(jiǎn)單！voidPreorder(BiTreeT,

void(*visit)(TElemType&e)){//

先序遍歷二叉樹(shù)

if(T){

visit(T->data);//訪問(wèn)根結(jié)點(diǎn)Preorder(T->lchild,visit);//遍歷左子樹(shù)Preorder(T->rchild,visit);//遍歷右子樹(shù)

}}51先序遍歷算法DLR(tree*root){if(root!=NULL){

//非空二叉樹(shù)printf(“%d”,root->data);//訪問(wèn)DDLR(root->lchild);//遞歸遍歷左子樹(shù)DLR(root->rchild);//遞歸遍歷右子樹(shù)

}return(0);}中序遍歷算法LDR(tree*root){if(root!=NULL){

LDR(root->lchild);printf(“%d”,root->data);

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

{

LRD(root->lchild);LRD(root->rchild);printf(“%d”,root->data);}return(0);}結(jié)點(diǎn)數(shù)據(jù)類(lèi)型自定義typedefstructNode{intdata;structNode*lchild,*rchild；}tree;tree*root;

52三、對(duì)遍歷的分析：1.從前面的三種遍歷算法可以知道：如果將print語(yǔ)句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說(shuō)這三種遍歷算法的訪問(wèn)路徑是相同的，只是訪問(wèn)結(jié)點(diǎn)的時(shí)機(jī)不同。從虛線的出發(fā)點(diǎn)到終點(diǎn)的路徑上，每個(gè)結(jié)點(diǎn)經(jīng)過(guò)3次。AFEDCBG第1次經(jīng)過(guò)時(shí)訪問(wèn)＝先序遍歷第2次經(jīng)過(guò)時(shí)訪問(wèn)＝中序遍歷第3次經(jīng)過(guò)時(shí)訪問(wèn)＝后序遍歷2.二叉樹(shù)遍歷的時(shí)間效率和空間效率時(shí)間效率:O(n)//每個(gè)結(jié)點(diǎn)只訪問(wèn)一次空間效率:O(n)//棧占用的最大輔助空間（精確值：樹(shù)深為k的遞歸遍歷需要k+1個(gè)輔助單元！）53ADBCDLRADLRDLR>B>>D>>CDLR先序遍歷序列：ABDC先序遍歷:54ADBCLDRBLDRLDR>A>>D>>CLDR中序遍歷序列：BDAC中序遍歷:55ADBCLRDLRDLRD>A>>D>>CLRD后序遍歷序列：DBCA后序遍歷:B56ABCDEFGHK復(fù)習(xí)回顧：先序序列：中序序列：后序序列：A

BCD

EFGHKBDC

A

EHGKFDCBHKGFE

Alchild

data

rchildparent

lchild

data

rchild57voidPreorder(BiTreeT,

void(*visit)(TElemType&e)){//

先序遍歷二叉樹(shù)

if(T){

visit(T->data);//訪問(wèn)根結(jié)點(diǎn)Preorder(T->lchild,visit);//遍歷左子樹(shù)Preorder(T->rchild,visit);//遍歷右子樹(shù)

}}58voidpre(BiTreeT){if(T){printf("%d\t",T->data);pre(T->L);pre(T->R);}}主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(TR);先序序列：ABDC59四、遍歷二叉樹(shù)的非遞歸實(shí)現(xiàn)：中序遍歷的非遞歸實(shí)現(xiàn)：1、結(jié)點(diǎn)（初始時(shí)是根結(jié)點(diǎn)）進(jìn)棧，沿左指針查找左孩子。2、若有左孩子，返回第一步。3、若無(wú)左孩子，判棧空？空則結(jié)束。非空，棧頂結(jié)點(diǎn)出棧訪問(wèn)。轉(zhuǎn)向右子樹(shù)，返回1。例如:BCDELAXW中序：B、L、E、A、C、W、X、DStatusInOrderTraverse(BiTreet,Visit){initstack(s);push(s,t);//t是根結(jié)點(diǎn)while(!stackempty(s)){while(Gettop(s,p))&&p)//有值且非空時(shí)push(s,p->lchild)；//null值可能進(jìn)棧pop(s,p);//空指針退棧if(!stackempty(s))//訪問(wèn)結(jié)點(diǎn)，向右一步{pop(s,p);visit(p->data);push(s,p->rchild);}}//WhilereturnOK;}//InOrderTraverseStatusInOrderTraverse(BiTreet,Visit){initstack(s);p=T;while(p||!StackEmpty(s)){if(p){push(s,p)；p=p->lchild;}//根指針進(jìn)棧，遍歷左子樹(shù)else{//根指針退棧，訪問(wèn)根結(jié)點(diǎn)，遍歷右子樹(shù)pop(s,p);if(!Visit(p->data))returnERROR;p=p->rchild;}}returnOK;}//InOrderTraverse中序非遞歸算法演示ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B訪問(wèn)：C(4)61pABCDEFGiP->A訪問(wèn)：CB(5)ABCDEFGiP->AP->D訪問(wèn)：CBp(6)ABCDEFGiP->AP->DP->E訪問(wèn)：CBp(7)ABCDEFGiP->AP->D訪問(wèn)：CBEp(8)62ABCDEFGiP->AP->DP->G訪問(wèn)：CBEP=NULL(9)ABCDEFGiP->A訪問(wèn)：CBEGDp(11)ABCDEFGiP->AP->F訪問(wèn)：CBEGDp(12)ABCDEFGiP->AP->D訪問(wèn)：CBEGp(10)63ABCDEFGiP->A訪問(wèn)：CBEGDFp=NULL(13)ABCDEFGi訪問(wèn)：CBEGDFAp(14)ABCDEFGi訪問(wèn)：CBEGDFAp=NULL(15)64五、建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)不同的定義方法相應(yīng)有不同的存儲(chǔ)結(jié)構(gòu)的建立算法65

以字符串的形式“根左子樹(shù)右子樹(shù)”定義一棵二叉樹(shù)例如:以空白字符“”表示ABCDA(B(,C(,)),D(,))空樹(shù)只含一個(gè)根結(jié)點(diǎn)的二叉樹(shù)A以字符串“A”表示以下列字符串表示66Status

CreateBiTree(BiTree&T)

{scanf(&ch);

if(ch=='')T=NULL;

else{

if(!(T=newBiTNode))

exit(OVERFLOW);T->data=ch;//生成根結(jié)點(diǎn)

CreateBiTree(T->lchild);//構(gòu)造左子樹(shù)

CreateBiTree(T->rchild);//構(gòu)造右子樹(shù)

}

returnOK;

}//CreateBiTree67AB

C

D

ABCD上頁(yè)算法執(zhí)行過(guò)程舉例如下:ATBCD^^^^^scanf(&ch);if(ch=='')T=NULL;else{

if(!(T=newBiTNode))

exit(OVERFLOW);T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);68六、遍歷算法的應(yīng)用舉例2、統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)3、求二叉樹(shù)的深度(后序遍歷)4、復(fù)制二叉樹(shù)(后序遍歷)5、建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)1、查詢(xún)二叉樹(shù)中某個(gè)結(jié)點(diǎn)691)在二叉樹(shù)不空的前提下,和根結(jié)點(diǎn)的元素進(jìn)行比較,若相等,則找到返回TRUE;2)否則在左子樹(shù)中進(jìn)行查找,若找到,則返回TRUE;3)否則繼續(xù)在右子樹(shù)中進(jìn)行查找,若找到,則返回TRUE,否則返回FALSE;1、查詢(xún)二叉樹(shù)中某個(gè)結(jié)點(diǎn)StatusPreorder(BiTreeT,ElemTypex,BiTree&p){//若二叉樹(shù)中存在和x相同的元素，則p指向該結(jié)點(diǎn)并返回OK,否則返回FALSE

}if(T){

if(T->data==x){p=T;returnOK,}

}//if

elsereturnFALSE;else{

if(Preorder(T->lchild,x,p)

returnOK;

else

return(Preorder(T->rchild,x,p));}//else702、統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)算法基本思想:先序(或中序或后序)遍歷二叉樹(shù)，在遍歷過(guò)程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。由此，需在遍歷算法中增添一個(gè)“計(jì)數(shù)”的參數(shù)，并將算法中“訪問(wèn)結(jié)點(diǎn)”的操作改為:若是葉子，則計(jì)數(shù)器增1。void

CountLeaf(BiTreeT,int&count){

if(T){

if((!T->lchild)&&(!T->rchild))count++;

//對(duì)葉子結(jié)點(diǎn)計(jì)數(shù)

CountLeaf(T->lchild,count);

CountLeaf(T->rchild,count);

}//if}//CountLeafint

CountLeaf(BiTreeT){//返回指針T所指二叉樹(shù)中所有葉子結(jié)點(diǎn)個(gè)數(shù)

if(!T)return0;if(!T->lchild&&!T->rchild)return1;else{

m=CountLeaf(T->lchild);

n=CountLeaf(T->rchild);

return(m+n);}//else}//CountLeafintCount

(BiTreeT){//返回指針T所指二叉樹(shù)中所有結(jié)點(diǎn)個(gè)數(shù)if(!T)return0;if(!T->lchild&&!T->rchild)return1;else{

m=Count

(T->lchild);

n=Count

(T->rchild);

return(m+n+1);}//else}//CountLeaf713、求二叉樹(shù)的深度(后序遍歷)算法基本思想:首先分析二叉樹(shù)的深度和它的左、右子樹(shù)深度之間的關(guān)系。

從二叉樹(shù)深度的定義可知，二叉樹(shù)的深度應(yīng)為其左、右子樹(shù)深度的最大值加1。由此，需先分別求得左、右子樹(shù)的深度，算法中訪問(wèn)結(jié)點(diǎn)的操作為:求得左、右子樹(shù)深度的最大值，然后加1。int

Depth(BiTreeT){

//返回二叉樹(shù)的深度

if(!T)depthval=0;else{depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);

depthval=1+(depthLeft>depthRight?depthLeft:depthRight);

}

returndepthval;}voidDepth(BiTreeT,intlevel,int&dval){

if(T){if(level>dval)dval=level;

Depth(T->lchild,level+1,dval);

Depth(T->rchild,level+1,dval);}}//調(diào)用之前l(fā)evel的初值為1,dval的初值為0.724、復(fù)制二叉樹(shù)(后序遍歷)其基本操作為:生成一個(gè)結(jié)點(diǎn)。根元素NEWT左子樹(shù)右子樹(shù)根元素T左子樹(shù)右子樹(shù)左子樹(shù)右子樹(shù)ABCDEFGHK^D^C^^H^^K^GAnewTF^^BE^73BiTNode*GetTreeNode(TElemTypeitem,BiTNode*lptr,BiTNode*rptr){

if(!(T=newBiTNode))exit(1);

T->data=item;T->lchild=lptr;T->rchild=rptr;returnT;}生成一個(gè)二叉樹(shù)的結(jié)點(diǎn)(其數(shù)據(jù)域?yàn)閕tem,左指針域?yàn)閘ptr,右指針域?yàn)閞ptr)BiTNode*CopyTree(BiTNode*T){if(!T)returnNULL;if(T->lchild)newlptr=CopyTree(T->lchild);//復(fù)制左子樹(shù)elsenewlptr=NULL;if(T->rchild)newrptr=CopyTree(T->rchild);//復(fù)制右子樹(shù)elsenewrptr=NULL;newT=GetTreeNode(T->data,newlptr,newrptr);returnnewT;}//CopyTree745、建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)不同的定義方法相應(yīng)有不同的存儲(chǔ)結(jié)構(gòu)的建立算法(1)以字符串的形式“根-左子樹(shù)-右子樹(shù)”定義一棵二叉樹(shù)例如:A(B(,C(,)),D(,))ABCD以下列字符串表示以空白字符“”表示空樹(shù)只含一個(gè)根結(jié)點(diǎn)的二叉樹(shù)A以字符串“A”表示75StatusCreateBiTree(BiTree&T){scanf(&ch);if(ch=='')T=NULL;else{if(!(T=newBiTNode))exit(OVERFLOW);T->data=ch;//生成根結(jié)點(diǎn)

CreateBiTree(T->lchild);//構(gòu)造左子樹(shù)

CreateBiTree(T->rchild);//構(gòu)造右子樹(shù)}returnOK;}//CreateBiTreeATBCD^^^^^scanf(&ch);if(ch=='')T=NULL;else{

if(!(T=newBiTNode))exit(OVERFLOW);T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}AB

C

D

ABCD76(2)按給定的表達(dá)式建相應(yīng)二叉樹(shù)由先綴表示式建樹(shù).

例如：已知表達(dá)式的先綴表示式:-×+abc/de由原表達(dá)式建樹(shù).

例如：已知表達(dá)式:(a+b)×c–d/e對(duì)應(yīng)先綴表達(dá)式-×+abc/de的二叉樹(shù)abcde-×+/特點(diǎn)：操作數(shù)為葉子結(jié)點(diǎn),運(yùn)算符為分支結(jié)點(diǎn)scanf(&ch);if(In(ch,字母集))建葉子結(jié)點(diǎn);else{建根結(jié)點(diǎn);遞歸建左子樹(shù);遞歸建右子樹(shù);}由先綴表示式建樹(shù)的算法的基本操作：77a+b(a+b)×c–d/ea+b×c分析表達(dá)式和二叉樹(shù)的關(guān)系:abba×c+abc(a+b)×c/deabc×+++×-78基本操作:scanf(&ch);if(In(ch,字母集)){建葉子結(jié)點(diǎn);暫存;}elseif(In(ch,運(yùn)算符集)){和前一個(gè)運(yùn)算符比較優(yōu)先數(shù);若當(dāng)前的優(yōu)先數(shù)“高”，則暫存;否則建子樹(shù);}79voidCrtExptree(BiTree&T,charexp[]){InitStack(S);Push(S,#);InitStack(PTR);p=exp;ch=*p;while(!(GetTop(S)==#&&ch==#)){

if(!IN(ch,OP))CrtNode(t,ch);//建葉子結(jié)點(diǎn)并入棧else{

switch(ch){ case(:Push(S,ch);break; case):Pop(S,c); while(c!=(){CrtSubtree(t,c);Pop(S,c)} break; defult:while(!Gettop(S,c)&&(precede(c,ch))){

CrtSubtree(t,c);Pop(S,c); } if(ch!=#)Push(S,ch);break;

}//switch

}

if(ch!=#){p++;ch=*p;}}//whilePop(PTR,T);}//CrtExptree80建葉子結(jié)點(diǎn)的算法為：voidCrtNode(BiTree&T,charch){if(!(T=newBiTNode))exit(OVERFLOW);T->data=char;T->lchild=T->rchild=NULL;Push(PTR,T);}建子樹(shù)的算法為：voidCrtSubtree(Bitree&T,charc){if(!(T=newBiTNode))exit(OVERFLOW);T->data=c;Pop(PTR,rc);T->rchild=rc;Pop(PTR,lc);T->lchild=lc;Push(PTR,T);}81

僅知二叉樹(shù)的先序序列“abcdefg”不能唯一確定一棵二叉樹(shù)，如果同時(shí)已知二叉樹(shù)的中序序列“cbdaegf”,則會(huì)如何？

(3)由二叉樹(shù)的先序和中序序列建樹(shù)二叉樹(shù)的先序序列二叉樹(shù)的中序序列左子樹(shù)左子樹(shù)右子樹(shù)右子樹(shù)根根82abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列83voidCrtBT(BiTree&T,charpre[],charino[],intps,intis,intn){//已知pre[ps..ps+n-1]為二叉樹(shù)的先序序列，ins[is..is+n-1]為二叉樹(shù)的中序//序列，本算法由此兩個(gè)序列構(gòu)造二叉鏈表

if(n==0)T=NULL;else{k=Search(ino,pre[ps]);//在中序序列中查詢(xún)if(k==-1)T=NULL;else{ if(!(T=newBiTNode))exit(OVERFLOW); T->data=pre[ps]; if(k==is)T->Lchild=NULL; elseCrtBT(T->Lchild,pre[],ino[],ps+1,is,k-is); if(k=is+n-1)T->Rchild=NULL; elseCrtBT(T->Rchild,pre[],ino[],ps+1+(k-is),k+1,n-(k-is)-1);}}//}//CrtBT84討論：1.求二叉樹(shù)深度，或從x結(jié)點(diǎn)開(kāi)始的子樹(shù)深度。

算法思路：只查各結(jié)點(diǎn)后繼鏈表指針，若左(右)孩子的左(右)指針?lè)强眨瑒t層次數(shù)加1；否則函數(shù)返回。技巧：遞歸時(shí)應(yīng)當(dāng)從葉子開(kāi)始向上計(jì)數(shù)，層深者保留。否則不易確定層數(shù)。2.按層次輸出二叉樹(shù)中所有結(jié)點(diǎn)。

算法思路：既然要求從上到下，從左到右，則利用隊(duì)列存放各子樹(shù)結(jié)點(diǎn)的指針是個(gè)好辦法，而不必拘泥于遞歸算法。技巧：當(dāng)根結(jié)點(diǎn)入隊(duì)后，令其左、右孩子結(jié)點(diǎn)入隊(duì)，而左孩子出隊(duì)時(shí)又令它的左右孩子結(jié)點(diǎn)入隊(duì)，……由此便可產(chǎn)生按層次輸出的效果。3中序遍歷的非遞歸(迭代)算法算法思路：若不用遞歸，則要實(shí)現(xiàn)二叉樹(shù)遍歷的“嵌套”規(guī)則，必用堆棧。可直接用while語(yǔ)句和push/pop操作。參見(jiàn)教材P130-131程序。4.判別給定二叉樹(shù)是否為完全二叉樹(shù)（即順序二叉樹(shù)）。

算法思路：完全二叉樹(shù)的特點(diǎn)是：沒(méi)有左子樹(shù)空而右子樹(shù)單獨(dú)存在的情況(前k-1層都是滿(mǎn)的，且第k層左邊也滿(mǎn)）。技巧:按層序遍歷方式，先把所有結(jié)點(diǎn)（不管當(dāng)前結(jié)點(diǎn)是否有左右孩子）都入隊(duì)列.若為完全二叉樹(shù),則層序遍歷時(shí)得到的肯定是一個(gè)連續(xù)的不包含空指針的序列.如果序列中出現(xiàn)了空指針，則說(shuō)明不是完全二叉樹(shù)。856.3.2線索二叉樹(shù)線索二叉樹(shù)的相關(guān)概念線索二叉樹(shù)的遍歷算法二叉樹(shù)如何線索化？86一、線索二叉樹(shù)的相關(guān)概念遍歷二叉樹(shù)最終求得結(jié)點(diǎn)的一個(gè)線性序列。其實(shí)質(zhì)是：非線性結(jié)構(gòu)—>線性結(jié)構(gòu)。

ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA87普通二叉樹(shù)只能找到結(jié)點(diǎn)的左右孩子信息，而該結(jié)點(diǎn)的直接前驅(qū)和直接后繼只能在遍歷過(guò)程中獲得。若將遍歷后對(duì)應(yīng)的有關(guān)前驅(qū)和后繼預(yù)存起來(lái)，則從第一個(gè)結(jié)點(diǎn)開(kāi)始就能很快“順藤摸瓜”而遍歷整個(gè)樹(shù)了。兩種解決方法增加兩個(gè)域：fwd和bwd；利用空鏈域（n+1個(gè)空鏈域）存放前驅(qū)指針存放后繼指針如何預(yù)存這類(lèi)信息？可能是根、或最左（右）葉子88指向該線性序列中的“前驅(qū)”和“后繼”的指針，稱(chēng)作“線索”與其相應(yīng)的二叉樹(shù)，稱(chēng)作“線索二叉樹(shù)”包含“線索”的存儲(chǔ)結(jié)構(gòu)，稱(chēng)作“線索鏈表”ABCDEFGHK^D^

C^^B

E^89規(guī)定：1）若結(jié)點(diǎn)有左子樹(shù)，則lchild指向其左孩子；否則，lchild指向其直接前驅(qū)(即線索)；2）若結(jié)點(diǎn)有右子樹(shù)，則rchild指向其右孩子；否則，rchild指向其直接后繼(即線索)。為了避免混淆，增加兩個(gè)標(biāo)志域，如下圖所示：lchildLTagdataRTagrchild約定:當(dāng)Tag域?yàn)?時(shí),表示正常情況，即為指針Link;當(dāng)Tag域?yàn)?時(shí),表示線索情況，即為線索Thread注：在線索化二叉樹(shù)中，并不是每個(gè)結(jié)點(diǎn)都能直接找到其后繼的，當(dāng)標(biāo)志為0時(shí)，則需要通過(guò)一定運(yùn)算才能找到它的后繼。

線索鏈表：用前頁(yè)結(jié)點(diǎn)結(jié)構(gòu)所構(gòu)成的二叉鏈表線索：指向結(jié)點(diǎn)前驅(qū)和后繼的指針線索二叉樹(shù)：加上線索的二叉樹(shù)（后面圖形式樣）線索化：對(duì)二叉樹(shù)以某種次序遍歷使其變?yōu)榫€索二叉樹(shù)的過(guò)程90ABCGEIDHFroot懸空？懸空？解：該二叉樹(shù)中序遍歷結(jié)果為:

H,D,I,B,E,A,F,C,

G所以添加線索應(yīng)當(dāng)按如下路徑進(jìn)行：例：畫(huà)出以下二叉樹(shù)對(duì)應(yīng)的中序線索二叉樹(shù)。為避免懸空態(tài)，應(yīng)增設(shè)一個(gè)頭結(jié)點(diǎn)91對(duì)應(yīng)的中序線索二叉樹(shù)存儲(chǔ)結(jié)構(gòu)如圖所示：00A00C00B11E11F11G00D11I11H注：此圖中序遍歷結(jié)果為:H,

D,I,B,E,A,F,C,

G0--root192typedefstruct

BiThrNode{

TElemTypedata;

structBiThrNode*lchild,*rchild;//左右指針

PointerTagLTag,RTag;//左右標(biāo)志}BiThrNode,*BiThrTree;線索鏈表的類(lèi)型描述：

typedef

enumPointerTag{

Link,Thread};

//Link==0:指針，Thread==1:線索93二、線索二叉樹(shù)的遍歷算法:

for(p=

FirstNode(T);p;p=Next(p))Visit(p);由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息，從而簡(jiǎn)化了遍歷的算法。94例如:對(duì)中序線索二叉樹(shù)的遍歷算法

※中序遍歷的第一個(gè)結(jié)點(diǎn)？

※在中序線索化鏈表中結(jié)點(diǎn)的后繼？左子樹(shù)上處于“最左下”（沒(méi)有左子樹(shù)）的結(jié)點(diǎn)（線索鏈表中該結(jié)點(diǎn)有何特點(diǎn)？）若無(wú)右子樹(shù)，則為后繼線索所指結(jié)點(diǎn)否則為對(duì)其右子樹(shù)進(jìn)行中序遍歷時(shí)訪問(wèn)的第一個(gè)結(jié)點(diǎn)95StatusInOrderTraverse_Thr(BiThrTreeT,

Status(*Visit)(TElemTypee)){p=T->lchild;//p指向根結(jié)點(diǎn)

while(p!=T){

//空樹(shù)或遍歷結(jié)束時(shí)，p==Twhile(p->LTag==Link)p=p->lchild;//第一個(gè)結(jié)點(diǎn)

Visit(p->data);while(p->RTag==Thread&&p->rchild!=T){p=p->rchild;Visit(p->data);//訪問(wèn)后繼結(jié)點(diǎn)

}p=p->rchild;//p進(jìn)至其后繼或右子樹(shù)根

}}//InOrderTraverse_Thr96由于線索化的實(shí)質(zhì)是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索，而前驅(qū)或后繼的信息只有在遍歷時(shí)才能得到，因此線索化的過(guò)程即為在遍歷的過(guò)程中修改空指針的過(guò)程。三、二叉樹(shù)如何線索化？97如何實(shí)現(xiàn)？以中序線索化為例需要記下遍歷過(guò)程中訪問(wèn)結(jié)點(diǎn)的先后順序。遍歷過(guò)程中，附設(shè)指針pre,并始終保持指針pre指向當(dāng)前訪問(wèn)的、指針p所指結(jié)點(diǎn)的前驅(qū)。98void

InThreading(BiThrTreep,BiThrNode*&pre)

{

if(p){//對(duì)以p為根的非空二叉樹(shù)進(jìn)行線索化

InThreading(p->lchild,pre);

//左子樹(shù)線索化

if(!p->lchild)//建前驅(qū)線索

{p->LTag=Thread;p->lchild=pre;}

if(!pre->rchild)//建后繼線索

{pre->RTag=Thread;pre->rchild=p;}

pre=p;//保持pre指向p的前驅(qū)

InThreading(p->rchild,pre);

//右子樹(shù)線索化

}//if}//InThreading99StatusInOrderThreading(BiThrTree&Thrt,

BiThrTreeT){//構(gòu)建中序線索鏈表if(!(Thrt=newBiThrNode))

exit(OVERFLOW);

Thrt->LTag=Link;Thrt->RTag=Thread;Thrt->rchild=Thrt;

//添加頭結(jié)點(diǎn)returnOK;}//InOrderThreading

……100if(!T)

Thrt->lchild=Thrt;

//若二叉樹(shù)空，則左指針回指else{Thrt->lchild=T;

pre=Thrt;InThreading(T,pre);

//中序遍歷并線索化

pre->rchild=Thrt;//處理最后一個(gè)結(jié)點(diǎn)pre->RTag=Thread;

Thrt->rchild=pre;

}101二叉樹(shù)小結(jié)1、定義和性質(zhì)2、存儲(chǔ)結(jié)構(gòu)3、遍歷4、線索化：線索樹(shù)順序結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)二叉鏈表三叉鏈表先序線索樹(shù)中序線索樹(shù)后序線索樹(shù)樹(shù)二叉樹(shù)森林中序遍歷后序遍歷先序遍歷赫夫曼樹(shù)赫夫曼編碼1026.4樹(shù)和森林6.4.1樹(shù)的存儲(chǔ)結(jié)構(gòu)6.4.2樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換6.4.3樹(shù)和森林的遍歷1036.4.1樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)有三種常用存儲(chǔ)方式：①雙親表示法②孩子表示法③孩子兄弟表示法1、用雙親表示法來(lái)存儲(chǔ)思路：用一組連續(xù)空間來(lái)存儲(chǔ)樹(shù)的結(jié)點(diǎn)，同時(shí)在每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指示器，指示其雙親結(jié)點(diǎn)在鏈表中的位置。parentsdata結(jié)點(diǎn)結(jié)構(gòu)dataparents1樹(shù)結(jié)構(gòu)23n104ABCGEIDHF缺點(diǎn)：求結(jié)點(diǎn)的孩子時(shí)需要遍歷整個(gè)結(jié)構(gòu)。01234567812233ABCDEFGHI-1001例1:雙親表示法105

typedefstructPTNode{Elemdata;

intparent;//雙親位置域

}PTNode;

dataparent#defineMAX_TREE_SIZE100結(jié)點(diǎn)結(jié)構(gòu):C語(yǔ)言的類(lèi)型描述:106typedefstruct{

PTNodenodes[MAX_TREE_SIZE];

intr,n;//根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù)

}PTree;樹(shù)結(jié)構(gòu):107思路一：多重鏈表第一種結(jié)點(diǎn)結(jié)構(gòu)：同構(gòu)的結(jié)點(diǎn)結(jié)構(gòu)？有n個(gè)結(jié)點(diǎn)度為k的樹(shù)種有nk-（n-1）個(gè)空鏈域第二種結(jié)點(diǎn)結(jié)構(gòu)：異構(gòu)的結(jié)點(diǎn)結(jié)構(gòu)思路二：將每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來(lái)，形成一個(gè)孩子鏈表，則n個(gè)結(jié)點(diǎn)要設(shè)立n個(gè)孩子鏈表； 每個(gè)孩子鏈表再設(shè)一個(gè)頭結(jié)點(diǎn)，用于存放雙親和表頭指針，這些頭結(jié)點(diǎn)可以用數(shù)組存放起來(lái)，這樣就形成一個(gè)混合結(jié)構(gòu)。2、用孩子表示法來(lái)存儲(chǔ)108typedefstructCTNode{

intchild;

structCTNode*nextchild;}*ChildPtr;孩子結(jié)點(diǎn)結(jié)構(gòu):

childnextchildC語(yǔ)言的類(lèi)型描述:109

typedefstruct{ElemTypedata;ChildPtrfirstchild;//孩子鏈的頭指針

}CTBox;孩子鏈表頭結(jié)點(diǎn)(雙親結(jié)點(diǎn)結(jié)構(gòu))

datafirstchild110typedefstruct{CTBoxnodes[MAX_TREE_SIZE];

intn,r;//結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置

}CTree;樹(shù)結(jié)構(gòu):111r=0n=6datafirstchildABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

4645123孩子鏈表表示法示例:-1000224112思路：用二叉鏈表來(lái)表示樹(shù)，但鏈表中的兩個(gè)指針域含義不同。左指針指向該結(jié)點(diǎn)的第一個(gè)孩子；右指針指向該結(jié)點(diǎn)的下一個(gè)兄弟結(jié)點(diǎn)。nextsiblingdatafirstchild3、用孩子兄弟表示法來(lái)存儲(chǔ)指向左孩子指向右兄弟113typedefstructCSNode{Elemdata;

structCSNode

*firstchild,*nextsibling;}CSNode,*CSTree;C語(yǔ)言的類(lèi)型描述:結(jié)點(diǎn)結(jié)構(gòu):

firstchilddatanextsibling114abecdfhgbacedfgh設(shè)問(wèn)：樹(shù)轉(zhuǎn)二叉樹(shù)的“連線—抹線—旋轉(zhuǎn)”如何由計(jì)算機(jī)自動(dòng)實(shí)現(xiàn)？例如：1156.4.2樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換樹(shù)和二叉樹(shù)如何互相轉(zhuǎn)換？森林和二叉樹(shù)如何互相轉(zhuǎn)換？116樹(shù)與二叉樹(shù)轉(zhuǎn)換ACBED樹(shù)ABCDE二叉樹(shù)A^^BC^D^^E^A^^BC^D^^E^A^^BC^D^^E^對(duì)應(yīng)存儲(chǔ)存儲(chǔ)解釋解釋117轉(zhuǎn)換步驟：step1:將樹(shù)中同一結(jié)點(diǎn)的孩子（兄弟）相連;step2:保留結(jié)點(diǎn)的最左孩子連線，刪除其它孩子連線；step3:將同一孩子的連線繞左孩子旋轉(zhuǎn)45度角。加線抹線旋轉(zhuǎn)討論1：樹(shù)如何轉(zhuǎn)為二叉樹(shù)？118將樹(shù)轉(zhuǎn)換成二叉樹(shù)加線：在兄弟之間加一連線抹線：對(duì)每個(gè)結(jié)點(diǎn)，除了其左孩子外，去除其與其余孩子之間的關(guān)