《深圳大學-數(shù)據(jù)結(jié)構(gòu)-2017樹與二叉樹演示文檔》由會員分享，可在線閱讀，更多相關《深圳大學-數(shù)據(jù)結(jié)構(gòu)-2017樹與二叉樹演示文檔（73頁珍藏版）》請在裝配圖網(wǎng)上搜索。
.,第六章 樹與二叉樹,,,數(shù)據(jù)結(jié)構(gòu),,.,一、樹的定義(Tree),2,樹是有n(n≥0)個結(jié)點的有限集合。
如果 n=0，稱為空樹；
如果 n>0,稱為非空樹,對于非空樹,有且僅有一個特定的稱為根(Root)的節(jié)點(無直接前驅(qū))
如果 n>1，則除根以外的其它結(jié)點劃分為 m (m>0)個互不相交的有限集 T1, T2 ,…, Tm，其中每個集合本身又是一棵樹，并且稱為根的子樹(SubTree)。
每個結(jié)點都有唯一的直接前驅(qū)，但可能有多個后繼,,第一節(jié) 樹的概念與基本術(shù)語,.,一、樹的定義(舉例),3,其中：A是根；其余結(jié)點分成三個互不相交的子集，
T1={B,E,F,K,L}； T2={C,G}； T3={D,H,I,J,M},
T1,T2,T3都是根A的子樹，且本身也是一棵樹,A,只有根結(jié)點的樹,有13個結(jié)點的樹,第一節(jié) 樹的概念與基本術(shù)語,.,二、樹的基本術(shù)語,4,第一節(jié) 樹的概念與基本術(shù)語,結(jié)點：包含一個數(shù)據(jù)元素及若干指向其子樹的分支
結(jié)點的度：結(jié)點擁有的子樹數(shù)
樹的度：樹中各結(jié)點的度的最大值
葉結(jié)點：度為0的結(jié)點,也稱終端結(jié)點
分支結(jié)點：度不為0
的結(jié)點[包括根結(jié)點]，
也稱非終端結(jié)點。,.,二、樹的基本術(shù)語,5,第一節(jié) 樹的概念與基本術(shù)語,孩子：結(jié)點的子樹的根[直接后繼，可能有多個]
雙親：孩子的直接前驅(qū)[最多只能有一個]
兄弟：同一雙親的孩子
子孫：以某結(jié)點為根的
樹中的所有結(jié)點
祖先：從根到該結(jié)點
所經(jīng)分支上的所有結(jié)點,.,二、樹的基本術(shù)語,6,第一節(jié) 樹的概念與基本術(shù)語,層次：根結(jié)點為第一層，其孩子為第二層，依此類推
深度：樹中結(jié)點的最大層次
森林：互不相交的樹的集合。
對樹中每個結(jié)點而言，
其子樹的集合即為森林
.有序樹:樹中各結(jié)點的子樹按照一定次序從左向右安排,相對次序不能改變,.,一、二叉樹(Binary Tree),7,第二節(jié) 二叉樹,二叉樹是一種特殊的樹
每個結(jié)點最多有２棵子樹
二叉樹的子樹有左右之分,二叉樹的五種基本形態(tài),.,二、二叉樹性質(zhì)１,8,第二節(jié) 二叉樹,在二叉樹的第i層上至多有2i-1個結(jié)點
證明：
1.i=1, 只有一個根節(jié)點，因此2i-1=20=1
2.設第i-1層上，以上性質(zhì)成立，即第i-1層至多有2(i-1)-1結(jié)點。由二叉樹的定義可知，任何結(jié)點的度小于2，因此，第i層上的結(jié)點數(shù)最多為第i-1層上的兩倍，即2*2i-2=2i-1,.,三、二叉樹性質(zhì)２,9,第二節(jié) 二叉樹,深度為k的二叉樹至多有2k-1個結(jié)點
證明：
1.由性質(zhì)１，已知第i層上結(jié)點數(shù)最多為2i-1
k
2. ∑ 2i-1 = 2k-1
i=1,.,四、二叉樹性質(zhì)３,10,第二節(jié) 二叉樹,非空二叉樹上葉結(jié)點數(shù)等于雙分支結(jié)點數(shù)加一,即n0=n2+1
證明：
1.設n1為度為1的結(jié)點，則總結(jié)點數(shù)= n0+n1+n2
2.設B為二叉樹的分支數(shù)，除根結(jié)點外，每個結(jié)點有且只有一個分支，因此n=B+1
3.每個分支皆由度為1或2的結(jié)點發(fā)出，B=n1+2n2
4.n=B+1=(n1+2n2)+1 = n0+n1+n2，因此 n0=n2+1,.,五、滿二叉樹,11,第二節(jié) 二叉樹,一個深度為k且有2k-1個結(jié)點的二叉樹
每層上的結(jié)點數(shù)都是最大數(shù)
可以自上而下、
自左至右連續(xù)編號,.,六、完全二叉樹,12,第二節(jié) 二叉樹,當且僅當每一個結(jié)點都與深度相同的滿二叉樹中編號從1到n的結(jié)點一一對應的二叉樹
葉子結(jié)點只在最大兩層上出現(xiàn)
左子樹深度與右子樹
深度相等或大１,.,六、完全二叉樹(性質(zhì)４),13,第二節(jié) 二叉樹,具有n個結(jié)點的完全二叉樹,其深度為log2n +1
設k為深度，由二叉樹性質(zhì)２，已知
2k-1-1 < n ≤ 2k-1
即 2k-1 ≤ n < 2k
k-1 ≤ log2n
Rchild ，若q不為空，則q進棧；
⑶ p=p->Lchild ，若p不為空，轉(zhuǎn)(1)，否則轉(zhuǎn)(4)；
⑷ 退棧到p ，轉(zhuǎn)(1)，直到?？諡橹埂?.,第三節(jié) 遍歷二叉樹,void PreorderTraverse( BTNode T)
{ BTNode *Stack[MAX_NODE] ,*p=T, *q ;
int top=0 ;
if (T==NULL) printf(“ Binary Tree is Empty!\n”) ;
else
{ do
{ visit( p-> data ) ; q=p->Rchild ;
if ( q!=NULL )
stack[++top]=q ;
p=p->Lchild ;
if (p==NULL)
{ p=stack[top] ; top-- ;
}while (p!=NULL) ;
}
},.,三、中序遍歷二叉樹,30,第三節(jié) 遍歷二叉樹,算法：
1.若二叉樹為空，則返回；否則：
2.中序遍歷左子樹(L)
3.訪問根節(jié)點(D)
4.中序遍歷右子樹(R),.,三、中序遍歷二叉樹,31,第三節(jié) 遍歷二叉樹,算法(舉例)：
1.若二叉樹為空，則返回；否則：
2.中序遍歷左子樹(L)
3.訪問根節(jié)點(D)
4.中序遍歷右子樹(R)
輸出結(jié)果：DBGEAFC,.,三、中序遍歷二叉樹,32,第三節(jié) 遍歷二叉樹,算法：
void InOrderTraverse ( BinTree T )
{ if (T)
{ InOrderTraverse ( T->lChild );
cout data;
InOrderTraverse ( T->rChild );
}
},.,四、后序遍歷二叉樹,33,第三節(jié) 遍歷二叉樹,算法：
1.若二叉樹為空，則返回；否則：
2.后序遍歷左子樹(L)
3.后序遍歷右子樹(R)
4.訪問根節(jié)點(D),.,四、后序遍歷二叉樹,34,第三節(jié) 遍歷二叉樹,算法(舉例)：
1.若二叉樹為空，則返回；否則：
2.訪問根節(jié)點(D)
3.后序遍歷左子樹(L)
4.后序遍歷右子樹(R)
輸出結(jié)果：DGEBFCA,.,四、后序遍歷二叉樹,35,第三節(jié) 遍歷二叉樹,算法：
void PostOrderTraverse(BinTreeT)
{ if(T)
{ PostOrderTraverse(T->lChild);
PostOrderTraverse(T->rChild);
cout data;
}
},.,第三節(jié) 遍歷二叉樹,層次遍歷二叉樹
從根結(jié)點開始遍歷，按層次次序“自上而下，從左至右”訪問樹中的各結(jié)點。
算法：
設置一個隊列初始化為空,T指向根結(jié)點指針變量，
若二叉樹為空，返回；
否則，p=T，p入隊；
⑴ 隊首元素出隊到p；
⑵訪問p所指向的結(jié)點；
⑶將p指向結(jié)點的左、右子結(jié)點依次入隊。直到隊空為止。,.,第三節(jié) 遍歷二叉樹,#define MAX_NODE 50
void LevelorderTraverse( BTNode *T)
{ BTNode *Queue[MAX_NODE] ,*p=T ;
int front=0 , rear=0 ;
if (p!=NULL)
{ Queue[++rear]=p; /* 根結(jié)點入隊 */
while (frontdata );
if (p->Lchild!=NULL)
Queue[++rear]=p; /* 左結(jié)點入隊 */
if (p->Rchild!=NULL)
Queue[++rear]=p; /* 左結(jié)點入隊 */
}
},.,課堂練習,1. 已知二叉樹的先根和中根序列，求該二叉樹的后根序列
先根序列：A，B，C，D，E，F(xiàn)，G，H，I，J
中根序列：C，B，A，E，F(xiàn)，D，I，H，J，G
2. 已知一棵二叉樹的中根和后根序列，求該二叉樹的高度和雙支，單支及葉子結(jié)點數(shù)。
中根序列：c,b,d,e,a,g,I,h,j,f
后根序列：c,e,d,b,I,j,h,g,f,a,.,一、增加新指針,39,第四節(jié) 線索二叉樹,最簡單的方法是在每個結(jié)點中，增加前驅(qū)(fwd)和后繼(bkwd)指針
在做二叉樹遍歷（前、中、后序），將每個結(jié)點的前驅(qū)和后繼信息添入fwd和bkwd域中,.,二、利用空指針,40,第四節(jié) 線索二叉樹,在有n個結(jié)點的二叉樹中，必定存在n+1個空鏈域
因為每個結(jié)點有兩個鏈域（左、右孩子指針），因此共有2n個鏈域
除根結(jié)點外，每個結(jié)點都有且僅有一個分支相連，即n-1個鏈域被使用
可以利用這些空閑的指針域來存放結(jié)點的直接前驅(qū)和直接后繼信息。,.,二、利用空指針,41,第四節(jié) 線索二叉樹,在結(jié)點中增加兩個標記位（LTag, RTag)
LTag=0, lChild域指示結(jié)點的左孩子
LTag=1, lChild域指示結(jié)點的前驅(qū)結(jié)點
RTag=0, lChild域指示結(jié)點的右孩子
RTag=1, lChild域指示結(jié)點的后繼結(jié)點,.,第四節(jié) 線索二叉樹,.,第四節(jié) 線索二叉樹,線索二叉樹表示:實線表示指針，指向其左、右孩子； 虛線表示線索，指向其直接前驅(qū)(紅線)或直接后繼(綠線)。,.,第四節(jié) 線索二叉樹,1.在線索樹上進行遍歷
只要先找到序列中的第一個結(jié)點，然后就可以依次找結(jié)點的直接后繼結(jié)點直到后繼為空為止。
2.在線索樹中找結(jié)點的直接后繼(以中序遍歷為例)
◆ 樹中所有葉子結(jié)點的右鏈都是線索。
◆ 樹中所有非葉子結(jié)點的右鏈都是指針。
非葉子結(jié)點的直接后繼是遍歷其右子樹時訪問的第一個結(jié)點，即右子樹中最左下的(葉子)結(jié)點。如結(jié)點C的直接后繼：沿右指針找到右子樹的根結(jié)點F，然后沿左鏈往下直到Ltag=1的結(jié)點即為C的直接后繼結(jié)點H。,.,第四節(jié) 線索二叉樹,3.在線索樹中找結(jié)點的直接前驅(qū)(以中序遍歷為例)
若結(jié)點的Ltag=1，則左鏈是線索，指示其直接前驅(qū)；否則，遍歷左子樹時訪問的最后一個結(jié)點(即沿左子樹中最右往下的結(jié)點) 為其直接前驅(qū)結(jié)點。,.,一、樹的存儲結(jié)構(gòu),46,第五節(jié) 樹與森林,1.雙親表示法
采用一組連續(xù)的存儲空間
由于每個結(jié)點只有一個雙親，只需要一個指針,0 1 2 3 4 5 6,.,一、樹的存儲結(jié)構(gòu),47,第五節(jié) 樹與森林,2.孩子表示法
可以采用多重鏈表，即每個結(jié)點有多個指針
特點：鏈表結(jié)構(gòu)簡單,指針域的數(shù)目就是樹的度。
最大缺點:空鏈域太多,在一棵有n個結(jié)點，
度為k的樹中必有n(k-1)+1空指針域。,.,一、樹的存儲結(jié)構(gòu),48,第五節(jié) 樹與森林,2.孩子表示法
將每個結(jié)點的孩子排列起來，用單鏈表表示
將每個結(jié)點排列成一個線性表,0
1
2
3
4
5
6,,Root,,,,,,,.,一、樹的存儲結(jié)構(gòu),49,第五節(jié) 樹與森林,3.孩子兄弟表示法
采用二叉鏈表
左邊指針指向第一個孩子，右邊指針指向兄弟,.,二、樹與二叉樹的對應關系,50,第五節(jié) 樹與森林,樹與二叉樹都可以采用二叉鏈表作存儲結(jié)構(gòu)
任意給定一棵樹，可以找到一個唯一的二叉樹(沒有右子樹),樹,對應的二叉樹,.,三、森林與二叉樹的對應關系,51,第五節(jié) 樹與森林,如果把森林中的第二棵樹的根結(jié)點看作是第一棵樹的根結(jié)點的兄弟，則可找到一個唯一的二叉樹與之對應,三棵樹的森林,對應的二叉樹,T1 T2 T3,.,四、樹的遍歷,52,第五節(jié) 樹與森林,對樹的遍歷主要有兩種：
1. 先根（次序）遍歷
2. 后根（次序）遍歷,.,四、樹的遍歷,53,第五節(jié) 樹與森林,1. 先根（次序）遍歷
當樹非空時
訪問根結(jié)點
依次先根遍歷根的各棵子樹
輸出結(jié)果：ABEFCDG,.,四、樹的遍歷,54,第五節(jié) 樹與森林,2. 后根（次序）遍歷
當樹非空時
依次后根遍歷根的各棵子樹
訪問根結(jié)點
輸出結(jié)果：EFBCGDA,.,課堂練習,1. 二叉樹采用順序存儲結(jié)構(gòu)，如下圖所示：
(1)畫出該樹的邏輯結(jié)構(gòu)
(2)寫出該樹的先序遍歷、中序遍歷和后序遍歷的結(jié)果
(3)畫出把此二叉樹還原成森林的圖,.,課堂練習,2. 已知一棵樹的邊集表示為{,,,,,,,},每個結(jié)點的孩子按照從左下到右下的次序排列，先根遍歷得到的序列為（ ）。
3. 在一棵樹的孩子兄弟鏈表表示（又稱樹的二叉鏈表表示）中，一個結(jié)點的右孩子是該結(jié)點的(A )結(jié)點
A．兄弟 B.父子 C.祖先 D.子孫,.,一、最優(yōu)二叉樹,57,第六節(jié) 哈夫曼樹及其應用,路徑：從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點之間的路徑
路徑長度：路徑上的分支數(shù)目
樹的路徑長度：從樹根到
每個結(jié)點的路徑長度之和
右樹路徑長度為：
2*1 + 3*2 + 1*3 = 11,.,一、最優(yōu)二叉樹,58,第六節(jié) 哈夫曼樹及其應用,帶權(quán)路徑長度：從結(jié)點到樹根之間的路徑長度與結(jié)點上權(quán)的乘積
樹的帶權(quán)路徑長度(WPL)：樹中所有葉子結(jié)點的帶權(quán)路徑長度之和
WPL = 2*5+3*3+2*4=27,.,一、最優(yōu)二叉樹,59,第六節(jié) 哈夫曼樹及其應用,最優(yōu)二叉樹：假設二叉樹有n個葉子，其每個葉子結(jié)點帶權(quán)wi，則帶權(quán)路徑長度WPL最小的二叉樹稱為最優(yōu)二叉樹
哈夫曼(Huffman)樹就是一棵最優(yōu)二叉樹
WPL = 1*5+2*3+2*4=19,.,二、Huffman樹(構(gòu)造),60,第六節(jié) 哈夫曼樹及其應用,在Huffman樹中，權(quán)值最大的結(jié)點離根最近
權(quán)值最小的結(jié)點離根最遠,.,二、Huffman樹(算法),61,第六節(jié) 哈夫曼樹及其應用,1.根據(jù)給定的n個權(quán)值(w1, w2, …, wn)構(gòu)成n棵二叉樹的集合F={T1, T2, …, Tn}，其中每棵二叉樹Ti中只有一個帶樹為Ti的根結(jié)點
2.在F中選取兩棵根結(jié)點的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置其根結(jié)點的權(quán)值為其左右子樹權(quán)值之和
3.在F中刪除這兩棵樹，同時將新得到的二叉樹加入F中
4.重復2, 3，直到F只含一棵樹為止,.,二、Huffman樹(舉例),62,第六節(jié) 哈夫曼樹及其應用,.,三、Huffman編碼,63,第六節(jié) 哈夫曼樹及其應用,設給出一段報文：GOOD_GOOD_GOODGODG
字符集合是 { O, G, _, D }，各個字符出現(xiàn)的頻度(次數(shù))是 W＝{ 7, 5, 2, 4 }。
若給每個字符以等長編碼
O: 00 G: 10 _: 01 D: 11
則總編碼長度為 (2+7+4+5) * 2 = 36.,.,三、Huffman編碼,64,第六節(jié) 哈夫曼樹及其應用,若按各個字符出現(xiàn)的概率不同而給予不等長編碼，可望減少總編碼長度。
各字符出現(xiàn)概率為{ 2/18, 7/18, 4/18, 5/18 },化整為 { 2, 7, 4, 5 }
可構(gòu)成右圖所示Huffman樹,.,三、Huffman編碼,65,第六節(jié) 哈夫曼樹及其應用,令左孩子分支為編碼‘0’，右孩子分支為編碼‘1’
得到不等長編碼：
O:0 G:10 _:110 D:111
則總編碼長度為
7*1+5*2+4*3+2*3 = 35
Huffman是一種前綴編碼，解碼時不會混淆,.,第六節(jié) 哈夫曼樹及其應用,void HuffmanCoding(HuffmanTree ,.,第六節(jié) 哈夫曼樹及其應用,for (i=n+1; i<=m; i++) { // 建哈夫曼樹
// 在HT[1..i-1]中選擇parent為且weight最小的兩個結(jié)點，
// 其序號分別為s1和s2。
Select(HT, i-1, s1, s2);
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchild = s1; HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
printf("\nselect: s1=%d s2=%d\n", s1, s2);
printf(" 結(jié)點 weight parent lchild rchild");
for (j=1; j<=i; j++)
printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,
HT[j].parent,HT[j].lchild, HT[j].rchild);
printf(" 按任意鍵，繼續(xù)...");
getch();
},.,第六節(jié) 哈夫曼樹及其應用,[實例] 假設用于通信的電文僅由8個字母組成.字母在電文中出現(xiàn)頻率:0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10,
設計8個字母的Huffman編碼并比較等長編碼的總編碼長度.,.,算法設計練習,[例1]求二叉樹中以值為x的結(jié)點為根的子樹的深度
int TreeDepth(bitnode *p) //遞歸求二叉樹深度
{ int hl,hr,h;
if ( p!=NULL )
{
hl=TreeDepth(p->lchild); //遞歸求左子樹深度
hr=TreeDepth(p->rchild); //遞歸求右子樹深度
if ( hl>hr )
h=hl;
else
h=hr;
return(h＋1); //返回較大左右子樹深度加1
}
else
return(0);
},.,算法設計練習,[例2]求二叉樹中葉子結(jié)點的個數(shù)
template
int leafnum(bitreenode*root)
{ if(root==NULL)
return 0;
else if((root->lchild==NULL)
},.,算法設計練習,[例3]將一棵二叉樹復制給另一棵二叉樹
?
bitree *CopyTree(bnode *p) //復制一棵二叉樹
{ bitnode *t;
if (p!=NULL )
{ t=(bitnode*)malloc(sizeof(bnode));
t->data=p->data;
t->lchild=CopyTree(p->lchild);
t->rchild=CopyTree(p->rchild);
return(t);
}
else
return(NULL);,.,算法設計練習
[例4] 用二叉鏈表表示，判斷給定的二叉樹是否為完全二叉樹。
void? wanquan(BiTree T)
{ BiTree a[100]; int flag=0; int i=1,j; ? BiTree p; Queue myque; //借用隊列進行層次遍歷
InitQueue(myque); ? if (T) EnQueue(myque,T); ? while(!QueueEmpty(myque)) ? { DeQueue(myque,p); ? a[i++]=p; ?? if (p) ?? { EnQueue(myque,p->lchild); EnQueue(myque,p->rchild); } ?? } //層次遍歷，并進行數(shù)組賦值
for(j=1;j
下載提示(請認真閱讀)
- 1.請仔細閱讀文檔，確保文檔完整性，對于不預覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔，不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請點此認領！既往收益都歸您。
文檔包含非法信息？點此舉報后獲取現(xiàn)金獎勵！
下載文檔到電腦，查找使用更方便
10
積分
- 配套講稿：
如PPT文件的首頁顯示word圖標，表示該PPT已包含配套word講稿。雙擊word圖標可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國旗、國徽等圖片，僅作為作品整體效果示例展示，禁止商用。設計者僅對作品中獨創(chuàng)性部分享有著作權(quán)。
- 關 鍵 詞：
-
深圳大學
數(shù)據(jù)結(jié)構(gòu)
2017
二叉
演示
文檔
- 溫馨提示:
1: 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學習交流，未經(jīng)上傳用戶書面授權(quán)，請勿作他用。
深圳大學-數(shù)據(jù)結(jié)構(gòu)-2017樹與二叉樹演示文檔
鏈接地址：http://www.3dchina-expo.com/p-359905.html