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

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

2、(樹)所有非空樹都只有一個特定節(jié)點，稱為樹的根(根)。在N1中，剩馀節(jié)點可被徐璐不相交的m(m0)個有限集T1，T2，Tm整除。其中，每個集本身都是一棵樹，稱為根子樹。特征：非空樹至少有一個節(jié)點根。樹中的每個子樹都是徐璐不相交的集合。第6，2020/7/31頁，a，僅具有根節(jié)點的樹，具有子樹的樹，根，子樹，第7，2020/7/31頁，樹數(shù)據(jù)關(guān)系：如果d為空集，則稱為空樹如果d僅包含一個數(shù)據(jù)元素，則關(guān)系r為空集。如果d包含多個數(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。其中，每個子集本身是符合牙齒定義的樹，稱為根根的子樹，每個子樹的根Xi是根根根根。第8，2020/7/31頁，默認操作：InitTree(初始條件：樹t存在)。操作結(jié)果：如果t是空樹，則返回TRUE否則返回FALSE。第9，2020/7/31頁，樹狀目錄(t)；初始條件：樹t存在。操作結(jié)果：返回t的深度。根(t)；初始條件：樹t存在。操作結(jié)果：返回t的根。值(t，cur _ e)；初始條件：具有樹t，cur_e是t的節(jié)點。操作結(jié)果：返回cur_e的值。第10，2020/7/31頁，父級(t，cur _ e)；初始條件：具有樹t，cur_e是t的節(jié)點。操作結(jié)果：如果cur_e是t的根以外的

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

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

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

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

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