第6章樹與二叉樹

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

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

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

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

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

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

基本操作：查找類插入類刪除類6

Root(T)//求樹的根結(jié)點

查找類：Value(T,cur_e)//求當前結(jié)點的元素值

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

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

ClearTree(&T)//將樹清空

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

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

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

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

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

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

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

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

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

一對二（1：2）

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

④……

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

二叉樹的主要基本操作：查找類插入類刪除類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二叉樹的性質(zhì)(3+2)討論1：第i層的結(jié)點數(shù)至多是多少？

（利用二叉樹的特性可輕松求出）

性質(zhì)1:

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

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

個結(jié)點？1討論2：深度為k的二叉樹，至多有多少個結(jié)點？

（利用二叉樹的特性可輕松求出）2k-1提問：深度為k時至少有

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

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

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

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

n0+n1+n2=

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

（特點：每層都“充滿”了結(jié)點）完全二叉樹：深度為k的，有n個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)。AOBCGEKDJFIHNML深度為4的滿二叉樹深度為4的完全二叉樹ABCGEIDHFJ為何要研究這兩種特殊形式？因為它們在順序存儲方式下可以復原！解釋：完全二叉樹的特點就是，只有最后一層葉子不滿，且全部集中在左邊。

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

個結(jié)點。最多呢？

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

個。

Ａ)２k-1Ｂ)log2kＣ)２k－１Ｄ)２k課堂練習：1.樹Ｔ中各結(jié)點的度的最大值稱為樹Ｔ的

。

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

性質(zhì)4：

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

即k-1≤log2n<k

因為k只能是整數(shù)，因此，k=log2n

+132課堂討論：問:設(shè)一棵完全二叉樹具有1000個結(jié)點，則它有

個葉子結(jié)點，有

個度為2的結(jié)點，有

個結(jié)點只有非空左子樹，有

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

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

(1)若i=1，則該結(jié)點是二叉樹的根，無雙親；否則，編號為i/2的結(jié)點為其雙親結(jié)點;

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

否則，編號為2i的結(jié)點為其左孩子結(jié)點；

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

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

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

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

39例如:

ABDCEF

012345678910111213ABCDEF140132640二、鏈式存儲結(jié)構(gòu)

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

解釋1:

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

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

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

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

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

structTriTNode

*parent;//雙親指針

}TriTNode,*TriTree;parent

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

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

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

DLRLDRLRD先

(根)序遍歷中

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

注：“先、中、后”的意思是指訪問的結(jié)點D是先于子樹出現(xiàn)還是后于子樹出現(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ù)表達式50二、遍歷的遞歸算法實現(xiàn)：用遞歸形式格外簡單！voidPreorder(BiTreeT,

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

先序遍歷二叉樹

if(T){

visit(T->data);//訪問根結(jié)點Preorder(T->lchild,visit);//遍歷左子樹Preorder(T->rchild,visit);//遍歷右子樹

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

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

}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é)點數(shù)據(jù)類型自定義typedefstructNode{intdata;structNode*lchild,*rchild；}tree;tree*root;

52三、對遍歷的分析：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個輔助單元?。?3ADBCDLRADLRDLR>B>>D>>CDLR先序遍歷序列：ABDC先序遍歷:54ADBCLDRBLDRLDR>A>>D>>CLDR中序遍歷序列：BDAC中序遍歷:55ADBCLRDLRDLRD>A>>D>>CLRD后序遍歷序列：DBCA后序遍歷:B56ABCDEFGHK復習回顧：先序序列：中序序列：后序序列：A

BCD

EFGHKBDC

A

EHGKFDCBHKGFE

Alchild

data

rchildparent

lchild

data

rchild57voidPreorder(BiTreeT,

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

先序遍歷二叉樹

if(T){

visit(T->data);//訪問根結(jié)點Preorder(T->lchild,visit);//遍歷左子樹Preorder(T->rchild,visit);//遍歷右子樹

}}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四、遍歷二叉樹的非遞歸實現(xiàn)：中序遍歷的非遞歸實現(xiàn)：1、結(jié)點（初始時是根結(jié)點）進棧，沿左指針查找左孩子。2、若有左孩子，返回第一步。3、若無左孩子，判?？?？空則結(jié)束。非空，棧頂結(jié)點出棧訪問。轉(zhuǎn)向右子樹，返回1。例如:BCDELAXW中序：B、L、E、A、C、W、X、DStatusInOrderTraverse(BiTreet,Visit){initstack(s);push(s,t);//t是根結(jié)點while(!stackempty(s)){while(Gettop(s,p))&&p)//有值且非空時push(s,p->lchild)；//null值可能進棧pop(s,p);//空指針退棧if(!stackempty(s))//訪問結(jié)點，向右一步{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;}//根指針進棧，遍歷左子樹else{//根指針退棧，訪問根結(jié)點，遍歷右子樹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訪問：C(4)61pABCDEFGiP->A訪問：CB(5)ABCDEFGiP->AP->D訪問：CBp(6)ABCDEFGiP->AP->DP->E訪問：CBp(7)ABCDEFGiP->AP->D訪問：CBEp(8)62ABCDEFGiP->AP->DP->G訪問：CBEP=NULL(9)ABCDEFGiP->A訪問：CBEGDp(11)ABCDEFGiP->AP->F訪問：CBEGDp(12)ABCDEFGiP->AP->D訪問：CBEGp(10)63ABCDEFGiP->A訪問：CBEGDFp=NULL(13)ABCDEFGi訪問：CBEGDFAp(14)ABCDEFGi訪問：CBEGDFAp=NULL(15)64五、建立二叉樹的存儲結(jié)構(gòu)不同的定義方法相應(yīng)有不同的存儲結(jié)構(gòu)的建立算法65

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

CreateBiTree(BiTree&T)

{scanf(&ch);

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

else{

if(!(T=newBiTNode))

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

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

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

}

returnOK;

}//CreateBiTree67AB

C

D

ABCD上頁算法執(zhí)行過程舉例如下: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)計二叉樹中葉子結(jié)點的個數(shù)3、求二叉樹的深度(后序遍歷)4、復制二叉樹(后序遍歷)5、建立二叉樹的存儲結(jié)構(gòu)1、查詢二叉樹中某個結(jié)點691)在二叉樹不空的前提下,和根結(jié)點的元素進行比較,若相等,則找到返回TRUE;2)否則在左子樹中進行查找,若找到,則返回TRUE;3)否則繼續(xù)在右子樹中進行查找,若找到,則返回TRUE,否則返回FALSE;1、查詢二叉樹中某個結(jié)點StatusPreorder(BiTreeT,ElemTypex,BiTree&p){//若二叉樹中存在和x相同的元素，則p指向該結(jié)點并返回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)計二叉樹中葉子結(jié)點的個數(shù)算法基本思想:先序(或中序或后序)遍歷二叉樹，在遍歷過程中查找葉子結(jié)點，并計數(shù)。由此，需在遍歷算法中增添一個“計數(shù)”的參數(shù)，并將算法中“訪問結(jié)點”的操作改為:若是葉子，則計數(shù)器增1。void

CountLeaf(BiTreeT,int&count){

if(T){

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

//對葉子結(jié)點計數(shù)

CountLeaf(T->lchild,count);

CountLeaf(T->rchild,count);

}//if}//CountLeafint

CountLeaf(BiTreeT){//返回指針T所指二叉樹中所有葉子結(jié)點個數(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所指二叉樹中所有結(jié)點個數(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、求二叉樹的深度(后序遍歷)算法基本思想:首先分析二叉樹的深度和它的左、右子樹深度之間的關(guān)系。

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

Depth(BiTreeT){

//返回二叉樹的深度

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、復制二叉樹(后序遍歷)其基本操作為:生成一個結(jié)點。根元素NEWT左子樹右子樹根元素T左子樹右子樹左子樹右子樹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;}生成一個二叉樹的結(jié)點(其數(shù)據(jù)域為item,左指針域為lptr,右指針域為rptr)BiTNode*CopyTree(BiTNode*T){if(!T)returnNULL;if(T->lchild)newlptr=CopyTree(T->lchild);//復制左子樹elsenewlptr=NULL;if(T->rchild)newrptr=CopyTree(T->rchild);//復制右子樹elsenewrptr=NULL;newT=GetTreeNode(T->data,newlptr,newrptr);returnnewT;}//CopyTree745、建立二叉樹的存儲結(jié)構(gòu)不同的定義方法相應(yīng)有不同的存儲結(jié)構(gòu)的建立算法(1)以字符串的形式“根-左子樹-右子樹”定義一棵二叉樹例如:A(B(,C(,)),D(,))ABCD以下列字符串表示以空白字符“”表示空樹只含一個根結(jié)點的二叉樹A以字符串“A”表示75StatusCreateBiTree(BiTree&T){scanf(&ch);if(ch=='')T=NULL;else{if(!(T=newBiTNode))exit(OVERFLOW);T->data=ch;//生成根結(jié)點

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

CreateBiTree(T->rchild);//構(gòu)造右子樹}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)按給定的表達式建相應(yīng)二叉樹由先綴表示式建樹.

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

例如：已知表達式:(a+b)×c–d/e對應(yīng)先綴表達式-×+abc/de的二叉樹abcde-×+/特點：操作數(shù)為葉子結(jié)點,運算符為分支結(jié)點scanf(&ch);if(In(ch,字母集))建葉子結(jié)點;else{建根結(jié)點;遞歸建左子樹;遞歸建右子樹;}由先綴表示式建樹的算法的基本操作：77a+b(a+b)×c–d/ea+b×c分析表達式和二叉樹的關(guān)系:abba×c+abc(a+b)×c/deabc×+++×-78基本操作:scanf(&ch);if(In(ch,字母集)){建葉子結(jié)點;暫存;}elseif(In(ch,運算符集)){和前一個運算符比較優(yōu)先數(shù);若當前的優(yōu)先數(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é)點并入棧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é)點的算法為：voidCrtNode(BiTree&T,charch){if(!(T=newBiTNode))exit(OVERFLOW);T->data=char;T->lchild=T->rchild=NULL;Push(PTR,T);}建子樹的算法為：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

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

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

if(n==0)T=NULL;else{k=Search(ino,pre[ps]);//在中序序列中查詢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.求二叉樹深度，或從x結(jié)點開始的子樹深度。

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

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

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

ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

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

C^^B

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

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

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

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

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

G0--root192typedefstruct

BiThrNode{

TElemTypedata;

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

PointerTagLTag,RTag;//左右標志}BiThrNode,*BiThrTree;線索鏈表的類型描述：

typedef

enumPointerTag{

Link,Thread};

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

for(p=

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

※中序遍歷的第一個結(jié)點？

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

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

while(p!=T){

//空樹或遍歷結(jié)束時，p==Twhile(p->LTag==Link)p=p->lchild;//第一個結(jié)點

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

}p=p->rchild;//p進至其后繼或右子樹根

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

InThreading(BiThrTreep,BiThrNode*&pre)

{

if(p){//對以p為根的非空二叉樹進行線索化

InThreading(p->lchild,pre);

//左子樹線索化

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);

//右子樹線索化

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

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

exit(OVERFLOW);

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

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

……100if(!T)

Thrt->lchild=Thrt;

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

pre=Thrt;InThreading(T,pre);

//中序遍歷并線索化

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

Thrt->rchild=pre;

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

typedefstructPTNode{Elemdata;

intparent;//雙親位置域

}PTNode;

dataparent#defineMAX_TREE_SIZE100結(jié)點結(jié)構(gòu):C語言的類型描述:106typedefstruct{

PTNodenodes[MAX_TREE_SIZE];

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

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

intchild;

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

childnextchildC語言的類型描述:109

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

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

datafirstchild110typedefstruct{CTBoxnodes[MAX_TREE_SIZE];

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

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

A

-11

B

02

C

03

D

04

E

25

F

26

G

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

structCSNode

*firstchild,*nextsibling;}CSNode,*CSTree;C語言的類型描述:結(jié)點結(jié)構(gòu):

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