版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
第6章樹與二叉樹數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第1頁。校長一系二系三系六系教務(wù)處科研處總務(wù)處601602教務(wù)科603ABCD…………張三李四王五…例1…工廠數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第2頁。(根目錄)
\f1f2f3fnd1d2dm………例2f11f12f1kd11d12…………數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第3頁。例3數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第4頁。1樹的基本概念2樹的存儲結(jié)構(gòu)3二叉樹4二叉樹的存儲結(jié)構(gòu)5二叉樹的遍歷6線索二叉樹數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第5頁。
6.1
樹的基本概念
樹是由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的子樹。遞歸定義一.樹的定義數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第6頁。2021/3/117JIHGFEACXBA的第1棵子樹A的第3棵子樹A的第2棵子樹二.樹(邏輯上)的特點(diǎn)1.有且僅有一個結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn),該結(jié)點(diǎn)為樹的根結(jié)點(diǎn)。2.除了根結(jié)點(diǎn)外,每個結(jié)點(diǎn)有且僅有一個直接前驅(qū)結(jié)點(diǎn)。3.包括根結(jié)點(diǎn)在內(nèi),每個結(jié)點(diǎn)可以有多個后繼結(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第7頁。JIHGFEACXB4.
樹形表示法
借助自然界中一棵倒置的樹的形狀來表示數(shù)據(jù)元素之間層次關(guān)系的方法。數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第8頁。1.
結(jié)點(diǎn)的度:2.
樹的度:3.
葉結(jié)點(diǎn):4.
分支結(jié)點(diǎn):5.
層次的定義:JIHGFEACXB該結(jié)點(diǎn)擁有的子樹的數(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ù)語第1層第2層第3層數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第9頁。7.
樹林(森林):m0棵不相交的樹組成的樹的集合.8.
樹的有序性:6.
樹的深度:樹中結(jié)點(diǎn)所處的最大層次數(shù).
若樹中結(jié)點(diǎn)的子樹的相對位置不能隨意改變,則稱該樹為有序樹,否則稱該樹為無序樹。JIHGFEACXB深度為3的樹數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第10頁。二叉樹的基本形態(tài):(空)根根左子樹根右子樹根左子樹右子樹
6.2
二叉樹數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第11頁。二.兩種特殊形態(tài)的二叉樹
若一棵二叉樹中的結(jié)點(diǎn),或者為葉結(jié)點(diǎn),或者具有兩棵非空子樹,并且葉結(jié)點(diǎn)都集中在二叉樹的最下面一層.這樣的二叉樹為滿二叉樹.1.滿二叉樹
若一棵二叉樹中只有最下面兩層的結(jié)點(diǎn)的度可以小于2,并且最下面一層的結(jié)點(diǎn)(葉結(jié)點(diǎn))都依次排列在該層從左至右的位置上。這樣的二叉樹為完全二叉樹.2.完全二叉樹數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第12頁。1.一棵非空二叉樹的第i層最多有2i–1個結(jié)點(diǎn)(i1)。三.二叉樹的性質(zhì)2.
深度為h的非空二叉樹最多有2h-1個結(jié)點(diǎn).3.
若非空二叉樹有n0個葉結(jié)點(diǎn),有n2個度為2的結(jié)點(diǎn),
則n0=n2+1
4.
具有n個結(jié)點(diǎn)的完全二叉樹的深度h=log2n+1.數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第13頁。
二叉樹的存儲結(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.完全二叉樹的順序存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第14頁。12345678910ABCDEFGHIJ111213BT[1:15]123456789101112131415ABCDEFGHJ
IABCDEFGHIJ2.一般二叉樹的順序存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第15頁。2021/3/1116
對于一般二叉樹,只須在二叉樹中“添加”一些實(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]中。數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第16頁。二.二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)(二叉鏈表)鏈結(jié)點(diǎn)的構(gòu)造為lchilddatarchild
其中,data為數(shù)據(jù)域
lchild
與rchild分別為指向左、右子樹的指針域.ABCDEFGIJABCDEFGJIT^^^^^^^^^^數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第17頁。6.3.3
二叉樹的遍歷數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第18頁。二.前序遍歷數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第19頁。三.中序遍歷數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第20頁。四.后序遍歷數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第21頁。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)二叉樹ppt全文共42頁,當(dāng)前為第22頁。2021/3/11236.3.2線索二叉樹1.何謂線索二叉樹?遍歷結(jié)果是求得結(jié)點(diǎn)的一個線性序列。指向該線性序列“前驅(qū)”和“后繼”的指針,稱“線索”;包含“線索”的存儲結(jié)構(gòu),稱為“線索鏈表”;與其相應(yīng)的二叉樹,稱為“線索二叉樹”;對二叉樹以某種次序遍歷,使其變?yōu)榫€索二叉樹的過程,稱為“線索化”。數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第23頁。2.線索鏈表中結(jié)點(diǎn)的結(jié)構(gòu)在二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)中增加兩個標(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)二叉樹ppt全文共42頁,當(dāng)前為第24頁。2021/3/1125二叉樹二叉線索存儲表示typedefenum{Link,Thread}PointerThr;
//Link==0:指針,Thread==1:線索typedefstructBiThrNode{TElemTypedata;StructBiThrNode*lchild,*rchild;
//左右孩子指針
PointerThrLTag,RTag;//左右標(biāo)志}BiThrNode,*BiThrTree;數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第25頁。2021/3/11263.線索二叉樹圖例
線索二叉樹及其存儲結(jié)構(gòu)(a)中序線索二叉樹(b)中序線索鏈表1234567010020131141050161171thrt0
1數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第26頁。2021/3/1127如何在線索樹中找結(jié)點(diǎn)的后繼?結(jié)合中序線索樹若其右標(biāo)志為“1”,右鏈?zhǔn)蔷€索,右鏈直接指示了結(jié)點(diǎn)的后繼;若其右標(biāo)志為“0”,右鏈?zhǔn)侵羔?,其后繼為右子樹中最左下的結(jié)點(diǎn)。1234567數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第27頁。2021/3/1128如何在線索樹中找結(jié)點(diǎn)的前驅(qū)?結(jié)合中序線索樹
若其左標(biāo)志為“1”,左鏈為線索,直接指示其前驅(qū);若其左標(biāo)志為“0”,左子樹中最右下的結(jié)點(diǎn)為其前驅(qū)。1234567數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第28頁。2021/3/1129線索鏈表的中序遍歷算法StatusIOTraver_T(BiThrTreeT,Status(*Visit)(TElemTypee)){//T指向頭結(jié)點(diǎn),頭結(jié)點(diǎn)的左鏈lchild指向根結(jié)點(diǎn),中序遍歷
//二叉線索樹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數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第29頁。2021/3/11306.4.2森林和二叉樹的轉(zhuǎn)換1.樹和二叉樹的對應(yīng)關(guān)系由于二叉樹和樹都可用二叉鏈表作為存儲結(jié)構(gòu),則以二叉鏈表作為媒介可導(dǎo)出樹與二叉樹之間的一個對應(yīng)關(guān)系。數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第30頁。2021/3/1131數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第31頁。2021/3/1132樹轉(zhuǎn)換為二叉樹方法:1)對每個孩子進(jìn)行從左到右的排序;2)在兄弟之間加一條連線;3)對每個結(jié)點(diǎn),除了左孩子外,去除其與其余孩子之間的聯(lián)系;4)以根結(jié)點(diǎn)為軸心,將整個樹順時針轉(zhuǎn)45°。數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第32頁。2021/3/1133ABCDEGHFIaABCDEGHFIbABCDEGHFIcABCDEGHFId數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第33頁。2021/3/11342.森林和二叉樹的對應(yīng)關(guān)系從樹的二叉鏈表表示的定義可知,任何一棵和樹對應(yīng)的二叉樹,其右子樹必空。若把森林中第二棵樹的根結(jié)點(diǎn)看成是第一棵樹的根結(jié)點(diǎn)的兄弟,則同樣可導(dǎo)出森林和二叉樹的對應(yīng)關(guān)系。數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第34頁。2021/3/1135數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第35頁。2021/3/1136BCDEGHFIaBCDEGHFIbBCDEGHFIcBCDEGHFId數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第36頁。2021/3/1137已知條件:森林和二叉樹的對應(yīng)關(guān)系設(shè)森林F=(T1,T2,…,Tn);T1=(root,t11,t12,…,t1m);
二叉樹B=(LBT,Node(root),RBT);由森林轉(zhuǎn)換成二叉樹的轉(zhuǎn)換規(guī)則為:若F=Φ,則B=Φ;否則,由Root(T1)對應(yīng)得到Node(root);
由(t11,t12,…,t1m)對應(yīng)得到LBT;
由(T2,T3,…,Tn)對應(yīng)得到RBT。由二叉樹轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為:若B=Φ,則F=Φ;否則,由Node(root)對應(yīng)得到Root(T1);
由LBT對應(yīng)得到(t11,t12,…,t1m);T1除根以外所構(gòu)成的森林由RBT對應(yīng)得到(T2,T3,…,Tn);除T1之外的森林?jǐn)?shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第37頁。2021/3/11386.4.3樹和森林的遍歷1.樹的遍歷:有三條搜索路徑先根(序)遍歷:若樹不空,則先訪問根結(jié)點(diǎn),然后依次先根遍歷各棵子樹。后根(序)遍歷:若樹不空,則先依次后根遍歷各棵子樹,然后訪問根結(jié)點(diǎn)。按層次遍歷:若樹不空,則自上而下自左至右訪問樹中每個結(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)二叉樹ppt全文共42頁,當(dāng)前為第38頁。2021/3/1139
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024藝術(shù)品拍賣與宣傳推廣綜合服務(wù)合同3篇
- 2025年度環(huán)保設(shè)施PPP項(xiàng)目合作合同范本3篇
- 2025年度智能車庫產(chǎn)權(quán)交易合同范本4篇
- 2025年度文化產(chǎn)業(yè)園開發(fā)與租賃合同3篇
- 2025年企事業(yè)單位食堂承包與托管全面合作協(xié)議12篇
- 2025年度廠長任期項(xiàng)目投資與風(fēng)險管理合同3篇
- 2025年中投中財基金管理有限公司招聘筆試參考題庫含答案解析
- 2025年中化集團(tuán)中化能源物流公司招聘筆試參考題庫含答案解析
- 二零二五版美容院專業(yè)護(hù)膚技術(shù)研發(fā)與轉(zhuǎn)讓合同4篇
- 二零二五版門窗安裝工程環(huán)保驗(yàn)收合同2篇
- MT/T 199-1996煤礦用液壓鉆車通用技術(shù)條件
- GB/T 6144-1985合成切削液
- GB/T 10357.1-2013家具力學(xué)性能試驗(yàn)第1部分:桌類強(qiáng)度和耐久性
- 第三方在線糾紛解決機(jī)制(ODR)述評,國際商法論文
- 第5章-群體-團(tuán)隊(duì)溝通-管理溝通
- 腎臟病飲食依從行為量表(RABQ)附有答案
- 深基坑-安全教育課件
- 園林施工管理大型園林集團(tuán)南部區(qū)域養(yǎng)護(hù)標(biāo)準(zhǔn)圖例
- 排水許可申請表
- 低血糖的觀察和護(hù)理課件
- 計量檢定校準(zhǔn)技術(shù)服務(wù)合同協(xié)議書
評論
0/150
提交評論