中山大學(xué)樹和二叉樹最終版.ppt

1、，第1，2020/7/31頁(yè)，第6章樹和二叉樹，了解學(xué)習(xí)目標(biāo)樹和二叉樹類型定義，了解樹和二叉樹結(jié)構(gòu)差異。熟記二叉樹的主要特征，掌握他們的證明方法。掌握二叉樹的各種巡回算法，通過算法實(shí)現(xiàn)二叉樹其他工作的靈活性。精通多種二叉樹存儲(chǔ)結(jié)構(gòu)和算法構(gòu)建。第2頁(yè)，2020/7/31頁(yè)，重點(diǎn)和難點(diǎn)重點(diǎn)：遍歷和應(yīng)用二叉樹和樹。困難：構(gòu)建實(shí)現(xiàn)二叉樹和樹的各種任務(wù)的遞歸算法知識(shí)點(diǎn)樹的類型定義，二叉樹類型定義二叉樹存儲(chǔ)是指二叉樹遍歷和其他任務(wù)的實(shí)現(xiàn)。第3，2020/7/31頁(yè)，樹案例和特征，社會(huì)組織結(jié)構(gòu)家族系譜計(jì)算機(jī)的目錄配置，說明層次，一對(duì)多邏輯關(guān)系，第4頁(yè)，第5頁(yè)，2020/7/31頁(yè)，6.1樹定義和基本術(shù)語(yǔ)，樹

2、(樹)所有非空樹都只有一個(gè)特定節(jié)點(diǎn)，稱為樹的根(根)。在N1中，剩馀節(jié)點(diǎn)可被徐璐不相交的m(m0)個(gè)有限集T1，T2，Tm整除。其中，每個(gè)集本身都是一棵樹，稱為根子樹。特征：非空樹至少有一個(gè)節(jié)點(diǎn)根。樹中的每個(gè)子樹都是徐璐不相交的集合。第6，2020/7/31頁(yè)，a，僅具有根節(jié)點(diǎn)的樹，具有子樹的樹，根，子樹，第7，2020/7/31頁(yè)，樹數(shù)據(jù)關(guān)系：如果d為空集，則稱為空樹如果d僅包含一個(gè)數(shù)據(jù)元素，則關(guān)系r為空集。如果d包含多個(gè)數(shù)據(jù)元素，則R=H，H為以下二元關(guān)系：(1) D具有唯一名為root的數(shù)據(jù)元素根，關(guān)系H下沒有前兆。(2) n1，剩余數(shù)據(jù)元素m(m0)徐璐不相交(非空)有限集T1，T2，

3、Tm。其中，每個(gè)子集本身是符合牙齒定義的樹，稱為根根的子樹，每個(gè)子樹的根Xi是根根根根。第8，2020/7/31頁(yè)，默認(rèn)操作：InitTree(初始條件：樹t存在)。操作結(jié)果：如果t是空樹，則返回TRUE否則返回FALSE。第9，2020/7/31頁(yè)，樹狀目錄(t)；初始條件：樹t存在。操作結(jié)果：返回t的深度。根(t)；初始條件：樹t存在。操作結(jié)果：返回t的根。值(t，cur _ e)；初始條件：具有樹t，cur_e是t的節(jié)點(diǎn)。操作結(jié)果：返回cur_e的值。第10，2020/7/31頁(yè)，父級(jí)(t，cur _ e)；初始條件：具有樹t，cur_e是t的節(jié)點(diǎn)。操作結(jié)果：如果cur_e是t的根以外的

4、節(jié)點(diǎn)，則返回父節(jié)點(diǎn)，否則返回“空”。LeftChild(T，cur _ e)；初始條件：具有樹t，cur_e是t的節(jié)點(diǎn)。操作結(jié)果：如果cur_e是t的非葉節(jié)點(diǎn)，則返回最左側(cè)的孩子，否則返回“空”。RightSibling(T，cur _ e)；初始條件：具有樹t，cur_e是t的節(jié)點(diǎn)。作業(yè)結(jié)果：如果cur_e有右兄弟，則返回右兄弟，否則返回“空”。第11，2020/7/31頁(yè)，traversetree (t，visit()；初始條件：節(jié)點(diǎn)作業(yè)的應(yīng)用程序節(jié)目函數(shù)，樹T存在。操作結(jié)果：對(duì)t中的每個(gè)節(jié)點(diǎn)依次調(diào)用函數(shù)visit()一次、一次或多次。如果Visit()失敗，則操作失敗。Assign(T，

5、cur_e，value)；初始條件：具有樹t，cur_e是t的節(jié)點(diǎn)。操作結(jié)果：為節(jié)點(diǎn)cur_e指定值value。ClearTree(初始條件：存在樹t)。任務(wù)結(jié)果：將樹t清空為空樹。頁(yè)面12，2020/7/31，insert child(初始條件：樹t存在，p指向t中的節(jié)點(diǎn)之一，1ip表示節(jié)點(diǎn)的角度)。操作結(jié)果：刪除T中P指向的節(jié)點(diǎn)的第I個(gè)子樹。Adttree、第13頁(yè)、2020/7/31頁(yè)、主術(shù)語(yǔ)節(jié)點(diǎn)(節(jié)點(diǎn)):包含指向數(shù)據(jù)元素和子樹的多個(gè)分支。節(jié)點(diǎn)度數(shù)：節(jié)點(diǎn)擁有的子樹的數(shù)量。葉：角度為零的節(jié)點(diǎn)。分支節(jié)點(diǎn)：角度不是零牙齒的節(jié)點(diǎn)。樹的度：一棵樹中每個(gè)節(jié)點(diǎn)的最大度值。兒童：節(jié)點(diǎn)的子樹的根稱為該節(jié)點(diǎn)

6、的孩子。父節(jié)點(diǎn)：子節(jié)點(diǎn)的父節(jié)點(diǎn)。兄弟：同一個(gè)雙親的孩子叫徐璐兄弟。祖先：從根部點(diǎn)到該節(jié)點(diǎn)通過的分支中的所有節(jié)點(diǎn)。后代：以一個(gè)節(jié)點(diǎn)為根的子樹的所有節(jié)點(diǎn)稱為該節(jié)點(diǎn)的后代。第14頁(yè)，2020/7/31頁(yè)，節(jié)點(diǎn)層次結(jié)構(gòu)(level):從根節(jié)點(diǎn)，根是一層，根孩子是二層。表哥：那位雙親是同一層結(jié)上的徐璐表親。深度：樹中節(jié)點(diǎn)的最大層次。有序樹：從左到右查看樹中節(jié)點(diǎn)的每個(gè)子樹時(shí)，都有順序。也就是說，不能徐璐交換。無序樹：可以交換樹中節(jié)點(diǎn)的每個(gè)子樹，將樹視為從左到右沒有順序。樹系：m (m0)徐璐不相交的樹集合。第15頁(yè)，2020/7/31頁(yè)，節(jié)點(diǎn)a的度：節(jié)點(diǎn)b的度：節(jié)點(diǎn)m的度：葉：節(jié)點(diǎn)a的孩子：節(jié)點(diǎn)b的孩子：

7、節(jié)點(diǎn)I的父：節(jié)點(diǎn)l的父：節(jié)點(diǎn)b C，D凹面表達(dá)：類似書目；顯示嵌套括號(hào)：顯示光表。樹，頁(yè)面17，2020/7/31，樹和線性結(jié)構(gòu)比較，頁(yè)面18，2020/7/31，62二叉樹，二叉樹定義n=0節(jié)點(diǎn)的限制，根節(jié)點(diǎn)，左側(cè)子樹，右側(cè)子樹，特征每個(gè)節(jié)點(diǎn)最多包含兩個(gè)子樹(即不存在的程度大于2的節(jié)點(diǎn))。二叉樹子樹區(qū)分左右，不能隨機(jī)顛倒順序。基本形式：A、空二叉樹、僅具有根節(jié)點(diǎn)的二叉樹、右側(cè)子樹為空、左側(cè)子樹為空、左側(cè)和右側(cè)子樹為空。第20頁(yè)，2020/7/31頁(yè)，二叉樹屬性，屬性1:二叉樹I，證明：I=1，僅根節(jié)點(diǎn)，顯然在設(shè)置I=k時(shí)成立，最大2k-1節(jié)點(diǎn)i=k 1時(shí)的最大節(jié)點(diǎn)數(shù)： 證明：n1從T設(shè)置為中

8、間1的節(jié)點(diǎn)數(shù)，摘要點(diǎn)數(shù)：n=n0 n1 N2 (1)。此外，除根節(jié)點(diǎn)外，所有節(jié)點(diǎn)都只有一個(gè)父節(jié)點(diǎn)。 也就是說，如果僅進(jìn)入一個(gè)分支，B是分支數(shù)，則N=B 1=N1。Page 23，2020/7/31，幾種茄子特殊形式的二叉樹，二叉樹總深度為K，2k-1節(jié)點(diǎn)二叉樹。屬性每個(gè)層中的節(jié)點(diǎn)數(shù)是最大節(jié)點(diǎn)數(shù)。所有分支節(jié)點(diǎn)的角度均為2。樹葉節(jié)點(diǎn)都在同一層。Page 24，2020/7/31，從上到下對(duì)完全二叉樹的整個(gè)二叉樹節(jié)點(diǎn)編號(hào)。深度為K，具有N個(gè)節(jié)點(diǎn)的二叉樹(整個(gè)二叉樹)全部(僅當(dāng)每個(gè)節(jié)點(diǎn)對(duì)應(yīng)K深度的二叉樹總數(shù)時(shí))。特征葉節(jié)點(diǎn)只能出現(xiàn)在級(jí)別最大的兩層。前面k-1層的節(jié)點(diǎn)全部為“全部”，層K的節(jié)點(diǎn)集中在左側(cè)。第25頁(yè)，2020/7/31頁(yè)，判斷是否完全二叉樹，說明原因。思想：整