數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt

第6章樹(shù)與二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第1頁(yè)。校長(zhǎng)一系二系三系六系教務(wù)處科研處總務(wù)處601602教務(wù)科603ABCD…………張三李四王五…例1…工廠數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第2頁(yè)。(根目錄)

\f1f2f3fnd1d2dm………例2f11f12f1kd11d12…………數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第3頁(yè)。例3數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第4頁(yè)。1樹(shù)的基本概念2樹(shù)的存儲(chǔ)結(jié)構(gòu)3二叉樹(shù)4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)5二叉樹(shù)的遍歷6線索二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第5頁(yè)。

6.1

樹(shù)的基本概念

樹(shù)是由n0個(gè)結(jié)點(diǎn)組成的有窮集合(不妨用D表示)以及結(jié)點(diǎn)之間關(guān)系組成的集合構(gòu)成的結(jié)構(gòu)。當(dāng)n=0時(shí)，稱該樹(shù)為空樹(shù)；在任何一棵非空的樹(shù)中，有一個(gè)特殊的結(jié)點(diǎn)tD，稱之為該樹(shù)的根結(jié)點(diǎn)；其余結(jié)點(diǎn)D–{t}被分割成m>0個(gè)不相交的子集D1,D2,…,Dm,其中每一個(gè)子集Di又為一棵樹(shù)，分別稱之為t的子樹(shù)。遞歸定義一.樹(shù)的定義數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第6頁(yè)。2021/3/117JIHGFEACXBA的第1棵子樹(shù)A的第3棵子樹(shù)A的第2棵子樹(shù)二.樹(shù)(邏輯上)的特點(diǎn)1.有且僅有一個(gè)結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn),該結(jié)點(diǎn)為樹(shù)的根結(jié)點(diǎn)。2.除了根結(jié)點(diǎn)外,每個(gè)結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)結(jié)點(diǎn)。3.包括根結(jié)點(diǎn)在內(nèi)，每個(gè)結(jié)點(diǎn)可以有多個(gè)后繼結(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第7頁(yè)。JIHGFEACXB4.

樹(shù)形表示法

借助自然界中一棵倒置的樹(shù)的形狀來(lái)表示數(shù)據(jù)元素之間層次關(guān)系的方法。數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第8頁(yè)。1.

結(jié)點(diǎn)的度：2.

樹(shù)的度：3.

葉結(jié)點(diǎn)：4.

分支結(jié)點(diǎn):5.

層次的定義:JIHGFEACXB該結(jié)點(diǎn)擁有的子樹(shù)的數(shù)目。樹(shù)中結(jié)點(diǎn)度的最大值。度為0的結(jié)點(diǎn).度非0的結(jié)點(diǎn).

根結(jié)點(diǎn)為第一層,若某結(jié)點(diǎn)在第i層,

則其孩子結(jié)點(diǎn)(若存在)為第i+1層.四.基本名詞術(shù)語(yǔ)第1層第2層第3層數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第9頁(yè)。7.

樹(shù)林(森林):m0棵不相交的樹(shù)組成的樹(shù)的集合.8.

樹(shù)的有序性:6.

樹(shù)的深度:樹(shù)中結(jié)點(diǎn)所處的最大層次數(shù).

若樹(shù)中結(jié)點(diǎn)的子樹(shù)的相對(duì)位置不能隨意改變,則稱該樹(shù)為有序樹(shù)，否則稱該樹(shù)為無(wú)序樹(shù)。JIHGFEACXB深度為3的樹(shù)數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第10頁(yè)。二叉樹(shù)的基本形態(tài)：(空)根根左子樹(shù)根右子樹(shù)根左子樹(shù)右子樹(shù)

6.2

二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第11頁(yè)。二.兩種特殊形態(tài)的二叉樹(shù)

若一棵二叉樹(shù)中的結(jié)點(diǎn),或者為葉結(jié)點(diǎn)，或者具有兩棵非空子樹(shù),并且葉結(jié)點(diǎn)都集中在二叉樹(shù)的最下面一層.這樣的二叉樹(shù)為滿二叉樹(shù).1.滿二叉樹(shù)

若一棵二叉樹(shù)中只有最下面兩層的結(jié)點(diǎn)的度可以小于2,并且最下面一層的結(jié)點(diǎn)(葉結(jié)點(diǎn))都依次排列在該層從左至右的位置上。這樣的二叉樹(shù)為完全二叉樹(shù).2.完全二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第12頁(yè)。1.一棵非空二叉樹(shù)的第i層最多有2i–1個(gè)結(jié)點(diǎn)(i1)。三.二叉樹(shù)的性質(zhì)2.

深度為h的非空二叉樹(shù)最多有2h-1個(gè)結(jié)點(diǎn).3.

若非空二叉樹(shù)有n0個(gè)葉結(jié)點(diǎn),有n2個(gè)度為2的結(jié)點(diǎn),

則n0=n2+1

4.

具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度h=log2n+1.數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第13頁(yè)。

二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)一.二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)12345678910ABCDEFGHIJBT[1:15]123456789101112131415ABCDEFGHIJ

根據(jù)完全二叉樹(shù)的性質(zhì)

,對(duì)于深度為h的完全二叉樹(shù),將樹(shù)中所有結(jié)點(diǎn)的數(shù)據(jù)信息按照編號(hào)的順序依次存儲(chǔ)到一維數(shù)組BT[1:2h-1]中,由于編號(hào)與數(shù)組的下標(biāo)一一對(duì)應(yīng),該數(shù)組就是該完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu).1.完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第14頁(yè)。12345678910ABCDEFGHIJ111213BT[1:15]123456789101112131415ABCDEFGHJ

IABCDEFGHIJ2.一般二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第15頁(yè)。2021/3/1116

對(duì)于一般二叉樹(shù),只須在二叉樹(shù)中“添加”一些實(shí)際上二叉樹(shù)中并不存在的“虛結(jié)點(diǎn)”

(可以認(rèn)為這些結(jié)點(diǎn)的數(shù)據(jù)信息為空),使其在形式上成為一棵“完全二叉樹(shù)”,然后按照完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)的構(gòu)造方法將所有結(jié)點(diǎn)的數(shù)據(jù)信息依次存放于數(shù)組BT[1:2h-1]中。數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第16頁(yè)。二.二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(二叉鏈表)鏈結(jié)點(diǎn)的構(gòu)造為lchilddatarchild

其中,data為數(shù)據(jù)域

lchild

與rchild分別為指向左、右子樹(shù)的指針域.ABCDEFGIJABCDEFGJIT^^^^^^^^^^數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第17頁(yè)。6.3.3

二叉樹(shù)的遍歷數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第18頁(yè)。二.前序遍歷數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第19頁(yè)。三.中序遍歷數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第20頁(yè)。四.后序遍歷數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第21頁(yè)。2021/3/1122ABCDKFGIJEH前序遍歷序列:

A,B,D,K,J,G,C,F,I,E,H中序遍歷序列:

D,B,G,J,K,A,F,I,E,C,H后序遍歷序列:

D,G,J,K,B,E,I,F,H,C,A按層次遍歷序列:

A,B,C,D,K,F,H,J,I,G,E例數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第22頁(yè)。2021/3/11236.3.2線索二叉樹(shù)1.何謂線索二叉樹(shù)？遍歷結(jié)果是求得結(jié)點(diǎn)的一個(gè)線性序列。指向該線性序列“前驅(qū)”和“后繼”的指針，稱“線索”；包含“線索”的存儲(chǔ)結(jié)構(gòu)，稱為“線索鏈表”；與其相應(yīng)的二叉樹(shù)，稱為“線索二叉樹(shù)”；對(duì)二叉樹(shù)以某種次序遍歷，使其變?yōu)榫€索二叉樹(shù)的過(guò)程，稱為“線索化”。數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第23頁(yè)。2.線索鏈表中結(jié)點(diǎn)的結(jié)構(gòu)在二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)中增加兩個(gè)標(biāo)志域，并規(guī)定：lchildLTagdataRTagrchild其中：LTag=0lchild域指示結(jié)點(diǎn)的左孩子1lchild域指示結(jié)點(diǎn)的前驅(qū)RTag=0rchild域指示結(jié)點(diǎn)的右孩子1rchild域指示結(jié)點(diǎn)的后繼數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第24頁(yè)。2021/3/1125二叉樹(shù)二叉線索存儲(chǔ)表示typedefenum{Link,Thread}PointerThr;

//Link==0:指針，Thread==1:線索typedefstructBiThrNode{TElemTypedata;StructBiThrNode*lchild,*rchild;

//左右孩子指針

PointerThrLTag,RTag;//左右標(biāo)志}BiThrNode,*BiThrTree;數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第25頁(yè)。2021/3/11263.線索二叉樹(shù)圖例

線索二叉樹(shù)及其存儲(chǔ)結(jié)構(gòu)（a）中序線索二叉樹(shù)（b）中序線索鏈表1234567010020131141050161171thrt0

1數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第26頁(yè)。2021/3/1127如何在線索樹(shù)中找結(jié)點(diǎn)的后繼？結(jié)合中序線索樹(shù)若其右標(biāo)志為“1”，右鏈?zhǔn)蔷€索，右鏈直接指示了結(jié)點(diǎn)的后繼；若其右標(biāo)志為“0”，右鏈?zhǔn)侵羔槪浜罄^為右子樹(shù)中最左下的結(jié)點(diǎn)。1234567數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第27頁(yè)。2021/3/1128如何在線索樹(shù)中找結(jié)點(diǎn)的前驅(qū)？結(jié)合中序線索樹(shù)

若其左標(biāo)志為“1”，左鏈為線索，直接指示其前驅(qū)；若其左標(biāo)志為“0”，左子樹(shù)中最右下的結(jié)點(diǎn)為其前驅(qū)。1234567數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第28頁(yè)。2021/3/1129線索鏈表的中序遍歷算法StatusIOTraver_T(BiThrTreeT,Status(*Visit)(TElemTypee)){//T指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的左鏈lchild指向根結(jié)點(diǎn)，中序遍歷

//二叉線索樹(shù)T的非遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit。

p=T->lchild;//p指向根結(jié)點(diǎn)

while(p!=T){//空樹(shù)或遍歷結(jié)束時(shí)，p==Twhile(p->LTag==Link)p=p->lchild;if(!Visit(p->data))returnERROR;//訪問(wèn)其左子樹(shù)為空的結(jié)點(diǎn)

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

p=p->rchild;}returnOK;}//IOTraver_T010020131141050161171T011數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第29頁(yè)。2021/3/11306.4.2森林和二叉樹(shù)的轉(zhuǎn)換1.樹(shù)和二叉樹(shù)的對(duì)應(yīng)關(guān)系由于二叉樹(shù)和樹(shù)都可用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則以二叉鏈表作為媒介可導(dǎo)出樹(shù)與二叉樹(shù)之間的一個(gè)對(duì)應(yīng)關(guān)系。數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第30頁(yè)。2021/3/1131數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第31頁(yè)。2021/3/1132樹(shù)轉(zhuǎn)換為二叉樹(shù)方法：1）對(duì)每個(gè)孩子進(jìn)行從左到右的排序；2）在兄弟之間加一條連線；3）對(duì)每個(gè)結(jié)點(diǎn)，除了左孩子外，去除其與其余孩子之間的聯(lián)系；4）以根結(jié)點(diǎn)為軸心，將整個(gè)樹(shù)順時(shí)針轉(zhuǎn)45°。數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第32頁(yè)。2021/3/1133ABCDEGHFIaABCDEGHFIbABCDEGHFIcABCDEGHFId數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第33頁(yè)。2021/3/11342.森林和二叉樹(shù)的對(duì)應(yīng)關(guān)系從樹(shù)的二叉鏈表表示的定義可知，任何一棵和樹(shù)對(duì)應(yīng)的二叉樹(shù)，其右子樹(shù)必空。若把森林中第二棵樹(shù)的根結(jié)點(diǎn)看成是第一棵樹(shù)的根結(jié)點(diǎn)的兄弟，則同樣可導(dǎo)出森林和二叉樹(shù)的對(duì)應(yīng)關(guān)系。數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第34頁(yè)。2021/3/1135數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第35頁(yè)。2021/3/1136BCDEGHFIaBCDEGHFIbBCDEGHFIcBCDEGHFId數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第36頁(yè)。2021/3/1137已知條件：森林和二叉樹(shù)的對(duì)應(yīng)關(guān)系設(shè)森林F=(T1,T2,…,Tn);T1=(root，t11,t12,…,t1m);

二叉樹(shù)B=(LBT,Node(root),RBT);由森林轉(zhuǎn)換成二叉樹(shù)的轉(zhuǎn)換規(guī)則為:若F=Φ，則B=Φ;否則，由Root(T1)對(duì)應(yīng)得到Node(root);

由(t11,t12,…,t1m)對(duì)應(yīng)得到LBT;

由(T2,T3,…,Tn)對(duì)應(yīng)得到RBT。由二叉樹(shù)轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為:若B=Φ,則F=Φ;否則，由Node(root)對(duì)應(yīng)得到Root(T1);

由LBT對(duì)應(yīng)得到(t11,t12,…，t1m);T1除根以外所構(gòu)成的森林由RBT對(duì)應(yīng)得到(T2,T3,…,Tn)；除T1之外的森林?jǐn)?shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第37頁(yè)。2021/3/11386.4.3樹(shù)和森林的遍歷1.樹(shù)的遍歷：有三條搜索路徑先根(序)遍歷：若樹(shù)不空，則先訪問(wèn)根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹(shù)。后根(序)遍歷：若樹(shù)不空，則先依次后根遍歷各棵子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)。按層次遍歷：若樹(shù)不空，則自上而下自左至右訪問(wèn)樹(shù)中每個(gè)結(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)ppt全文共42頁(yè)，當(dāng)前為第38頁(yè)。2021/3/1139