數(shù)據(jù)結(jié)構(gòu)二叉樹第1頁(yè)，共44頁(yè)，2023年，2月20日，星期六數(shù)據(jù)結(jié)構(gòu)請(qǐng)安靜§6.1樹的定義和基本術(shù)語(yǔ)第2頁(yè)，共44頁(yè)，2023年，2月20日，星期六

1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)

2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)3、對(duì)數(shù)據(jù)的操作：檢索、排序、插入、刪除、修改A．線性結(jié)構(gòu)

B．非線性結(jié)構(gòu)A順序存儲(chǔ)

B鏈?zhǔn)酱鎯?chǔ)線性表?xiàng)ｊ?duì)列樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)主要問題DataStructure樹的邏輯結(jié)構(gòu)??一對(duì)多（1：n）第3頁(yè)，共44頁(yè)，2023年，2月20日，星期六五子棋游戲……..……..…...…...…...…...樹的實(shí)例第4頁(yè)，共44頁(yè)，2023年，2月20日，星期六/(root)libuseretcbinmathdsswyintaoxieStack.cppQueue.cppTree.cpp人類的族譜各種社會(huì)關(guān)系各類分類編碼編譯程序的語(yǔ)法樹Internet中的DNS（域名系統(tǒng)）UNIX文件系統(tǒng)結(jié)構(gòu)樹的實(shí)例第5頁(yè)，共44頁(yè)，2023年，2月20日，星期六

樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)定義：樹(tree)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集，其中：n=0，稱為空樹有且僅有一個(gè)特殊的結(jié)點(diǎn)，稱為樹的根(root)當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的子集T1,T2,……Tm，其中每一個(gè)集合本身又是一棵樹，稱為根的子樹(subtree)特點(diǎn)：樹中至少有一個(gè)結(jié)點(diǎn)——根樹的定義是遞歸定義的，各子樹也滿足上面定義。樹的定義第6頁(yè)，共44頁(yè)，2023年，2月20日，星期六~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結(jié)構(gòu)樹型結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素

(無前驅(qū))

根結(jié)點(diǎn)

(無前驅(qū))最后一個(gè)數(shù)據(jù)元素

(無后繼)多個(gè)葉子結(jié)點(diǎn)

(無后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、一個(gè)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、多個(gè)后繼)第7頁(yè)，共44頁(yè)，2023年，2月20日，星期六A只有根結(jié)點(diǎn)的樹ABCDEFGHIJKLM有子樹的樹根子樹葉子葉子葉子第8頁(yè)，共44頁(yè)，2023年，2月20日，星期六ADT

Tree{數(shù)據(jù)對(duì)象D:D是具有相同特性的數(shù)據(jù)元素的集合

數(shù)據(jù)關(guān)系R:若D為空集，則稱為空樹 否則:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root；

(2)當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定義的樹，稱為根root的子樹

基本操作：

查找類操作

插入類操作

刪除類操作}ADT

Tree樹的抽象數(shù)據(jù)類型定義第9頁(yè)，共44頁(yè)，2023年，2月20日，星期六基本操作：TreeEmpty(T)

初始條件：樹T已存在

操作結(jié)果：空樹，返回TRUE;否則FALSETreeDepth(T)

初始條件：樹T已存在

操作結(jié)果：返回T的深度查找類：Root(T)

初始條件：樹T已存在操作結(jié)果：返回T的根Value(T,cur_e)

初始條件：樹T已存在,cur_e是T中結(jié)點(diǎn)操作結(jié)果：返回cur_e的值Parent(T,cur_e)

初始條件：樹T已存在,cur_e是T中結(jié)點(diǎn)操作結(jié)果：若cur_e是T中非根結(jié)點(diǎn),返回其雙親;否則,返回空樹的抽象數(shù)據(jù)類型定義第10頁(yè)，共44頁(yè)，2023年，2月20日，星期六LeftChild(T,cur_e)

初始條件：樹T已存在,cur_e是T中結(jié)點(diǎn)操作結(jié)果：若cur_e是T中非葉子結(jié)點(diǎn),返回其最左孩子;否則,返回空RightChild(T,cur_e)

初始條件：樹T已存在,cur_e是T中結(jié)點(diǎn)操作結(jié)果：若cur_e是T中非葉子結(jié)點(diǎn),返回其最右孩子;否則,返回空TraverseTree(T,visit())初始條件：樹T已存在

操作結(jié)果：按某種次序?qū)的每個(gè)元素調(diào)用函數(shù)visit()查找類：基本操作：樹的抽象數(shù)據(jù)類型定義第11頁(yè)，共44頁(yè)，2023年，2月20日，星期六插入類：InsertChild(&T,&p,i,c)

初始條件：樹T存在,p指向T中結(jié)點(diǎn),1≤i

≤p指結(jié)點(diǎn)度+1,非空樹c與T不相交操作結(jié)果：將以c為根的樹插入為T中p指結(jié)點(diǎn)的第i棵子樹CreateTree(&T,definition)

初始條件：definition給出樹的定義操作結(jié)果：按definition構(gòu)造樹TAssign(T,cur_e,value)

初始條件：樹T已存在,cur_e是T中結(jié)點(diǎn)操作結(jié)果：結(jié)點(diǎn)cur_e賦值為valueInitTree(&T)

操作結(jié)果：構(gòu)造空樹T基本操作：樹的抽象數(shù)據(jù)類型定義第12頁(yè)，共44頁(yè)，2023年，2月20日，星期六DeleteChild(&T,&p,i)

初始條件：樹T存在,p指向T中結(jié)點(diǎn),1≤i

≤p指結(jié)點(diǎn)度操作結(jié)果：刪除T中p指結(jié)點(diǎn)的第i棵子樹ClearTree(&T)

初始條件：樹T已存在

操作結(jié)果：將樹T清為空樹DestroyTree(&T)

初始條件：樹T已存在

操作結(jié)果：銷毀樹T刪除類：基本操作：樹的抽象數(shù)據(jù)類型定義第13頁(yè)，共44頁(yè)，2023年，2月20日，星期六結(jié)點(diǎn)(node)——表示樹中的元素，以及構(gòu)造元素之間關(guān)系的指針結(jié)點(diǎn)的度(degree)——結(jié)點(diǎn)擁有的子樹數(shù)樹的度——一棵樹中最大的結(jié)點(diǎn)度數(shù)葉子(leaf)——度為0的結(jié)點(diǎn)，終端結(jié)點(diǎn)分支結(jié)點(diǎn)——度不為0的結(jié)點(diǎn)，非終端結(jié)點(diǎn)孩子(child)——結(jié)點(diǎn)子樹的根稱為該結(jié)點(diǎn)的孩子雙親(parents)——孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的雙親樹的基本術(shù)語(yǔ)第14頁(yè)，共44頁(yè)，2023年，2月20日，星期六兄弟(sibling)——同一雙親的孩子祖先——從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)子孫（后裔）——一個(gè)節(jié)點(diǎn)所有子樹上的節(jié)點(diǎn)節(jié)點(diǎn)的層次(level)——從根結(jié)點(diǎn)算起，根為第一層，它的孩子為第二層……堂兄弟——同一層的結(jié)點(diǎn)深度(depth)——樹中結(jié)點(diǎn)的最大層次數(shù),又稱高度樹的基本術(shù)語(yǔ)第15頁(yè)，共44頁(yè)，2023年，2月20日，星期六森林(forest)——m(m0)棵互不相交的樹的集合無序樹——子樹之間不存在確定的次序關(guān)系有序樹——各子樹從左至右有嚴(yán)格的次序，不能互換，最左邊的節(jié)點(diǎn)稱為第一個(gè)孩子，最右邊的節(jié)點(diǎn)稱為最后一個(gè)孩子任何一棵非空樹是一個(gè)二元組

Tree=（root，F(xiàn)）其中：root

被稱為根結(jié)點(diǎn)

F

被稱為子樹森林樹的基本術(shù)語(yǔ)第16頁(yè)，共44頁(yè)，2023年，2月20日，星期六樹的表示JIACBDHGFEKLM圖形表示法嵌套集合表示法廣義表表示法凹入表示法第17頁(yè)，共44頁(yè)，2023年，2月20日，星期六GCKLEFBMHJIDA嵌套集合表示法

圖型表示法

樹的表示JIACBDHGFEKLM第18頁(yè)，共44頁(yè)，2023年，2月20日，星期六(A(B(E(k,L),F),C(G),D(H(M),I,J)))括號(hào)(廣義表)表示法

圖型表示法

樹的表示JIACBDHGFEKLM第19頁(yè)，共44頁(yè)，2023年，2月20日，星期六圖型表示法

ABCDEFGHIJKLM凹入表示法

樹的表示JIACBDHGFEKLM第20頁(yè)，共44頁(yè)，2023年，2月20日，星期六結(jié)點(diǎn)A的度：結(jié)點(diǎn)B的度：結(jié)點(diǎn)M的度：葉子：結(jié)點(diǎn)A的孩子：結(jié)點(diǎn)B的孩子：結(jié)點(diǎn)I的雙親：結(jié)點(diǎn)L的雙親：結(jié)點(diǎn)B，C，D為結(jié)點(diǎn)K，L為樹的度：結(jié)點(diǎn)A的層次：結(jié)點(diǎn)M的層次：樹的深度：結(jié)點(diǎn)F，G為結(jié)點(diǎn)A是結(jié)點(diǎn)F，G的結(jié)點(diǎn)F，G是A結(jié)點(diǎn)的ABCDEFGHIJKLM320B,C,DE,F3144K,L,F,G,M,I,JDE兄弟兄弟堂兄弟祖先子孫請(qǐng)同學(xué)回答第21頁(yè)，共44頁(yè)，2023年，2月20日，星期六數(shù)據(jù)結(jié)構(gòu)請(qǐng)安靜§6.2二叉樹第22頁(yè)，共44頁(yè)，2023年，2月20日，星期六6.2二叉樹為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè)“叉”的樹？二叉樹的結(jié)構(gòu)最簡(jiǎn)單，規(guī)律性最強(qiáng)；可以證明，所有樹都能轉(zhuǎn)換為唯一的一棵二叉樹與其對(duì)應(yīng)，不失一般性。6.2.1二叉樹的定義6.2.2二叉樹的性質(zhì)6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)第23頁(yè)，共44頁(yè)，2023年，2月20日，星期六定義：二叉樹是n(n0)個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛?n=0)，或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成特點(diǎn)每個(gè)結(jié)點(diǎn)至多有二棵子樹(不存在度大于2的結(jié)點(diǎn))子樹有左、右之分，且其次序不能任意顛倒基本形態(tài)空二叉樹左、右子樹均非空DRL只有根結(jié)點(diǎn)二叉樹D右子樹為空DL左子樹為空DR二叉樹的定義第24頁(yè)，共44頁(yè)，2023年，2月20日，星期六有關(guān)二叉樹下列說法正確的是（）A．二叉樹的度為2 B．一棵二叉樹的度可以小于2C．二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2D．二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為2問：一棵度為2的樹和一棵二叉樹有何區(qū)別？試分別畫出具有3個(gè)結(jié)點(diǎn)的樹和3個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。二叉樹的定義第25頁(yè)，共44頁(yè)，2023年，2月20日，星期六二叉樹的抽象數(shù)據(jù)類型定義ADTBinaryTree{數(shù)據(jù)對(duì)象D:數(shù)據(jù)關(guān)系R:基本操作P：}ADTBinaryTree若D=Φ，則R=Φ；若D≠Φ，則R={H}；存在二元關(guān)系：①root唯一//關(guān)于根的說明②Dl∩Dr=Φ//關(guān)于子樹不相交的說明③……//關(guān)于二元關(guān)系的說明

④……

//關(guān)于左子樹和右子樹的說明D是具有相同特性的數(shù)據(jù)元素的集合。//至少有20個(gè)第26頁(yè)，共44頁(yè)，2023年，2月20日，星期六性質(zhì)1：在二叉樹的第i

層上至多有___個(gè)結(jié)點(diǎn)(i≥1)

第一層：第二層：第三層：第i層：只有一個(gè)根結(jié)點(diǎn)：21-1=20=1；二叉樹上每個(gè)結(jié)點(diǎn)至多有兩棵子樹，則第i層的結(jié)點(diǎn)數(shù)=2i-1

。二叉樹的性質(zhì)最多：202

=21=2；最多：212

=22=4；2i-1第27頁(yè)，共44頁(yè)，2023年，2月20日，星期六二叉樹的性質(zhì)思考：具有n個(gè)節(jié)點(diǎn)的二叉樹的深度最小________，最大________∵高度h的二叉樹最多有2h-1個(gè)節(jié)點(diǎn)（性質(zhì)2）∴n≤2h-1∴h≥

log2(n+1)

解答：性質(zhì)2：123114589121367101415深度為k的二叉樹上至多含____個(gè)結(jié)點(diǎn)（k≥1）證明：基于上一條性質(zhì)，深度為k的二叉樹上的結(jié)點(diǎn)數(shù)至多為

20+21++2k-1=2k-1

2k-1第28頁(yè)，共44頁(yè)，2023年，2月20日，星期六性質(zhì)3：對(duì)任何一棵二叉樹T，如果其葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1證明：設(shè)n1為度為1的節(jié)點(diǎn)數(shù)∵二叉樹中所有節(jié)點(diǎn)的度≤2∴結(jié)點(diǎn)總數(shù)n=n0+n1+n2∵除根節(jié)點(diǎn)外，其余節(jié)點(diǎn)都是“別人”的孩子又∵葉子（n0）沒有孩子！∴所有的孩子數(shù)n-1=n1+2n2∴

n=n1+2n2+1=n0+n1+n2∴n0=n2+1123456二叉樹的性質(zhì)第29頁(yè)，共44頁(yè)，2023年，2月20日，星期六滿二叉樹定義：特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)123114589121367101415滿二叉樹及其編號(hào)指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹特殊形式的二叉樹第30頁(yè)，共44頁(yè)，2023年，2月20日，星期六完全二叉樹定義：深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為~特點(diǎn)葉子結(jié)點(diǎn)只可能在最后層和倒數(shù)第二層上出現(xiàn)特殊形式的二叉樹第31頁(yè)，共44頁(yè)，2023年，2月20日，星期六1231145891213671014151231145891267101234567123456üü完全二叉樹中可能有度為1的結(jié)點(diǎn)嗎？?第32頁(yè)，共44頁(yè)，2023年，2月20日，星期六性質(zhì)4：123114589126710證明：設(shè)完全二叉樹的深度為k根據(jù)第二條性質(zhì)得

n≤2k-1

且(2k-1-1)+1≤n即log2n<k≤log2n+1因?yàn)閗只能是整數(shù)，因此，k=

log2n

+1。

完全二叉樹性質(zhì)具有n個(gè)結(jié)點(diǎn)的完全二叉樹深度為_________log2n+1第33頁(yè)，共44頁(yè)，2023年，2月20日，星期六性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號(hào)，則對(duì)任一結(jié)點(diǎn)i(1in)，有：

(1)如果i=1,則結(jié)點(diǎn)i是二叉樹的根,如果i>1,則其雙親是i/2(2)如果2i>n,則結(jié)點(diǎn)i無左孩子;如果2in,則其左孩子是2i(3)如果2i+1>n,則結(jié)點(diǎn)i無右孩子;如果2i+1n,則其右孩子是2i+1123114589126710完全二叉樹性質(zhì)第34頁(yè)，共44頁(yè)，2023年，2月20日，星期六二叉樹性質(zhì)小結(jié)二叉樹的第i

層上至多有2i-1

個(gè)結(jié)點(diǎn)

性質(zhì)1：性質(zhì)2：深度為k的二叉樹上至多含2k-1個(gè)結(jié)點(diǎn)性質(zhì)3：對(duì)任何一棵二叉樹T，如果其葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1

性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為

log2n+1

性質(zhì)5：對(duì)完全二叉樹有：(1)如果i>1,則其雙親是i/2(2)如果2i>n,則結(jié)點(diǎn)i無左孩子;否則其左孩子是2i(3)如果2i+1>n,則結(jié)點(diǎn)i無右孩子;否則其右孩子是2i+1第35頁(yè)，共44頁(yè)，2023年，2月20日，星期六課堂討論：①二叉樹是不是樹的特殊情況？答：不是！它是單獨(dú)定義的一種樹狀結(jié)構(gòu)，并非一般樹的特例。它的子樹有順序規(guī)定，分為左子樹和右子樹。不能隨意顛倒。②：滿二叉樹和完全二叉樹有什么區(qū)別？答：滿二叉樹是完全二叉樹的一個(gè)特例。完全二叉樹最底層卻允許在右邊缺少連續(xù)若干個(gè)結(jié)點(diǎn)。第36頁(yè)，共44頁(yè)，2023年，2月20日，星期六5.深度為9的完全二叉樹中至少有

個(gè)結(jié)點(diǎn)。Ａ)２9

Ｂ)２8

Ｃ)９Ｄ)２9－14.深度為k的二叉樹的結(jié)點(diǎn)總數(shù)，最多為

個(gè)。Ａ)２k-1

Ｂ)log2k

Ｃ)２k－１Ｄ)２k3.樹Ｔ中各結(jié)點(diǎn)的度的最大值稱為樹Ｔ的

。Ａ)高度Ｂ)層次Ｃ)深度Ｄ)度√√√課堂討論：第37頁(yè)，共44頁(yè)，2023年，2月20日，星期六二叉樹的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)第38頁(yè)，共44頁(yè)，2023年，2月20日，星期六一、完全二叉樹實(shí)現(xiàn)：按結(jié)點(diǎn)層次編號(hào)，依次存放二叉樹中的數(shù)據(jù)元素（用數(shù)組實(shí)現(xiàn)）ABCDEFGHI[1][2][3][4][5][6][7][8][9]ABCGEIDHF問：順序存儲(chǔ)后能否唯一對(duì)應(yīng)一顆二叉樹？有規(guī)律：下標(biāo)值為i的結(jié)點(diǎn)，其左孩子的下標(biāo)值必為2i，其右孩子的下標(biāo)值必為2i＋1（即性質(zhì)5）二叉樹的存儲(chǔ)結(jié)構(gòu)——順序存儲(chǔ)結(jié)構(gòu)第39頁(yè)，共44頁(yè)，2023年，2月20日，星期六不是完全二叉樹怎么辦？特點(diǎn)：結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中浪費(fèi)空間,k層需要長(zhǎng)度多少的數(shù)組？abcdefg

1234567891011abcde0000fg該存儲(chǔ)結(jié)構(gòu)能否反映結(jié)點(diǎn)之間的關(guān)系？?0二叉樹的存儲(chǔ)結(jié)構(gòu)——順序存儲(chǔ)結(jié)構(gòu)適于滿二叉樹和完全二叉樹補(bǔ)“虛結(jié)點(diǎn)”！第40頁(yè)，共44頁(yè)，2023年，2月20日，星期六ABCDEF思考：將該二叉樹進(jìn)行順序存儲(chǔ)二叉樹的存儲(chǔ)結(jié)構(gòu)——順序存儲(chǔ)結(jié)構(gòu)第41頁(yè)，共44頁(yè)，2023年，2月20日，星期六思考：請(qǐng)畫出下列二叉樹的圖