數(shù)據(jù)結(jié)構(gòu)二叉樹優(yōu)選ppt資料

數(shù)據(jù)結(jié)構(gòu)(shùjùjiéɡòu)二叉樹第一頁，共41頁。校長(xiàozhǎng)一系二系三系六系教務(wù)處科研處總務(wù)處601602教務(wù)科603ABCD…………張三李四王五…例1…工廠第二頁，共41頁。(根目錄)

\f1f2f3fnd1d2dm………例2f11f12f1kd11d12…………第三頁，共41頁。例3第四頁，共41頁。1樹的根本(gēnběn)概念2樹的存儲(cúnchǔ)結(jié)構(gòu)3二叉樹4二叉樹的存儲(cúnchǔ)結(jié)構(gòu)5二叉樹的遍歷6線索二叉樹第五頁，共41頁。6.1樹的根本(gēnběn)概念

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

樹形表示法

借助自然界中一棵倒置的樹的形狀來表示數(shù)據(jù)元素之間層次關(guān)系的方法。第八頁，共41頁。1.結(jié)點(diǎn)(jiédiǎn)的度：2.樹的度：3.葉結(jié)點(diǎn)(jiédiǎn)：4.分支結(jié)點(diǎn)(jiédiǎn):5.層次(céngcì)的定義:JIHGFEACXB該結(jié)點(diǎn)擁有的子樹的數(shù)目。樹中結(jié)點(diǎn)度的最大值。度為0的結(jié)點(diǎn).度非0的結(jié)點(diǎn).根結(jié)點(diǎn)為第一層,假設(shè)某結(jié)點(diǎn)在第i層,那么其孩子結(jié)點(diǎn)(假設(shè)存在)為第i+1層.四.基本名詞術(shù)語第1層第2層第3層第九頁，共41頁。7.樹林(森林(sēnlín)):m0棵不相交的樹組成的樹的集合.8.

樹的有序性:6.樹的深度(shēndù):樹中結(jié)點(diǎn)(jiédiǎn)所處的最大層次數(shù).假設(shè)樹中結(jié)點(diǎn)的子樹的相對位置不能隨意改變,那么稱該樹為有序樹，否那么稱該樹為無序樹。JIHGFEACXB深度為3的樹第十頁，共41頁。二叉樹的根本(gēnběn)形態(tài)：(空)根根左子樹根右子樹根左子樹右子樹

6.2

二叉樹第十一頁，共41頁。二.兩種特殊(tèshū)形態(tài)的二叉樹

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

若一棵二叉樹中只有最下面兩層的結(jié)點(diǎn)的度可以小于2,并且最下面一層的結(jié)點(diǎn)(葉結(jié)點(diǎn))都依次排列在該層從左至右的位置上。這樣的二叉樹為完全二叉樹.2.完全二叉樹第十二頁，共41頁。1.一棵非空二叉樹的第i層最多有2i–1個結(jié)點(diǎn)(jiédiǎn)(i1)。三.二叉樹的性質(zhì)2.深度(shēndù)為h的非空二叉樹最多有2h-1個結(jié)點(diǎn).3.假設(shè)非空二叉樹有n0個葉結(jié)點(diǎn)(jiédiǎn),有n2個度為2的結(jié)點(diǎn)(jiédiǎn),那么n0=n2+14.

具有n個結(jié)點(diǎn)的完全二叉樹的深度h=log2n+1.第十三頁，共41頁。二叉樹的存儲(cúnchǔ)結(jié)構(gòu)一.二叉樹的順序存儲結(jié)構(gòu)(jiégòu)12345678910ABCDEFGHIJBT[1:15]123456789101112131415ABCDEFGHIJ

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

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

IABCDEFGHIJ2.一般(yībān)二叉樹的順序存儲結(jié)構(gòu)第十五頁，共41頁。

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

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

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

lchild

與rchild分別為指向左、右子樹的指針域.ABCDEFGIJABCDEFGJIT^^^^^^^^^^第十七頁，共41頁。6.3.3

二叉樹的遍歷第十八頁，共41頁。二.前序遍歷(biànlì)第十九頁，共41頁。三.中序遍歷(biànlì)第二十頁，共41頁。四.后序(hòuxù)遍歷第二十一頁，共41頁。ABCDKFGIJEH前序遍歷(biànlì)序列:A,B,D,K,J,G,C,F,I,E,H中序遍歷(biànlì)序列:D,B,G,J,K,A,F,I,E,C,H后序遍歷(biànlì)序列:D,G,J,K,B,E,I,F,H,C,A按層次遍歷序列:

A,B,C,D,K,F,H,J,I,G,E例第二十二頁，共41頁。6.3.2線索(xiànsuǒ)二叉樹1.何謂線索(xiànsuǒ)二叉樹？遍歷結(jié)果是求得結(jié)點(diǎn)的一個線性序列。指向該線性序列“前驅(qū)〞和“后繼〞的指針，稱“線索(xiànsuǒ)〞；包含“線索(xiànsuǒ)〞的存儲結(jié)構(gòu)，稱為“線索(xiànsuǒ)鏈表〞；與其相應(yīng)的二叉樹，稱為“線索(xiànsuǒ)二叉樹〞；對二叉樹以某種次序遍歷，使其變?yōu)榫€索(xiànsuǒ)二叉樹的過程，稱為“線索(xiànsuǒ)化〞。第二十三頁，共41頁。2.線索鏈表中結(jié)點(diǎn)(jiédiǎn)的結(jié)構(gòu)在二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)中增加(zēngjiā)兩個標(biāo)志域，并規(guī)定：lchildLTagdataRTagrchild其中(qízhōng)：LTag=0lchild域指示結(jié)點(diǎn)的左孩子1lchild域指示結(jié)點(diǎn)的前驅(qū)RTag=0rchild域指示結(jié)點(diǎn)的右孩子1rchild域指示結(jié)點(diǎn)的后繼第二十四頁，共41頁。二叉樹二叉線索(xiànsuǒ)存儲表示typedefenum{Link,Thread}PointerThr;//Link==0:指針(zhǐzhēn)，Thread==1:線索typedefstructBiThrNode{TElemTypedata;StructBiThrNode*lchild,*rchild;//左右孩子指針(zhǐzhēn)PointerThrLTag,RTag;//左右標(biāo)志}BiThrNode,*BiThrTree;第二十五頁，共41頁。3.線索(xiànsuǒ)二叉樹圖例線索二叉樹及其存儲(cúnchǔ)結(jié)構(gòu)〔a〕中序線索二叉樹〔b〕中序線索鏈表1234567010020131141050161171thrt0

1第二十六頁，共41頁。如何(rúhé)在線索樹中找結(jié)點(diǎn)的后繼？結(jié)合中序線索樹假設(shè)其右標(biāo)志為“1〞，右鏈?zhǔn)蔷€索，右鏈直接指示(zhǐshì)了結(jié)點(diǎn)的后繼；假設(shè)其右標(biāo)志為“0〞，右鏈?zhǔn)侵羔?，其后繼為右子樹中最左下的結(jié)點(diǎn)。1234567第二十七頁，共41頁。如何在線索(xiànsuǒ)樹中找結(jié)點(diǎn)的前驅(qū)？結(jié)合中序線索樹假設(shè)其左標(biāo)志為“1〞，左鏈為線索，直接指示其前驅(qū)(qiánqū)；假設(shè)其左標(biāo)志為“0〞，左子樹中最右下的結(jié)點(diǎn)為其前驅(qū)(qiánqū)。1234567第二十八頁，共41頁。線索(xiànsuǒ)鏈表的中序遍歷算法StatusIOTraver_T(BiThrTreeT,Status(*Visit)(TElemTypee)){//T指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的左鏈lchild指向根結(jié)點(diǎn)，中序遍歷

//二叉線索(xiànsuǒ)樹T的非遞歸算法，對每個數(shù)據(jù)元素調(diào)用函數(shù)Visit。p=T->lchild;//p指向根結(jié)點(diǎn)while(p!=T){//空樹或遍歷結(jié)束時，p==Twhile(p->LTag==Link)p=p->lchild;if(!Visit(p->data))returnERROR;//訪問其左子樹為空的結(jié)點(diǎn)while(p->RTag==Thread&&p->rchild!=T){p=p->rchild;Visit(p->data);}//訪問后繼結(jié)點(diǎn)p=p->rchild;}returnOK;}//IOTraver_T010020131141050161171T011第二十九頁，共41頁。6.4.2森林(sēnlín)和二叉樹的轉(zhuǎn)換1.樹和二叉樹的對應(yīng)關(guān)系由于二叉樹和樹都可用二叉鏈表作為存儲(cúnchǔ)結(jié)構(gòu)，那么以二叉鏈表作為媒介可導(dǎo)出樹與二叉樹之間的一個對應(yīng)關(guān)系。第三十頁，共41頁。第二十七頁，共41頁。typedefstructBiThrNode{對森林進(jìn)行先序遍歷，獲得的先序序列(xùliè)是：2〕訪問森林中第一棵樹的根結(jié)點(diǎn)；第二十二頁，共41頁。D,B,G,J,K,A,F,I,E,C,H第二十四頁，共41頁。假設(shè)把森林中第二棵樹的根結(jié)點(diǎn)看成(kànchénɡ)是第一棵樹的根結(jié)點(diǎn)的兄弟，那么同樣可導(dǎo)出森林和二叉樹的對應(yīng)關(guān)系。右訪問樹中每個結(jié)點(diǎn)。4二叉樹的存儲(cúnchǔ)結(jié)構(gòu)如何在線索(xiànsuǒ)樹中找結(jié)點(diǎn)的前驅(qū)？那么稱該樹為無序樹。樹轉(zhuǎn)換(zhuǎnhuàn)為二叉樹方法：while(p->RTag==Thread&&p->rchild!=T)第三十八頁，共41頁。4〕以根結(jié)點(diǎn)為軸心，將整個樹順時針轉(zhuǎn)45°。第三十一頁，共41頁。樹轉(zhuǎn)換(zhuǎnhuàn)為二叉樹方法：1〕對每個孩子進(jìn)行(jìnxíng)從左到右的排序；2〕在兄弟之間加一條連線；3〕對每個結(jié)點(diǎn)，除了左孩子外，去除其與其余孩子之間的聯(lián)系；4〕以根結(jié)點(diǎn)為軸心，將整個樹順時針轉(zhuǎn)45°。第三十二頁，共41頁。ABCDEGHFIaABCDEGHFIbABCDEGHFIcABCDEGHFId第三十三頁，共41頁。2.森林和二叉樹的對應(yīng)關(guān)系從樹的二叉鏈表表示的定義可知，任何一棵和樹對應(yīng)的二叉樹，其右子樹必空。假設(shè)把森林中第二棵樹的根結(jié)點(diǎn)看成(kànchénɡ)是第一棵樹的根結(jié)點(diǎn)的兄弟，那么同樣可導(dǎo)出森林和二叉樹的對應(yīng)關(guān)系。第三十四頁，共41頁。第三十五頁，共41頁。BCDEGHFIaBCDEGHFIbBCDEGHFIcBCDEGHFId第三十六頁，共41頁。條件：森林和二叉樹的對應(yīng)關(guān)系設(shè)森林F=(T1,T2,…,Tn);T1=(root，t11,t12,…,t1m);二叉樹B=(LBT,Node(root),RBT);由森林轉(zhuǎn)換成二叉樹的轉(zhuǎn)換規(guī)那么(nàme)為:假設(shè)F=Φ，那么(nàme)B=Φ;否那么(nàme)，由Root(T1)對應(yīng)得到Node(root);由(t11,t12,…,t1m)對應(yīng)得到LBT;由(T2,T3,…,Tn)對應(yīng)得到RBT。由二叉樹轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)那么(nàme)為:假設(shè)B=Φ,那么(nàme)F=Φ;否那么(nàme)，由Node(root)對應(yīng)得到Root(T1);由LBT對應(yīng)得到(t11,t12,…，t1m);T1除根以外所構(gòu)成的森林由RBT對應(yīng)得到(T2,T3,…,Tn)；除T1之外的森林第三十七頁，共41頁。6.4.3樹和森林(