數(shù)據(jù)結(jié)構(gòu)之樹和二叉樹課件

第六章樹和二叉樹第六章樹和二叉樹16.1樹的類型定義6.2二叉樹的類型定義6.3

二叉樹的存儲結(jié)構(gòu)6.4二叉樹的遍歷6.5線索二叉樹6.6樹和森林的表示方法6.7樹和森林的遍歷6.8哈夫曼樹與哈夫曼編碼6.1樹的類型定義6.2二叉樹的類型定義6.3二叉樹的26.1樹的類型定義6.13數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。

若D為空集，則稱為空樹。否則:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root；(2)當n>1時，其余結(jié)點可分為m(m>0)個互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定義的樹，稱為根root的子樹。

數(shù)據(jù)關(guān)系R：數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。若D4

基本操作：查找類

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

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())//遍歷Root(T)//求樹的根結(jié)點查找類：Val6InitTree(&T)//初始化置空樹

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

ClearTree(&T)//將樹清空

刪除類：DestroyTree(&T)//銷毀樹的結(jié)構(gòu)DeleteChild(&T,&p,i)//刪除結(jié)點p的第i棵子樹ClearTree(&T)//將樹清空刪除類：De81、樹（Tree)：是n個結(jié)點的有限集（n>=0)。在任意一棵非空樹中，有且僅有一個特定的稱為根的結(jié)點（root)；當n>1時，其余結(jié)點可分為m（m>0)個互不相交的有限集T1,T2,…,Tm,其中每個集合Ti本身又是一棵符合本定義的樹，并且稱為根root的子樹。1、樹（Tree)：是n個結(jié)點的有限集（n>=0)。在任意一9(１)有確定的根；(２)樹根和子樹根之間為有向關(guān)系。有向樹：有序樹：樹中結(jié)點的各子樹之間的先后次序是有意義的，不能互換，否則就成為另一棵樹了。子樹之間存在確定的次序關(guān)系。無序樹：樹中結(jié)點的各子樹之間的先后次序無意義，可以互換。子樹之間不存在確定的次序關(guān)系。(１)有確定的根；有向樹：有序樹：樹中結(jié)點的各子樹之間的先10ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2樹根例如:ABCDEFGHIJMKLA(B(E,F(K,L)),11樹的示意圖：根結(jié)點根結(jié)點葉結(jié)點分支結(jié)點子樹子樹子樹Level1Level2Level3Level4結(jié)點的層次樹的示意圖：根結(jié)點根結(jié)點葉結(jié)點分支結(jié)點子樹子樹子樹Level12對比樹型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點對比樹型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點13~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結(jié)構(gòu)樹型結(jié)構(gòu)第一個數(shù)據(jù)元素(無前驅(qū))

根結(jié)點(無前驅(qū))最后一個數(shù)據(jù)元素(無后繼)多個葉子結(jié)點(無后繼)其它數(shù)據(jù)元素(一個前驅(qū)、一個后繼)其它數(shù)據(jù)元素(一個前驅(qū)、多個后繼)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~14基本術(shù)語基本術(shù)語151、結(jié)點:2、結(jié)點的度:3、樹的度:4、葉子結(jié)點:5、分支結(jié)點:數(shù)據(jù)元素+若干指向子樹的分支分支的個數(shù)樹中所有結(jié)點的度的最大值度為零的結(jié)點度大于零的結(jié)點DHIJM（終端結(jié)點）（非終端結(jié)點）1、結(jié)點:2、結(jié)點的度:3、樹的度:4、葉子結(jié)點:5、分支結(jié)166、(從根到結(jié)點的)路徑：7、孩子結(jié)點、雙親結(jié)點兄弟結(jié)點、堂兄弟結(jié)點祖先結(jié)點、子孫結(jié)點8、結(jié)點的層次:9、樹的深度：

由從根到該結(jié)點所經(jīng)分支和結(jié)點構(gòu)成ABCDEFGHIJMKL假設(shè)根結(jié)點的層次為1，依次加1樹中葉子結(jié)點所在的最大層次6、(從根到結(jié)點的)路徑：7、孩子結(jié)點、雙親結(jié)點8、結(jié)點的層17任何一棵非空樹是一個二元組Tree=（root，F(xiàn)）其中：root被稱為根結(jié)點F被稱為子樹森林10、森林：是m（m≥0）棵互不相交的樹的集合。ArootBCDEFGHIJMKLF任何一棵非空樹是一個二元組10、森林：是m（m≥0）棵互Ar186.2

二叉樹的類型定義二叉樹是樹的基礎(chǔ)，一般的樹可以轉(zhuǎn)化為二叉樹來處理。6.219

1、二叉樹的定義：

二叉樹或為空樹，或是由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成（即左、右子樹次序不能顛倒）。ABCDEFGHK根結(jié)點左子樹右子樹1、二叉樹的定義：二叉樹或為空樹，或是由一個根結(jié)點加202、二叉樹的五種基本形態(tài)：N空樹只含根結(jié)點NNNLRR右子樹為空樹L左子樹為空樹左右子樹均不為空樹2、二叉樹的五種基本形態(tài)：N空樹只含根結(jié)點NNNLRR右子樹21

二叉樹的主要基本操作：查找類插入類刪除類二叉樹的主要基本操作：查找類插入類刪除22

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());Root(T);Value(T,e);23

InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);InitBiTree(&T);24ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);ClearBiTree(&T);25二叉樹

的重要特性二叉樹

的重要特性26

性質(zhì)1：

在二叉樹的第i層上至多有2i-1個結(jié)點。(i≥1)用歸納法證明：

歸納基：

歸納假設(shè)：

歸納證明：i=1

層時，只有一個根結(jié)點：

2i-1=20=1；假設(shè)對所有的j，1≤j

i，命題成立；由歸納假設(shè)知：第I-1層上至多有2i-2個結(jié)點。又因為二叉樹上每個結(jié)點至多有兩棵子樹，則第i層的結(jié)點數(shù)=2i-22=2i-1

。性質(zhì)1：在二叉樹的第i層上至多有27性質(zhì)2：

深度為k的二叉樹上至多有2k-1個結(jié)點（k≥1）。證明：[證明用求等比數(shù)列前k項和的公式]基于上一條性質(zhì)，深度為k的二叉樹上的結(jié)點數(shù)至多為

20+21+

+2k-1=2k-1。性質(zhì)2：

深度為k的二叉樹上至多有2k-128

性質(zhì)3：

對任何一棵二叉樹，若它含有n0個葉子結(jié)點、n2個度為2的結(jié)點，則必存在關(guān)系式：n0=n2+1。證明：設(shè)二叉樹上結(jié)點總數(shù)n=n0+n1+n2又二叉樹上分支總數(shù)b=n0*0+n1+2n2

而b=n-1=n0+n1+n2-1由此，n0=n2+1。性質(zhì)3：

對任何一棵二叉樹，若它含有n0個葉子29兩類特殊形態(tài)的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個結(jié)點的二叉樹。完全二叉樹：樹中所含的n個結(jié)點和滿二叉樹中編號為1至n的結(jié)點一一對應(yīng)。123456789101112131415abcdefghij兩類特殊形態(tài)的二叉樹：滿二叉樹：指的是深度為k且含有2k-130

性質(zhì)4：

具有n個結(jié)點的完全二叉樹的深度為log2n+1。證明：設(shè)完全二叉樹的深度為k，則由性質(zhì)2和完全二叉樹的定義知：深度為k-1的二叉樹應(yīng)該是一棵滿二叉樹，故結(jié)點數(shù)為2k-1-1；深度為k的完全二叉樹當為滿二叉樹時結(jié)點數(shù)最多為2k–1。所以得2k-1-1

<n≤2k–1

2k-1≤n<2k

即k-1≤log2n<k因為k只能是整數(shù)，因此，k=log2n

+1。性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為31性質(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é)點。性質(zhì)5：若對含n個結(jié)點的完全二叉樹從上到下且從左至右321、完全二叉樹第3層有2個葉子，則該二叉樹有多少個結(jié)點？分析：第3層最多有23-1=4個結(jié)點。完全二叉樹只有3層，則前2層為滿二叉樹，結(jié)點數(shù)為22-1=3個結(jié)點，故總結(jié)點數(shù)=3+2=5；完全二叉樹含有4層，則前3層為滿二叉樹，結(jié)點數(shù)為23-1=7個結(jié)點。又第3層上結(jié)點數(shù)為4，由題知其中兩個為葉子，則其它（4-2）=2個結(jié)點應(yīng)為內(nèi)部結(jié)點。由完全二叉樹的定義知：這兩個結(jié)點中有一個結(jié)點的度可以為1或2，而其它結(jié)點的度必為2。綜上：總結(jié)點數(shù)=7+1+（2-1）*2=10或總結(jié)點數(shù)=7+2*2=11。練習(xí)：1、完全二叉樹第3層有2個葉子，則該二叉樹有多少個結(jié)點？練習(xí)33作業(yè)已知二叉樹有50個葉子結(jié)點，則該二叉樹的總結(jié)點數(shù)至少應(yīng)有多少個？任意一個有n個結(jié)點的二叉樹，已知它有m個葉子結(jié)點，試證明非葉子結(jié)點中有（m-1）個結(jié)點的度為2，其余度為1。含n個結(jié)點的完全三叉樹的高度為多少？完全二叉樹第7層有10個葉子，問該二叉樹共有多少個結(jié)點？作業(yè)已知二叉樹有50個葉子結(jié)點，則該二叉樹的總結(jié)點數(shù)至少應(yīng)346.3二叉樹的存儲結(jié)構(gòu)二、二叉樹的鏈式存儲表示一、二叉樹的順序存儲表示6.3二、二叉樹的鏈式存儲表示一、二叉樹的順序存儲表示35（適合存儲完全二叉樹）即用一組地址連續(xù)的存儲單元集資從上至下，從左至右存儲完全二叉樹上的結(jié)點元素。也就是說，將完全二叉樹上編號為i的結(jié)點存放在數(shù)組下標為（i-1)的分量中。若要存儲一棵一般的二叉樹，結(jié)點的存放應(yīng)與完全二叉樹上的結(jié)點對照，存儲在數(shù)組的相應(yīng)分量中。用“0”表示不存在該結(jié)點。可能會浪費很多存儲空間，單支樹就是一個極端情況。一、二叉樹的順序存儲表示（適合存儲完全二叉樹）一、二叉樹的順序存儲表示36完全二叉樹的數(shù)組表示一般二叉樹的數(shù)組表示數(shù)組表示完全二叉樹的數(shù)組表示一般二叉樹的數(shù)組表示數(shù)組表示37#defineMAX_TREE_SIZE100//二叉樹的最大結(jié)點數(shù)typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0號單元存儲根結(jié)點SqBiTreebt;C語言描述#defineMAX_TREE_SIZE10038ADEBCFrootlchilddatarchild結(jié)點結(jié)構(gòu)1.二叉鏈表二、二叉樹的順序存儲表示ADEBCFrootlchilddata39typedefstruct

BiTNode

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

structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;lchilddatarchild結(jié)點結(jié)構(gòu):C語言描述:typedefstructBiTNode{//結(jié)點40ADEBCFroot2．三叉鏈表parent

lchilddatarchild結(jié)點結(jié)構(gòu)ADEBCFroot2．三叉鏈表parent41

typedefstruct

TriTNode

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

structTriTNode

*parent;//雙親指針

structTriTNode*lchild,;//左孩子指針TElemTypedata;

structTriTNode*rchild;//右孩子指針

}TriTNode,*TriTree;parentlchilddatarchild結(jié)點結(jié)構(gòu):C語言的類型描述如下:typedefstructTriTNode{42二叉樹鏈表表示的示例二叉樹鏈表表示的示例436.4二叉樹的遍歷6.444一、遍歷的概念二、先左后右的遍歷算法三、算法的遞歸描述四、遍歷算法的應(yīng)用舉例一、遍歷的概念二、先左后右的遍歷算法三、算法的遞歸描述四、遍45

按照某種順序不重復(fù)地訪問二叉樹中的所有結(jié)點。此處的訪問可以是輸出、修改等操作，根據(jù)實際需要而定。

使得每個結(jié)點均被訪問一次，而且僅被訪問一次?！霸L問”的含義可以很廣，如：輸出結(jié)點的信息。一、遍歷的概念按照某種順序不重復(fù)地訪問二叉樹中的所有結(jié)點。此處的46

“遍歷”是任何類型均有的操作，對線性結(jié)構(gòu)而言，只有一條搜索路徑(因為每個結(jié)點均只有一個后繼)，故不需要另加討論。而二叉樹是非線性結(jié)構(gòu)，每個結(jié)點有兩個后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。“遍歷”是任何類型均有的操作，47對“二叉樹”而言，可以有兩條搜索路徑：1．先上后下的按層次遍歷；2．先左（子樹）后右（子樹）的遍歷；對“二叉樹”而言，可以有兩條搜索路徑：1．先上后48二、先左后右的遍歷算法先（根）序的遍歷算法中（根）序的遍歷算法后（根）序的遍歷算法二、先左后右的遍歷算法先（根）序的遍歷算法中（根）序的遍歷算49

若二叉樹為空樹，則空操作；否則，（1）訪問根結(jié)點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。遍歷結(jié)果-+a*b-cd/ef先（根）序的遍歷算法：若二叉樹為空樹，則空操作；否則，先（根）序的遍歷算法：50voidPreorder(BiTreeT){if(T){//如果樹不為空visit(T->data);//輸出根結(jié)點Preorder(T->lchild);//先序遍歷左子樹Preorder(T->rchild);//先序遍歷右子樹}}先序voidPreorder(BiTree51

若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結(jié)點；（3）中序遍歷右子樹。遍歷結(jié)果

a+b*c-d-e/f中（根）序的遍歷算法：若二叉樹為空樹，則空操作；否則，中（根）序的遍歷算法：52voidInorder(BiTreeT){if(T){//如果樹不為空Inorder(T->lchild);//先序遍歷左子樹

visit(T->data);//輸出根結(jié)點Inorder(T->rchild);//先序遍歷右子樹}}中序voidInorder(BiTree53

若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點。后（根）序的遍歷算法：遍歷結(jié)果abcd-*+ef/-若二叉樹為空樹，則空操作；否則，后（根）序的遍歷算法：遍54voidPastorder(BiTreeT){if(T){//如果樹不為空

Pastorder(T->lchild);//先序遍歷左子樹

visit(T->data);//輸出根結(jié)點Pastorder(T->rchild);//先序遍歷右子樹}}后序voidPastorder(BiTree55二、遍歷算法的應(yīng)用舉例1、統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)(先序遍歷)2、求二叉樹的深度(后序遍歷)3、建立二叉樹的存儲結(jié)構(gòu)4、求二叉樹的結(jié)點個數(shù)二、遍歷算法的應(yīng)用舉例1、統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)2、求二561、統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)算法基本思想:分別求出左子樹、右子樹的葉子數(shù)，然后相加。1、統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)算法基本思想:分別求出左子57void

CountLeaf

(BiTreeT){if(!T)return0;elseif((!T->lchild)&&(!T->rchild))return1;else{nl=CountLeaf(T->lchild);nr=CountLeaf(T->rchild);returnnl+nr;

}//if}//CountLeafvoidCountLeaf(BiTreeT)582、求二叉樹的深度(后序遍歷)算法基本思想:從二叉樹深度的定義可知，二叉樹的深度應(yīng)為其左、右子樹深度的最大值加1。由此，需先分別求得左、右子樹的深度，算法中“訪問結(jié)點”的操作為：求得左、右子樹深度的最大值，然后加1。

首先分析二叉樹的深度和它的左、右子樹深度之間的關(guān)系。2、求二叉樹的深度(后序遍歷)算法基本思想:從二叉樹深59int

Depth(BiTreeT){//返回二叉樹的深度

if(!T)return0;else{dl=Depth(T->lchild);dr=Depth(T->rchild);

dep=1+(dl>dr?dl:dr);

}

return

dep;}intDepth(BiTreeT){//返回二叉603建立二叉樹的存儲結(jié)構(gòu)不同的定義方法相應(yīng)有不同的存儲結(jié)構(gòu)的建立算法3建立二叉樹的存儲結(jié)構(gòu)不同的定義方法相應(yīng)有不同的存儲結(jié)構(gòu)的建61

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

CreateBiTree(BiTree&T)

{scanf(&ch);

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

else{

if(!(T=(BiTree)malloc(sizeof(BiTNode))))

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

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

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

}

returnOK;}//CreateBiTreestatusCreateBiTree(BiTree&T)63AB

C

D

ABCD上頁算法執(zhí)行過程舉例如下：ATBCD^^^^^ABCDABCD上頁644、求二叉樹的結(jié)點個數(shù)IntNodeCount(BiTreeT){if(!T)return0;else{nl=NodeCount(T->lchild);nr=NodeCount(T->rchild);returnnl+nr+1;}}4、求二叉樹的結(jié)點個數(shù)IntNodeCount(BiTre65

僅知二叉樹的先序序列“abcdefg”

不能唯一確定一棵二叉樹，由二叉樹的先序和中序序列建樹

如果同時已知二叉樹的中序序列“cbdaegf”，則會如何？

二叉樹的先序序列二叉樹的中序序列左子樹左子樹右子樹右子樹根根僅知二叉樹的先序序列“abcdefg”不能唯一確定66主要思想：先序序列中第一個為“根”，標出之；在中序序列中標出“根”，并分出左、右子樹；在先序序列中標出左、右子樹；分別對左、右子樹重復(fù)以上步驟。主要思想：67abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列abcdefgcbda68由二叉樹的后序和中序序列建樹二叉樹的后序序列二叉樹的中序序列左子樹右子樹根左子樹右子樹根主要思想：后序序列中第一個為“根”，標出之；在中序序列中標出“根”，并分出左、右子樹；在后序序列中標出左、右子樹；分別對左、右子樹重復(fù)以上步驟。由二叉樹的后序和中序序列建樹二叉樹的后序序列二叉樹的中序序列69由二叉樹的后序和先序序列能否建樹？二叉樹的后序序列二叉樹的先序序列左子樹右子樹根左子樹右子樹根結(jié)論：不能唯一確定二叉樹！ABAB或例：先序：AB后序：BA由二叉樹的后序和先序序列能否建樹？二叉樹的后序序列二叉樹的先70練習(xí)：先序：ABDEGCFH

中序：DBGEAFHC中序：DBGEAFHC

后序：DGEBHFCA畫出二叉樹，并寫出后序序列。畫出二叉樹，并寫出先序序列。練習(xí)：畫出二叉樹，并寫出后序序列。畫出二叉樹，并寫出先序序列71證明：在含有n個結(jié)點的二叉樹中，含有n+1個空指針。Proof:設(shè)二叉樹中度為0、1、2的結(jié)點數(shù)分別為n0,n1,n2，即n=n0+n1+n2由于二叉樹中的空指針數(shù)=2n0+n1+0=n0+n0+n1由性質(zhì)3知：n0=n2+1所以空指針數(shù)=n2+1+n0+n1=n+1

證畢。證明：在含有n個結(jié)點的二叉樹中，含有n+1個空指針。Proo726.5

線索二叉樹

何謂線索二叉樹？線索鏈表的遍歷算法如何建立線索鏈表？6.5

線索二叉樹何謂線索二叉樹？73一、何謂線索二叉樹？是要借助含有n個結(jié)點的二叉樹中(n+1)個空指針域，作為線索，直接指向遍歷序列中“前驅(qū)”或“后繼”結(jié)點。ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA一、何謂線索二叉樹？是要借助含有n個結(jié)點的二叉樹中(n+1)74指向該線性序列中的“前驅(qū)”和“后繼”的指針，稱作“線索”與其相應(yīng)的二叉樹，稱作“線索二叉樹”包含“線索”的存儲結(jié)構(gòu)，稱作“線索鏈表”ABCDEFGHK^D^

C^^B

E^指向該線性序列中的“前驅(qū)”和“后繼”的指針，稱作“線索751、對線索鏈表中結(jié)點的約定：在二叉鏈表的結(jié)點中增加兩個標志域，并作如下規(guī)定：若該結(jié)點的左子樹不空，則Lchild域的指針指向其左子樹，且左標志域的值為“指針Link=0”；否則，Lchild域的指針指向其“前驅(qū)”，且左標志的值為“線索Thread=1”

。1、對線索鏈表中結(jié)點的約定：在二叉鏈表的結(jié)點中增加兩個76若該結(jié)點的右子樹不空，則rchild域的指針指向其右子樹，且右標志域的值為“指針Link=0”；否則，rchild域的指針指向其“后繼”，且右標志的值為“線索Thread=1”。

如此定義的二叉樹的存儲結(jié)構(gòu)稱作“線索鏈表”。若該結(jié)點的右子樹不空，如此定義的二叉樹的存儲結(jié)構(gòu)稱作“線索鏈77typedefstruct

BiThrNod{

TElemTypedata;

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

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

typedef

enum{

Link,Thread

}PointerThr;

//Link==0:指針，Thread==1:線索typedefstructBiThrNod2、線索鏈表78二、線索鏈表的遍歷算法:

for(p=

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

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

※在中序線索化鏈表中結(jié)點的后繼？左子樹上處于“最左下”（沒有左子樹）的結(jié)點。若無右子樹，則為后繼線索所指結(jié)點；否則為對其右子樹進行中序遍歷時訪問的第一個結(jié)點。例如:對中序線索化鏈表的遍歷算法※中序遍歷的第一80voidInOrder(BiThrTreeT,void(*Visit)(TElemTypee)){p=T->lchild;//p指向根結(jié)點

while(p!=T){

//空樹或遍歷結(jié)束時，p==Twhile(p->LTag==Link)p=p->lchild;//第一個結(jié)點while(p->RTag==Thread&&p->rchild!=T)

{//為右線索時找其右線索p=p->rchild;Visit(p->data);//訪問后繼結(jié)點

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

}}

//InOrdervoidInOrder(BiThrTreeT,void81三、如何建立線索鏈表？ABDEGCFH中序遍歷序列：DBEGAFHCNULLNULL方法：在遍歷過程中修改空指針或先寫出遍歷序列，標出空指針，對照再畫出線索。三、如何建立線索鏈表？ABDEGCFH中序遍歷序列：DB82

6.6樹和森林的表示方法6.6樹和森林83樹的三種存儲結(jié)構(gòu)一、雙親表示法二、孩子鏈表表示法三、樹的二叉鏈表(孩子-兄弟）存儲表示法樹的三種存儲結(jié)構(gòu)一、雙親表示法二、孩子鏈表表示法三、樹的二叉84一、雙親表示法:1、定義：用一組地址連續(xù)的空間存儲樹的結(jié)點，同時在每個結(jié)點中附設(shè)一個指示器指示雙親結(jié)點在鏈表中的位置。（即：保存結(jié)點信息和雙親的下標）一、雙親表示法:1、定義：用一組地址連續(xù)的空間存儲樹的結(jié)點，85ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5r=0n=7dataparent2、特點：求雙親簡便，求孩子麻煩。ABCDEFG0A-1r=0datap86

typedefstructPTNode{ElemTypedata;

intparent;//雙親位置域

}PTNode;

dataparent#defineMAX_TREE_SIZE100結(jié)點結(jié)構(gòu):3、C語言的類型描述:typedefstructPTNode{dat87typedefstruct{PTNodenodes[MAX_TREE_SIZE];

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

}PTree;樹結(jié)構(gòu):typedefstruct{樹結(jié)構(gòu):88二、孩子鏈表表示法:1、定義：把每個結(jié)點的孩子結(jié)點鏈成單鏈表。2、特點：求孩子方便，求雙親麻煩。二、孩子鏈表表示法:1、定義：把每個結(jié)點的孩子結(jié)點鏈成單鏈表89ABCDEFG0

A1

B2

C3

D4

E5

F6

Gr=0n=7datafirstchild123456孩子鏈表表示法ABCDEFG0Ar=0datafirstchi90ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5r=0n=7dataparentfirstchild123456-10002243、可能把孩子鏈表表示法和雙親表示法結(jié)合起來。ABCDEFG0A-1r=0dataparen91typedefstructCTNode{

intchild;

structCTNode*next;

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

childnext4、C語言的類型描述:typedefstructCTNode{孩子結(jié)點結(jié)構(gòu):92

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

}CTBox;雙親結(jié)點結(jié)構(gòu)

datafirstchildtypedefstruct{雙親結(jié)點結(jié)構(gòu)data93typedefstruct{CTBoxnodes[MAX_TREE_SIZE];

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

}CTree;樹結(jié)構(gòu):typedefstruct{樹結(jié)構(gòu):94三、樹的二叉鏈表(孩子-兄弟）存儲表示法1、定義：鏈表中結(jié)點的兩個鏈域分別指向該結(jié)點的第一個孩子結(jié)點和下一個兄弟結(jié)點。2、結(jié)點結(jié)構(gòu)：firstchilddatanextsibling第一個孩子下一個兄弟三、樹的二叉鏈表(孩子-兄弟）存儲表示法1、定義：鏈表中結(jié)95ABCDEFGABCEDFGrootABCEDFG

ABCDEFGAroot96typedefstructCSNode{TElemTypedata;

structCSNode

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

firstchilddatanextsiblingtypedefstructCSNode{3、C語言的類型97四、樹和二叉樹的轉(zhuǎn)換1、轉(zhuǎn)換規(guī)則樹的根樹的第一個孩子右兄弟二叉樹的根左孩子右孩子注：由樹轉(zhuǎn)換得到的二叉樹的右子樹永遠為空！四、樹和二叉樹的轉(zhuǎn)換1、轉(zhuǎn)換規(guī)則二叉樹的根左孩子右孩子注：98五、森林和二叉樹的轉(zhuǎn)換1、規(guī)則：森林中第一棵樹的根變成二叉樹的根森林中其它樹的根當成第一棵樹的根的兄弟把森林中每棵樹都轉(zhuǎn)化成相應(yīng)的二叉樹注：由森林轉(zhuǎn)換得到的二叉樹的右子樹可能不為空！五、森林和二叉樹的轉(zhuǎn)換1、規(guī)則：注：由森林轉(zhuǎn)換得到的二叉樹99ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI1006.7樹和森林的遍歷6.7101一、樹的遍歷二、森林的遍歷一、樹的遍歷二、森林的遍歷102ABCDEFGHIJK一、樹的遍歷把樹看成兩部分：1。樹的根2。根的子樹森林12A一、樹的遍歷12103樹的遍歷可有三條搜索路徑:按層次遍歷:先根(次序)遍歷:后根(次序)遍歷:若樹不空，則先訪問根結(jié)點，然后依次先根遍歷各棵子樹。若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點。若樹不空，則自上而下自左至右訪問樹中每個結(jié)點。1、22、1樹的遍歷可有三條搜索路徑:按層次遍歷:先根(次序)遍歷:后根104ABCDEFGHIJK先根遍歷時頂點的訪問次序：ABEFCDGHIJK后根遍歷時頂點的訪問次序：EFBCIJKHGDA層次遍歷時頂點的訪問次序：ABCDEFGHIJKA先根遍歷時頂點的訪問次105

BCDEFGHIJK森林中第一棵樹的根結(jié)點；森林中第一棵樹的子樹森林；森林中其它樹構(gòu)成的森林。森林由三部分構(gòu)成：二、森林的遍歷123森林中第一棵樹的根結(jié)點；森林中第一棵1061.先序遍歷若森林不空，則訪問森林中第一棵樹的根結(jié)點；先序遍歷森林中第一棵樹的子樹森林；先序遍歷森林中(除第一棵樹之外)其余樹構(gòu)成的森林。即：依次從左至右對森林中的每一棵樹進行先序遍歷。(1、2、3)1.先序遍歷107

BCDEFGHIJK123先序遍歷序列：BEFCDGHIJK123先序遍歷序列：BEFCDGHI108２．中序遍歷

若森林不空，則中序遍歷森林中第一棵樹的子樹森林；訪問森林中第一棵樹的根結(jié)點；中序遍歷森林中(除第一棵樹之外)其

余樹構(gòu)成的森林。即：依次從左至右對森林中的每一棵樹進行中序遍歷。(2、1、3)２．中序遍歷若森林不空，則即：依次從左至右對森109

BCDEFGHIJK123中序遍歷序列：EFBCIJKHGD123中序遍歷序列：EFBCIJKH1106.8哈夫曼樹與

哈夫曼編碼

幾個預(yù)備概念

最優(yōu)樹的定義

如何構(gòu)造最優(yōu)樹

前綴編碼

6.8哈夫曼樹與

哈夫曼編碼111幾個概念路徑：樹中一個結(jié)點到另一個結(jié)點所經(jīng)過的分支。路徑長度：路徑上的分支數(shù)目。樹的路徑長度：從根到每一個結(jié)點的路徑長度之和。（完全二叉樹是路徑長度最短的二叉樹）ABCD幾個概念路徑：樹中一個結(jié)點到另一個結(jié)點所經(jīng)過的分支。ABCD112

一、最優(yōu)樹的定義結(jié)點的帶權(quán)路徑長度定義為：

結(jié)點的權(quán)值乘以該結(jié)點的路徑長度。結(jié)點的路徑長度定義為：

從根結(jié)點到該結(jié)點的路徑上分支的數(shù)目。一、最優(yōu)樹的定義結(jié)點的帶權(quán)路徑長度定義為：結(jié)點的路徑長度113樹的帶權(quán)路徑長度定義為：

樹中所有葉子結(jié)點的帶權(quán)路徑長度之和WPL(T)=wklk(對所有葉子結(jié)點)。

在所有含n個葉子結(jié)點、并帶相同權(quán)值的m叉樹中，必存在一棵其帶權(quán)路徑長度取最小值的樹，稱為“最優(yōu)二叉樹”。例如：樹的帶權(quán)路徑長度定義為：在所有含n個葉子結(jié)11427975492WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=895427975492WPL(T)=7115用給定的n個權(quán)值構(gòu)造n棵以各權(quán)值為根的二叉樹。二、如何構(gòu)造最優(yōu)樹(哈夫曼樹）(1)(赫夫曼算法)以二叉樹為例：問題：根據(jù)給定的n個權(quán)值{w1,w2,…,wn}，構(gòu)造一棵以這些權(quán)值為葉子的哈夫曼樹？用給定的n個權(quán)值構(gòu)造n棵以各權(quán)值為根的二叉樹。二、如何構(gòu)116選取其根結(jié)點的權(quán)值為最小的兩棵二叉樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并且這棵新的二叉樹根結(jié)點的權(quán)值為其左、右子樹根結(jié)點的權(quán)值之和；并刪去這兩棵二叉樹，同時加入剛新生成的二叉樹；(2)(3)重復(fù)

第(2)

步，直至生成一棵樹為止。選取其根結(jié)點的權(quán)值為最小的兩棵二叉樹，分別作為左、1179例如:已知權(quán)值W={5,6,2,9,7}5627527697671395279例如:已知權(quán)值W={5,6,2,9,7}51186713952795271667132900001111000110110111671395279527166713290000111100119

指的是，任何一個字符的編碼都不是同一字符集中另一個字符的編碼碼的前綴。三、前綴編碼

利用哈夫曼樹可以構(gòu)造一種不等長的二進制編碼，并且構(gòu)造所得的哈夫曼編碼是一種最優(yōu)前綴編碼，即：使所傳電文的總長度最短。指的是，任何一個字符的編碼都三、前綴編碼120有八種字符：abcdefgh，其在通信聯(lián)絡(luò)中出現(xiàn)的概率分別為：0.050.290.070.080.140.230.030.11,試設(shè)計哈夫曼遍碼。

設(shè)權(quán)w=(5,29,7,8,14,23,3,11)n=8構(gòu)造過程：52978142331153829781423117815292311141119291423142929232342295810000000001111111a:0000b:11c:1000d:1001e:101f:01g:0001h:001有八種字符：abcdefgh，其在通信聯(lián)絡(luò)中121作業(yè)以數(shù)據(jù)集{2，5，7，9，13}為權(quán)值構(gòu)造一棵huffman樹，并計算其帶權(quán)路徑長度。習(xí)題集P416.26（僅使用01編碼方案）作業(yè)122按層次遍歷二叉樹（二叉鏈表）分析：使用一個隊列，先將二叉樹根結(jié)點入隊列，然后出隊，并輸出該結(jié)點。若它有左孩子則左孩子入隊；若有右孩子則右孩子入隊，然后分別出隊，直到隊列為空。

按層次遍歷二叉樹（二叉鏈表）分析：123#defineMAXSIZE100structqueue{bitreev[MAXSIZE];

intfront,rear;

//隊頭、隊尾指針}q;voidlevelorder(bitreet){q.front=q.rear=0;//初始化空隊列

if(t!=NULL)printf(“%d”,t->data);

//遍歷根結(jié)點

q.v[q.rear]=t;q.rear=q.rear+1;

//結(jié)點指針入隊while(q.front<q.rear)//隊列不空

{

s=q.v[q.front];q.front=q.front;

//隊頭出隊if(s->lchild!=NULL)//遍歷左孩子

{printf(“%d”,s->lchile->data);q.v[q.rear]=s->lchild;q.rear=q.rear+1;}if(s->rchild!=NULL)//遍歷右孩子{printf(“%d”,s->rchile->data);q.v[q.rear]=s->rchild;q.rear=q.rear+1;}

}}

#defineMAXSIZE100124

1.熟練掌握二叉樹的結(jié)構(gòu)特性，了解相應(yīng)的證明方法。2.熟悉二叉樹的各種存儲結(jié)構(gòu)的特點及適用范圍。3.遍歷二叉樹是二叉樹各種操作的基礎(chǔ)。實現(xiàn)二叉樹遍歷的具體算法與所采用的存儲結(jié)構(gòu)有關(guān)。掌握各種遍歷策略的遞歸算法，靈活運用遍歷算法實現(xiàn)二叉樹的其它操作。層次遍歷是按另一種搜索策略進行的遍歷。1.熟練掌握二叉樹的結(jié)構(gòu)特性，了解相應(yīng)的證明方法。1254.理解二叉樹線索化的實質(zhì)是建立結(jié)點與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系，熟練掌握二叉樹的線索化過程以及在中序線索化樹上找給定結(jié)點的前驅(qū)和后繼的方法。二叉樹的線索化過程是基于對二叉樹進行遍歷，而線索二叉樹上的線索又為相應(yīng)的遍歷提供了方便。4.理解二叉樹線索化的實質(zhì)是建立結(jié)點與其在相應(yīng)序列中的1265.熟悉樹的各種存儲結(jié)構(gòu)及其特點，掌握樹和森林與二叉樹的轉(zhuǎn)換方法。建立存儲結(jié)構(gòu)是進行其它操作的前提，因此讀者應(yīng)掌握1至2種建立二叉樹和樹的存儲結(jié)構(gòu)的方法。6.學(xué)會編寫實現(xiàn)樹的各種操作的算法。7.了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和哈夫曼編碼的方法。5.熟悉樹的各種存儲結(jié)構(gòu)及其特點，掌握樹和森林與二叉樹127

第六章樹和二叉樹第六章樹和二叉樹1286.1樹的類型定義6.2二叉樹的類型定義6.3

二叉樹的存儲結(jié)構(gòu)6.4二叉樹的遍歷6.5線索二叉樹6.6樹和森林的表示方法6.7樹和森林的遍歷6.8哈夫曼樹與哈夫曼編碼6.1樹的類型定義6.2二叉樹的類型定義6.3二叉樹的1296.1樹的類型定義6.1130數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。

若D為空集，則稱為空樹。否則:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root；(2)當n>1時，其余結(jié)點可分為m(m>0)個互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定義的樹，稱為根root的子樹。

數(shù)據(jù)關(guān)系R：數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。若D131

基本操作：查找類

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

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())//遍歷Root(T)//求樹的根結(jié)點查找類：Val133InitTree(&T)//初始化置空樹

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

ClearTree(&T)//將樹清空

刪除類：DestroyTree(&T)//銷毀樹的結(jié)構(gòu)DeleteChild(&T,&p,i)//刪除結(jié)點p的第i棵子樹ClearTree(&T)//將樹清空刪除類：De1351、樹（Tree)：是n個結(jié)點的有限集（n>=0)。在任意一棵非空樹中，有且僅有一個特定的稱為根的結(jié)點（root)；當n>1時，其余結(jié)點可分為m（m>0)個互不相交的有限集T1,T2,…,Tm,其中每個集合Ti本身又是一棵符合本定義的樹，并且稱為根root的子樹。1、樹（Tree)：是n個結(jié)點的有限集（n>=0)。在任意一136(１)有確定的根；(２)樹根和子樹根之間為有向關(guān)系。有向樹：有序樹：樹中結(jié)點的各子樹之間的先后次序是有意義的，不能互換，否則就成為另一棵樹了。子樹之間存在確定的次序關(guān)系。無序樹：樹中結(jié)點的各子樹之間的先后次序無意義，可以互換。子樹之間不存在確定的次序關(guān)系。(１)有確定的根；有向樹：有序樹：樹中結(jié)點的各子樹之間的先137ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2樹根例如:ABCDEFGHIJMKLA(B(E,F(K,L)),138樹的示意圖：根結(jié)點根結(jié)點葉結(jié)點分支結(jié)點子樹子樹子樹Level1Level2Level3Level4結(jié)點的層次樹的示意圖：根結(jié)點根結(jié)點葉結(jié)點分支結(jié)點子樹子樹子樹Level139對比樹型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點對比樹型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點140~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結(jié)構(gòu)樹型結(jié)構(gòu)第一個數(shù)據(jù)元素(無前驅(qū))

根結(jié)點(無前驅(qū))最后一個數(shù)據(jù)元素(無后繼)多個葉子結(jié)點(無后繼)其它數(shù)據(jù)元素(一個前驅(qū)、一個后繼)其它數(shù)據(jù)元素(一個前驅(qū)、多個后繼)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~141基本術(shù)語基本術(shù)語1421、結(jié)點:2、結(jié)點的度:3、樹的度:4、葉子結(jié)點:5、分支結(jié)點:數(shù)據(jù)元素+若干指向子樹的分支分支的個數(shù)樹中所有結(jié)點的度的最大值度為零的結(jié)點度大于零的結(jié)點DHIJM（終端結(jié)點）（非終端結(jié)點）1、結(jié)點:2、結(jié)點的度:3、樹的度:4、葉子結(jié)點:5、分支結(jié)1436、(從根到結(jié)點的)路徑：7、孩子結(jié)點、雙親結(jié)點兄弟結(jié)點、堂兄弟結(jié)點祖先結(jié)點、子孫結(jié)點8、結(jié)點的層次:9、樹的深度：

由從根到該結(jié)點所經(jīng)分支和結(jié)點構(gòu)成ABCDEFGHIJMKL假設(shè)根結(jié)點的層次為1，依次加1樹中葉子結(jié)點所在的最大層次6、(從根到結(jié)點的)路徑：7、孩子結(jié)點、雙親結(jié)點8、結(jié)點的層144任何一棵非空樹是一個二元組Tree=（root，F(xiàn)）其中：root被稱為根結(jié)點F被稱為子樹森林10、森林：是m（m≥0）棵互不相交的樹的集合。ArootBCDEFGHIJMKLF任何一棵非空樹是一個二元組10、森林：是m（m≥0）棵互Ar1456.2

二叉樹的類型定義二叉樹是樹的基礎(chǔ)，一般的樹可以轉(zhuǎn)化為二叉樹來處理。6.2146

1、二叉樹的定義：

二叉樹或為空樹，或是由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成（即左、右子樹次序不能顛倒）。ABCDEFGHK根結(jié)點左子樹右子樹1、二叉樹的定義：二叉樹或為空樹，或是由一個根結(jié)點加1472、二叉樹的五種基本形態(tài)：N空樹只含根結(jié)點NNNLRR右子樹為空樹L左子樹為空樹左右子樹均不為空樹2、二叉樹的五種基本形態(tài)：N空樹只含根結(jié)點NNNLRR右子樹148

二叉樹的主要基本操作：查找類插入類刪除類二叉樹的主要基本操作：查找類插入類刪除149

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());Root(T);Value(T,e);150

InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);InitBiTree(&T);151ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);ClearBiTree(&T);152二叉樹

的重要特性二叉樹

的重要特性153

性質(zhì)1：

在二叉樹的第i層上至多有2i-1個結(jié)點。(i≥1)用歸納法證明：

歸納基：

歸納假設(shè)：

歸納證明：i=1

層時，只有一個根結(jié)點：

2i-1=20=1；假設(shè)對所有的j，1≤j

i，命題成立；由歸納假設(shè)知：第I-1層上至多有2i-2個結(jié)點。又因為二叉樹上每個結(jié)點至多有兩棵子樹，則第i層的結(jié)點數(shù)=2i-22=2i-1

。性質(zhì)1：在二叉樹的第i層上至多有154性質(zhì)2：

深度為k的二叉樹上至多有2k-1個結(jié)點（k≥1）。證明：[證明用求等比數(shù)列前k項和的公式]基于上一條性質(zhì)，深度為k的二叉樹上的結(jié)點數(shù)至多為

20+21+

+2k-1=2k-1。性質(zhì)2：

深度為k的二叉樹上至多有2k-1155

性質(zhì)3：

對任何一棵二叉樹，若它含有n0個葉子結(jié)點、n2個度為2的結(jié)點，則必存在關(guān)系式：n0=n2+1。證明：設(shè)二叉樹上結(jié)點總數(shù)n=n0+n1+n2又二叉樹上分支總數(shù)b=n0*0+n1+2n2

而b=n-1=n0+n1+n2-1由此，n0=n2+1。性質(zhì)3：

對任何一棵二叉樹，若它含有n0個葉子156兩類特殊形態(tài)的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個結(jié)點的二叉樹。完全二叉樹：樹中所含的n個結(jié)點和滿二叉樹中編號為1至n的結(jié)點一一對應(yīng)。123456789101112131415abcdefghij兩類特殊形態(tài)的二叉樹：滿二叉樹：指的是深度為k且含有2k-1157

性質(zhì)4：

具有n個結(jié)點的完全二叉樹的深度為log2n+1。證明：設(shè)完全二叉樹的深度為k，則由性質(zhì)2和完全二叉樹的定義知：深度為k-1的二叉樹應(yīng)該是一棵滿二叉樹，故結(jié)點數(shù)為2k-1-1；深度為k的完全二叉樹當為滿二叉樹時結(jié)點數(shù)最多為2k–1。所以得2k-1-1

<n≤2k–1

2k-1≤n<2k

即k-1≤log2n<k因為k只能是整數(shù)，因此，k=log2n

+1。性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為158性質(zhì)5：若對含n個結(jié)點的完全二叉樹從上到下且從左至右進行1至n的編號，則對完全二叉樹中任意一個編號為i的結(jié)點：

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

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

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

(3)