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