第7講6與二叉樹114節(jié)

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

二叉樹的存儲結(jié)構(gòu)6.4二叉樹的遍歷6.5線索二叉樹6.6樹和森林的表示方法6.7樹和森林的遍歷6.8哈夫曼樹與哈夫曼編碼6.1樹的類型定義一.樹的抽象數(shù)據(jù)類型定義二.樹的基本術(shù)語ABCDEFGHIJMKL樹的表示方法A()T1T3T2樹根B(E,F(K,L)),

C(G),

D(H,I,J(M))ABEFKLCGDHIJMWKPTMS舉例：

W(K(A,T(M(B,S),C)),P)ABC數(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：

基本操作：查找類

插入類刪除類

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())//遍歷InitTree(&T)//初始化置空樹

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

ClearTree(&T)//將樹清空

刪除類：DestroyTree(&T)//銷毀樹的結(jié)構(gòu)DeleteChild(&T,&p,i)//刪除結(jié)點p的第i棵子樹樹的基本術(shù)語結(jié)點:結(jié)點的度:樹的度:葉子結(jié)點:分支結(jié)點:數(shù)據(jù)元素+若干指向子樹的分支分支的個數(shù)樹中所有結(jié)點的度的最大值度為零的結(jié)點度大于零的結(jié)點DHIJM(從根到結(jié)點的)路徑：孩子結(jié)點、雙親結(jié)點、兄弟結(jié)點、堂兄弟祖先結(jié)點、子孫結(jié)點結(jié)點的層次:樹的深度：由從根到該結(jié)點所經(jīng)分支和結(jié)點構(gòu)成ABCDEFGHIJMKL假設(shè)根結(jié)點的層次為1,第k層的結(jié)點的子樹根結(jié)點的層次為k+1樹中葉子結(jié)點所在的最大層次任何一棵非空樹是一個二元組

Tree=（root，F(xiàn)）其中：root被稱為根結(jié)點，

F被稱為子樹森林森林：是m（m≥0）棵互不相交的樹的集合ArootBEFKLCGDHIJMF6.1樹的類型定義6.2二叉樹的類型定義6.3二叉樹的存儲結(jié)構(gòu)6.4二叉樹的遍歷6.5線索二叉樹6.6樹和森林的表示方法6.7樹和森林的遍歷6.8哈夫曼樹與哈夫曼編碼6.2

二叉樹的類型定義二叉樹的五種基本形態(tài)二叉樹的定義

二叉樹的主要基本操作

二叉樹的重要特性1.或為空樹；2.或是由一個根結(jié)點構(gòu)成;3.或是由一個根結(jié)點加上兩棵分別稱為左子樹

和右子樹的、互不相交的二叉樹組成;ABCDEFGHK根結(jié)點左子樹右子樹二叉樹的五種基本形態(tài)：N空樹只含根結(jié)點NNNLRR右子樹為空樹L左子樹為空樹左右子樹均不為空樹

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

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());查找類

InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,&p,LR,c);插入類ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,&p,LR);刪除類二叉樹

的重要特性

性質(zhì)1：在二叉樹的第i

層上至多有2i-1個結(jié)點。(i≥1)歸納基礎(chǔ)：i=1

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

2i-1=20=1；對所有的k，1≤ki，命題成立;即：在第k層上至多有2k-1個結(jié)點。二叉樹上每個結(jié)點至多有兩棵子樹，則：第k+1層的結(jié)點數(shù)=2k-12=2k

只要證明：k+1時命題成立;

即：在第k+1層上至多有2k個結(jié)點。用歸納法證明：

歸納假設(shè)：

證明：性質(zhì)2：

深度為k的二叉樹上至多含2k-1個結(jié)點（k≥1）證明：基于上一條性質(zhì)，深度為k的二叉樹上的結(jié)點數(shù)至多為

20+21+

+2k-1=2k-1

性質(zhì)3：

對任何一棵二叉樹，若它含有n0個葉子結(jié)點、n2個度為

2

的結(jié)點，則必存在關(guān)系式：n0=n2+1證明：設(shè)二叉樹上結(jié)點總數(shù)n=n0+n1+n2又二叉樹上分支總數(shù)b=n1+2n2而b=n-1

由此，n0=n2+1=n0+n1+n2-1兩類特殊的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個結(jié)點的二叉樹。完全二叉樹：樹中所含的n個結(jié)點和滿二叉樹中編號為1至n的結(jié)點一一對應(yīng)。123456789101112131415abcdefghij例：在含有968個結(jié)點的完全二叉樹中，葉子結(jié)點的個數(shù)為多少？n0=n2+1；（性質(zhì)3）解：在含有968個結(jié)點的完全二叉樹中，度為1的結(jié)點個數(shù)為1。 即：n1=1;n0=4842n2+1=966完全二叉樹中度為1的結(jié)點個數(shù)為1或0；如果完全二叉樹結(jié)點個數(shù)為奇數(shù)，則度為1的結(jié)點個數(shù)為0.n0＋n1＋n2＝9682n2＋n1

＋1＝9682n2＋n1

＝967n2=483k-1層一定是滿二叉樹，即n=前k-1層結(jié)點+第k層結(jié)點≥2k-1

性質(zhì)4：

具有n個結(jié)點的完全二叉樹的深度為

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

k-1≤log2n<k

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

+1因此，2k-1≤n<2k<2k

6.1樹的類型定義6.2二叉樹的類型定義6.3二叉樹的存儲結(jié)構(gòu)6.4二叉樹的遍歷6.5線索二叉樹6.6樹和森林的表示方法6.7樹和森林的遍歷6.8哈夫曼樹與哈夫曼編碼6.3二叉樹的存儲結(jié)構(gòu)二、二叉樹的鏈式存儲表示一、二叉樹的順序存儲表示一、二叉樹的順序存儲表示ABCDEFGHIJKLMNPABCDEFGHIJKLMNP123456789101112131415滿二叉樹12483715性質(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é)點。ABCDEFGHIJKL完全二叉樹ABCDEFGHIJKL123456789101112131415

ABCDEF

012345678910111213ABDCEF1401326一般二叉樹ABCDEF

123456D#defineMAX_TREE_SIZE100//二叉樹的最大結(jié)點數(shù)typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0號單元存儲根結(jié)點二叉樹順序存儲的C語言表示二、二叉樹的鏈式存儲表示1.二叉鏈表2．三叉鏈表3．雙親鏈表4．線索鏈表ADEBCFrootlchilddatarchild結(jié)點結(jié)構(gòu):1.二叉鏈表指針域=2n分支=n-1空域＝2n-(n-1)=n+1typedefstruct

BiTNode

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

TElemTypedata;

structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;lchilddatarchild結(jié)點結(jié)構(gòu):二叉鏈表的C語言的類型描述如下:二、二叉樹的鏈式存儲表示1.二叉鏈表2．三叉鏈表3．雙親鏈表4．線索鏈表2．三叉鏈表parent

lchilddatarchild結(jié)點結(jié)構(gòu):ADEBCFroot二、二叉樹的鏈式存儲表示1.二叉鏈表2．三叉鏈表3．雙親鏈表4．線索鏈表0123456dataparent結(jié)點結(jié)構(gòu):3．雙親鏈表LRTagLRRRLABCDEF二、二叉樹的鏈式存儲表示1.二叉鏈表2．三叉鏈表3．雙親鏈表4．線索鏈表6.1樹的類型定義6.2二叉樹的類型定義6.3二叉樹的存儲結(jié)構(gòu)6.4二叉樹的遍歷6.5線索二叉樹6.6樹和森林的表示方法6.7樹和森林的遍歷6.8哈夫曼樹與哈夫曼編碼一、問題的提出二、先左后右的遍歷算法三、算法的遞歸描述四、先序遍歷的非遞歸算法五、遍歷算法的應(yīng)用舉例6.4二叉樹的遍歷順著某一條搜索路徑巡訪二叉樹中的結(jié)點，使得每個結(jié)點均被訪問一次，而且僅被訪問一次。一、問題的提出二叉樹是非線性結(jié)構(gòu)，每個結(jié)點有兩個后繼，因此，存在如何遍歷即按什么樣的搜索路徑遍歷的問題。對“二叉樹”而言，可以有三條搜索路徑：1．先上后下的按層次遍歷；2．先左（子樹）后右（子樹）的遍歷；3．先右（子樹）后左（子樹）的遍歷。一、問題的提出二、先左后右的遍歷算法三、算法的遞歸描述四、先序遍歷的非遞歸算法五、遍歷算法的應(yīng)用舉例6.4二叉樹的遍歷二、先左后右的遍歷算法先（根）序的遍歷算法中（根）序的遍歷算法后（根）序的遍歷算法先（根）序的遍歷算法根左子樹右子樹根左子樹右子樹

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

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

若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點。ABCDEFGHK例如：先序序列：中序序列：后序序列：A

BCD

EFGHKBDC

A

EHGKFDCBHKGFE

A一、問題的提出二、先左后右的遍歷算法三、算法的遞歸描述四、先序遍歷的非遞歸算法五、遍歷算法的應(yīng)用舉例6.4二叉樹的遍歷三、算法的遞歸描述先序遍歷算法1.若二叉樹為空樹，則空操作(結(jié)束)；2.否則，（1）訪問根結(jié)點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。根左子樹右子樹根左子樹右子樹先序遞歸算法描述void

Preorder(BiTreeT,

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

先序遍歷二叉樹

if(T){visit(T->data);//訪問結(jié)點

Preorder(T->lchild,visit);//遍歷左子樹

Preorder(T->rchild,visit);//遍歷右子樹

}}中序遍歷算法1.若二叉樹為空樹，則空操作（結(jié)束）；2.否則，（1）中序遍歷左子樹；（2）訪問根結(jié)點；（3）中序遍歷右子樹。中序遞歸算法描述void

Inorder(BiTreeT,

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

中序遍歷二叉樹

if(T){

Inorder(T->lchild,visit);//遍歷左子樹

visit(T->data);//訪問結(jié)點

Inorder(T->rchild,visit);//遍歷右子樹

}}61一、問題的提出二、先左后右的遍歷算法三、算法的遞歸描述四、先序遍歷的非遞歸算法五、遍歷算法的應(yīng)用舉例6.4二叉樹的遍歷62四、先序遍歷的非遞歸算法ABCDE訪問ABCDE當前結(jié)點指針棧ApPBpCpDpEp63先序遍歷非遞歸算法思想算法關(guān)鍵:當前指針和棧

1.得到新的當前指針,則訪問結(jié)點,

然后,先進棧,再訪問左孩子;

2.使用棧存放待訪問結(jié)點的指針,以備在訪問該結(jié)點的左子樹之后,彈出結(jié)點指針,再訪問該結(jié)點的右子樹.

3.初始條件:指針指向樹根結(jié)點,棧為空;

4.結(jié)束條件:當前指針空,且?？?

5.循環(huán):指針不空則訪問結(jié)點,

指針空則退棧;64StatusPreOrderTraverse(BiTreeT,Visit())

{InitStack(S);

//使用棧

S

存放已訪問的根結(jié)點

p=T;//令

p

指向二叉樹根結(jié)點

while(p||!StackEmpty(S)){

//當

p

不為空，或棧

S

不為空時

if(p){

//如果

p

非空

Visit(p);

//訪問p

指針指向的結(jié)點

Push(S,p);

//將p

指針入棧

p=p->lchild;

//指向左子樹根結(jié)點，遍歷左子樹

}//if結(jié)束

else{

//如果p為空

Pop(S,p);

//退棧，將上一層的根結(jié)點指針彈出

p=p->rchild;

//指針指向右子樹根結(jié)點，遍歷右子樹

}//else結(jié)束

}//while結(jié)束

returnOK;}//PreOrderTraverse先序遍歷非遞歸算法65四、中序遍歷的非遞歸算法ABCDE訪問CBDAE當前結(jié)點指針棧ApPBpCpDpEp66StatusPreOrderTraverse(BiTreeT,Visit())

{InitStack(S);

//使用棧

S

存放已訪問的根結(jié)點

p=T;//令

p

指向二叉樹根結(jié)點

while(p||!StackEmpty(S)){

//當

p

不為空，或棧

S

不為空時

if(p){

//如果

p

非空

Visit(p);

//訪問p

指針指向的結(jié)點

Push(S,p);