《樹和二叉樹》教學課件

《樹和二叉樹》幻燈片本課件PPT僅供大家學習使用學習完請自行刪除，謝謝！本課件PPT僅供大家學習使用學習完請自行刪除，謝謝！本課件PPT僅供大家學習使用學習完請自行刪除，謝謝！本課件PPT僅供大家學習使用學習完請自行刪除，謝謝！《樹和二叉樹》幻燈片本課件PPT僅供大家學習使用課程回憶什么是稀疏矩陣稀疏矩陣表示廣義表定義課程回憶什么是稀疏矩陣本講目錄樹的定義和根本術語二叉樹樹的定義樹的基本術語二叉樹的定義二叉樹的性質二叉樹的存儲結構本講目錄樹的定義和根本術語樹的定義二叉樹的定本講重點、難點重點二叉樹的定義二叉樹的性質二叉樹的存儲構造難點二叉樹的定義二叉樹的性質本講重點、難點重點樹的定義和根本術語樹的定義和根本術語二叉樹樹的定義樹的基本術語樹的定義和根本術語樹的定義和根本術語樹的定義樹的定義樹型結構是一類重要的非線性數據結構。直觀看來樹是以分支關系定義的層次結構。樹型結構在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機構都可用樹來形象表示。樹在計算機領域中也有著廣泛的應用，如在數據庫系統(tǒng)中，可用樹來組織信息；在分析算法的行為時，可用樹來描述其執(zhí)行過程。樹的定義樹型結構是一類重要的非線性數據結構。樹的定義例如：家族樹樹的定義例如：家族樹樹棧和隊列數組和廣義表線性表和廣義表數據結構……線性表廣義表棧隊列……樹的定義例如本書的目錄樹棧和隊列數組和廣義表線性表和廣義表數據結構……線性表廣義表樹的定義樹的定義樹是由n(n0)個結點組成的有限集合。如果n=0，稱為空樹；如果n>0，那么:有一個特定的稱之為根(root)的結點，它只有后繼，但沒有前驅；除根以外的其它結點劃分為m(m>0)個互不相交的有限集合T1,T2,…,Tm。每個集合本身又是一棵樹，并且稱之為根的子樹(subTree)。每棵子樹的根結點有且僅有一個直接前驅，但可以有0個或多個后繼。樹的定義是遞歸的。樹的定義樹的定義樹的定義例如圖(a)是一棵空樹，沒有結點圖(b)是一棵只有根結點的樹，根結點是A圖(c)是一棵有13個結點的樹，其中A是根結點三個互不相交的子集：T1={B,E,F,K,L},T2={C,G},T3={D,H,I,J,M}樹的定義例如圖(a)是一棵空樹，沒有結點樹的定義抽象數據類型樹的定義ADTTree{數據對象D：D是具有一樣特性的數據元素的集合。數據關系R：假設D為空集，那么稱為空樹；否那么:(1)在D中存在唯一的稱為根的數據元素root,(2)當n>1時，其余結點可分為m(m>0)個互不相交的有限集T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定義的樹，稱為根root的子樹。根本操作P：(見教材)}ADTTree樹的定義抽象數據類型樹的定義樹的表示樹的邏輯表示方法有多種，常見的有：樹形圖表示法嵌套集合表示法〔文氏圖表示法〕凹入表示法廣義表表示法樹的定義樹的表示樹的定義樹的根本術語根本術語結點：數據元素+假設干指向子樹的分支結點的度：分支的個數〔或子樹的個數〕葉子結點〔終端結點〕：度為零的結點分支結點〔非終端結點〕：度不等于零的結點樹的度：樹中所有結點的度的最大值孩子結點：結點的子樹的根結點為該結點的孩子結點雙親結點：與孩子結點相對應的結點兄弟結點：同一個雙親的孩子結點之間的互稱祖先結點：從根結點起到該結點所經分支上的所有結點子孫結點：以某結點為根的子樹中的任意結點樹的根本術語根本術語樹的根本術語根本術語層次：從根結點起，根結點為第一層，跟的孩子為第二層，依次類推假設根結點的層次為1,第l層的結點的子樹根結點的層次為l+1堂兄弟：雙親在同一層的結點互稱深度：樹中葉子結點所在的最大層次有序樹：子樹之間存在確定的次序關系無序樹：子樹之間不存在確定的次序關系森林：是m〔m≥0〕棵互不相交的樹的集合。任何一棵非空樹是一個二元組Tree=〔root，F(xiàn)〕其中：root被稱為根結點，F(xiàn)被稱為子樹森林CGFHIJMDEKLBFAroot樹的根本術語根本術語CGFHIJMDEKLBFAroot二叉樹樹的定義和根本術語二叉樹二叉樹的定義二叉樹的性質二叉樹的存儲結構二叉樹樹的定義和根本術語二叉樹的定義二叉樹的定義二叉樹的定義二叉樹是由n(n>=0)個結點的有限集合構成，此集合或者為空集，或者由一個根結點及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹。二叉樹的每個結點至多只有兩棵子樹〔結點的度最多為2〕。二叉樹的子樹有左右之分，其次序不能任意顛倒。根結點右子樹左子樹EFHKCBADGEF二叉樹的定義二叉樹的定義根結點右子樹左子樹EFHKCBADG二叉樹的定義抽象數據類型二叉樹的定義ADTBinaryTree{數據對象D：D是具有一樣特性的數據元素的集合。數據關系R：假設D為空集，那么稱為空二叉樹；否那么:(1)在D中存在唯一的稱為根的數據元素root(2)當n>1時，其余結點可分為2個互不相交的有限集Dl，Dr(3)假設Dl，Dr都不為空集，那么Dl，Dr本身又是一棵符合本定義的二叉樹，稱為根root的左右子樹。根本操作P：(見教材)}ADTBinaryTree二叉樹的定義抽象數據類型二叉樹的定義二叉樹的定義二叉樹的5種根本形態(tài)AABABACB

(b)根和空的左右子樹

(c)根和左子樹(d)根和右子樹(e)根和左右子樹

(a)空二叉樹二叉樹的定義二叉樹的5種根本形態(tài)AABABACB(5×3！=30棵二叉樹的定義例如：由三個結點組成的二叉樹的根本類型有幾種？由三個結點組成的二叉樹的根本形態(tài)有5種。如果這三個結點分別是A,B,C。那么可以組成幾棵二叉樹？5×3！=30棵二叉樹的定義例如：由三個結點組成的二叉樹的根二叉樹的性質二叉樹的性質性質1：在二叉樹的第i層上至多有2i-1個結點。(i≥1)證明：用歸納法證明：歸納基：i=1層時，只有一個根結點，2i-1=20=1；歸納假設：假設對所有的j，1≤ji，命題成立;歸納證明：二叉樹上每個結點至多有兩棵子樹，那么第i層的結點數=2i-22=2i-1。按照題意，二叉樹除最后一層，其余每一層上的結點都有兩個孩子結點，那么每一層均比上一層的結點個數多一倍。按照等比數列的定義，每一項都可以看作是相應每一層上的結點個數，那么，ai=ai*qi-1=2i-1二叉樹的性質二叉樹的性質用歸納法證明：按照題意，二叉樹除最后二叉樹的性質性質2：深度為k的二叉樹上至多含2k-1個結點〔k≥1〕證明：基于上一條性質，深度為k

的二叉樹上的結點數至多為

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

二叉樹的性質性質2：深度為k的二叉樹上至多含2k-1個結點〔二叉樹的性質性質3：對任何一棵二叉樹，假設它含有n0個葉子結點、n2個度為2的結點，那么必存在關系式：n0=n2+1證明：設二叉樹上結點總數n=n0+n1+n2又二叉樹上分支總數B=n1+2n2而B=n-1=n0+n1+n2–1由此，n0=n2+1二叉樹的性質性質3：對任何一棵二叉樹，假設它含有n0個葉子滿二叉樹：指的是深度為k且含有2k-1個結點的二叉樹。完全二叉樹：樹中所含的n個結點和滿二叉樹中編號為1

至n

的結點一一對應。123456789101112131415abcdefghij特點：每一層上的結點數都是最大結點數特點：葉子結點只能在層次最大的兩層出現(xiàn)任意結點，假設其右分支下的子孫最大層數為L,那么左分支下的子孫的最大層次為L或L+1兩類特殊的二叉樹二叉樹的性質滿二叉樹：指的是深度為k且含有2k-1個結點的二叉樹。完全二性質4：具有n個結點的完全二叉樹的深度為

log2n+1證明：設完全二叉樹的深度為k

那么根據第二條性質得2k-1≤n<2k即k-1≤log2n<k

因為k

只能是整數，因此，k=log2n

+1二叉樹的性質性質4：具有n個結點的完全二叉樹的深度為證明：設完全二叉樹性質5：假設對含n個結點的完全二叉樹從上到下且從左至右進展1至n的編號，那么對完全二叉樹中任意一個編號為i的結點：假設i=1，那么該結點是二叉樹的根，無雙親,否那么，編號為i/2的結點為其雙親結點;假設2i>n，那么該結點無左孩子，

否那么，編號為2i的結點為其左孩子結點；假設2i+1>n，那么該結點無右孩子結點，

否那么，編號為2i+1的結點為其右孩子結點。二叉樹的性質性質5：假設對含n個結點的完全二叉樹從上到二叉樹的二叉樹的存儲構造順序存儲構造它是用一組連續(xù)的存儲單元存儲二叉樹的數據元素。必須把二叉樹的所有結點安排成為一個恰當的序列，結點在這個序列中的相互位置能反映出結點之間的邏輯關系，用編號的方法：從樹根起，自上層至下層，每層自左至右的給所有結點編號。順序存儲表示#defineMAX_TREE_SIZE100typedefintTElemType;typedefTElemTypeSqBiTree[MAX_TREE_SIZE]；SqBiTreebt;二叉樹的存儲構造順序存儲構造二叉樹的存儲構造例如：完全二叉樹的數組表示二叉樹的存儲構造例如：完全二叉樹的數組表示二叉樹的存儲構造例如：一般二叉樹的數組表示00000二叉樹的存儲構造例如：一般二叉樹的數組表示00000二叉樹的存儲構造順序存儲構造的缺點由于一般二叉樹必須仿照完全二叉樹那樣存儲，可能會浪費很多存儲空間，單支樹就是一個極端情況。假設經常需要插入與刪除樹中結點時，順序存儲方式需要大量移動數據。二叉樹的存儲構造順序存儲構造的缺點二叉樹的存儲構造鏈式存儲構造二叉鏈表二叉鏈表構造：數據域、左指針域、右指針域

lchilddatarchild二叉鏈表存儲表示：typedefcharTElemType;typedefstructBiTNode{TElemTypedata;structBiTNode*lchild，*rchild；//左右孩子指針}BiTNode，*BiTree；二叉樹的存儲構造鏈式存儲構造lchilddat二叉樹的存儲構造鏈式存儲構造三叉鏈表三叉鏈表構造：數據域、左指針域、右指針域、雙親指針域

lchilddataparentrchild思考：二叉樹的三叉鏈表存儲表示如何定義？二叉樹的存儲構造鏈式存儲構造lchild二叉樹的存儲構造二叉樹鏈式存儲構造例如二叉樹的存儲構造二叉樹鏈式存儲構造例如教學內容樹的定義和根本術語二叉樹樹的定義樹的基本術語二叉樹的定義二叉樹的性質二叉樹的存儲結構教學內容樹的定義和根本術語樹的定義二叉樹的定本講總結為什么說樹的定義是遞歸的？二叉樹的性質有哪些？二叉樹的順序存儲構造有什么缺點？本講總結為什么說樹的定義是遞歸的？上機實驗實驗14-1建立一棵含有n個結點的二叉樹，采用二叉鏈表存儲〔ex6-1.c〕上機實驗實驗14-1ThankYou!ThankYou!《樹和二叉樹》幻燈片本課件PPT僅供大家學習使用學習完請自行刪除，謝謝！本課件PPT僅供大家學習使用學習完請自行刪除，謝謝！本課件PPT僅供大家學習使用學習完請自行刪除，謝謝！本課件PPT僅供大家學習使用學習完請自行刪除，謝謝！《樹和二叉樹》幻燈片本課件PPT僅供大家學習使用課程回憶什么是稀疏矩陣稀疏矩陣表示廣義表定義課程回憶什么是稀疏矩陣本講目錄樹的定義和根本術語二叉樹樹的定義樹的基本術語二叉樹的定義二叉樹的性質二叉樹的存儲結構本講目錄樹的定義和根本術語樹的定義二叉樹的定本講重點、難點重點二叉樹的定義二叉樹的性質二叉樹的存儲構造難點二叉樹的定義二叉樹的性質本講重點、難點重點樹的定義和根本術語樹的定義和根本術語二叉樹樹的定義樹的基本術語樹的定義和根本術語樹的定義和根本術語樹的定義樹的定義樹型結構是一類重要的非線性數據結構。直觀看來樹是以分支關系定義的層次結構。樹型結構在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機構都可用樹來形象表示。樹在計算機領域中也有著廣泛的應用，如在數據庫系統(tǒng)中，可用樹來組織信息；在分析算法的行為時，可用樹來描述其執(zhí)行過程。樹的定義樹型結構是一類重要的非線性數據結構。樹的定義例如：家族樹樹的定義例如：家族樹樹棧和隊列數組和廣義表線性表和廣義表數據結構……線性表廣義表棧隊列……樹的定義例如本書的目錄樹棧和隊列數組和廣義表線性表和廣義表數據結構……線性表廣義表樹的定義樹的定義樹是由n(n0)個結點組成的有限集合。如果n=0，稱為空樹；如果n>0，那么:有一個特定的稱之為根(root)的結點，它只有后繼，但沒有前驅；除根以外的其它結點劃分為m(m>0)個互不相交的有限集合T1,T2,…,Tm。每個集合本身又是一棵樹，并且稱之為根的子樹(subTree)。每棵子樹的根結點有且僅有一個直接前驅，但可以有0個或多個后繼。樹的定義是遞歸的。樹的定義樹的定義樹的定義例如圖(a)是一棵空樹，沒有結點圖(b)是一棵只有根結點的樹，根結點是A圖(c)是一棵有13個結點的樹，其中A是根結點三個互不相交的子集：T1={B,E,F,K,L},T2={C,G},T3={D,H,I,J,M}樹的定義例如圖(a)是一棵空樹，沒有結點樹的定義抽象數據類型樹的定義ADTTree{數據對象D：D是具有一樣特性的數據元素的集合。數據關系R：假設D為空集，那么稱為空樹；否那么:(1)在D中存在唯一的稱為根的數據元素root,(2)當n>1時，其余結點可分為m(m>0)個互不相交的有限集T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定義的樹，稱為根root的子樹。根本操作P：(見教材)}ADTTree樹的定義抽象數據類型樹的定義樹的表示樹的邏輯表示方法有多種，常見的有：樹形圖表示法嵌套集合表示法〔文氏圖表示法〕凹入表示法廣義表表示法樹的定義樹的表示樹的定義樹的根本術語根本術語結點：數據元素+假設干指向子樹的分支結點的度：分支的個數〔或子樹的個數〕葉子結點〔終端結點〕：度為零的結點分支結點〔非終端結點〕：度不等于零的結點樹的度：樹中所有結點的度的最大值孩子結點：結點的子樹的根結點為該結點的孩子結點雙親結點：與孩子結點相對應的結點兄弟結點：同一個雙親的孩子結點之間的互稱祖先結點：從根結點起到該結點所經分支上的所有結點子孫結點：以某結點為根的子樹中的任意結點樹的根本術語根本術語樹的根本術語根本術語層次：從根結點起，根結點為第一層，跟的孩子為第二層，依次類推假設根結點的層次為1,第l層的結點的子樹根結點的層次為l+1堂兄弟：雙親在同一層的結點互稱深度：樹中葉子結點所在的最大層次有序樹：子樹之間存在確定的次序關系無序樹：子樹之間不存在確定的次序關系森林：是m〔m≥0〕棵互不相交的樹的集合。任何一棵非空樹是一個二元組Tree=〔root，F(xiàn)〕其中：root被稱為根結點，F(xiàn)被稱為子樹森林CGFHIJMDEKLBFAroot樹的根本術語根本術語CGFHIJMDEKLBFAroot二叉樹樹的定義和根本術語二叉樹二叉樹的定義二叉樹的性質二叉樹的存儲結構二叉樹樹的定義和根本術語二叉樹的定義二叉樹的定義二叉樹的定義二叉樹是由n(n>=0)個結點的有限集合構成，此集合或者為空集，或者由一個根結點及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹。二叉樹的每個結點至多只有兩棵子樹〔結點的度最多為2〕。二叉樹的子樹有左右之分，其次序不能任意顛倒。根結點右子樹左子樹EFHKCBADGEF二叉樹的定義二叉樹的定義根結點右子樹左子樹EFHKCBADG二叉樹的定義抽象數據類型二叉樹的定義ADTBinaryTree{數據對象D：D是具有一樣特性的數據元素的集合。數據關系R：假設D為空集，那么稱為空二叉樹；否那么:(1)在D中存在唯一的稱為根的數據元素root(2)當n>1時，其余結點可分為2個互不相交的有限集Dl，Dr(3)假設Dl，Dr都不為空集，那么Dl，Dr本身又是一棵符合本定義的二叉樹，稱為根root的左右子樹。根本操作P：(見教材)}ADTBinaryTree二叉樹的定義抽象數據類型二叉樹的定義二叉樹的定義二叉樹的5種根本形態(tài)AABABACB

(b)根和空的左右子樹

(c)根和左子樹(d)根和右子樹(e)根和左右子樹

(a)空二叉樹二叉樹的定義二叉樹的5種根本形態(tài)AABABACB(5×3！=30棵二叉樹的定義例如：由三個結點組成的二叉樹的根本類型有幾種？由三個結點組成的二叉樹的根本形態(tài)有5種。如果這三個結點分別是A,B,C。那么可以組成幾棵二叉樹？5×3！=30棵二叉樹的定義例如：由三個結點組成的二叉樹的根二叉樹的性質二叉樹的性質性質1：在二叉樹的第i層上至多有2i-1個結點。(i≥1)證明：用歸納法證明：歸納基：i=1層時，只有一個根結點，2i-1=20=1；歸納假設：假設對所有的j，1≤ji，命題成立;歸納證明：二叉樹上每個結點至多有兩棵子樹，那么第i層的結點數=2i-22=2i-1。按照題意，二叉樹除最后一層，其余每一層上的結點都有兩個孩子結點，那么每一層均比上一層的結點個數多一倍。按照等比數列的定義，每一項都可以看作是相應每一層上的結點個數，那么，ai=ai*qi-1=2i-1二叉樹的性質二叉樹的性質用歸納法證明：按照題意，二叉樹除最后二叉樹的性質性質2：深度為k的二叉樹上至多含2k-1個結點〔k≥1〕證明：基于上一條性質，深度為k

的二叉樹上的結點數至多為

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

二叉樹的性質性質2：深度為k的二叉樹上至多含2k-1個結點〔二叉樹的性質性質3：對任何一棵二叉樹，假設它含有n0個葉子結點、n2個度為2的結點，那么必存在關系式：n0=n2+1證明：設二叉樹上結點總數n=n0+n1+n2又二叉樹上分支總數B=n1+2n2而B=n-1=n0+n1+n2–1由此，n0=n2+1二叉樹的性質性質3：對任何一棵二叉樹，假設它含有n0個葉子滿二叉樹：指的是深度為k且含有2k-1個結點的二叉樹。完全二叉樹：樹中所含的n個結點和滿二叉樹中編號為1

至n

的結點一一對應。123456789101112131415abcdefghij特點：每一層上的結點數都是最大結點數特點：葉子結點只能在層次最大的兩層出現(xiàn)任意結點，假設其右分支下的子孫最大層數為L,那么左分支下的子孫的最大層次為L或L+1兩類特殊的二叉樹二叉樹的性質滿二叉樹：指的是深度為k且含有2k-1個結點的二叉樹。完全二性質4：具有n個結點的完全二叉樹的深度為

log2n+1證明：設完全二叉樹的深度為k

那么根據第二條性質得2k-1≤n<2k即k-1≤log2n<k

因為k

只能是整數，因此，k=log2n

+1二叉樹的性質性質4：具有n個結點的完全二叉樹的深度為證明：設完全二叉樹性質5：假設對含n個結點的完全二叉樹從上到下且從左至右進展1至n的編號，那么對完全二叉樹中任意一個編號為i的結點：假設i=1，那么該結點是二叉樹的根，無雙親,否那么，編號為i/2的結點為其雙親結點;假設2i>n，那么該結點無左孩子，

否那么，編號為2i的結點為其左孩子結點；假設2i+1>n，那么該結點無右孩子結點，

否那么，編號為2i+1的結點為其右孩子結點。二叉樹的性質性質5：假設對含n個結點的完全二叉樹從上到二叉樹的二叉樹的存儲構造順序存儲構造它是用一組連續(xù)的存儲單元存儲二叉樹的數據元素。必須把二叉樹的所有結點安排成為一個恰當的序列，結點在這個序列中的相互位置能反映出結點之間的邏輯關系，用編號的方法