第6章樹與二叉樹-wenkub
2022-11-04 15:07:05 本頁面
【正文】 ENT (i) 是節(jié)點 ?i/2? 。 特點：每一層上的節(jié)點數(shù)都達到了最大節(jié)點數(shù)。 ?性質 (2)：深度為 k的二叉樹至多有 2k1個節(jié)點（ k ≥ 1）。child) 遍歷樹 tree各元素，并用visit代表的操作處理元素數(shù)據(jù) 在樹 tree中求節(jié)點 elem的父節(jié)點，并將結果放入parent中 說明 :在樹 tree中求節(jié)點 parent的第 order個子節(jié)點，并將結果放入 child中 treeSetChild(tree,parent,order,child) } 在樹 tree中設置節(jié)點parent的第 order個子節(jié)點，待設置的值已經放入 child中 二叉樹 二叉樹的定義與基本運算 二叉樹是一個集合 T；它可以是空集 ， 也可以是一個由節(jié)點組成的有限集 。tree) treeEmpty(tree) treeWidth(tree) 創(chuàng)建一棵樹 tree 銷毀一棵已有的樹tree 創(chuàng)建一棵樹 tree 判樹是否為空 求樹的度 treeDepth(tree) treeRoot(tree) treeInsert(amp。 () 對應于 D{r}的劃分 ,H{r,x1,r,x2,…,r,xm}有惟一的一個劃分H1,H2,…,Hm(m0),對任意 j?k(1≤ j,k≤ m)有Hj∩ Hk=Ф,且對任意的 i(1≤ i≤ m),Hi是 Di上的二元關系 ,(Di,{Hi})是一棵符合本定義的樹 ,稱為根 r的子樹。 AB C DE F GHBGFHDECAABCDEFHG( b ) 文式圖表示方法( a ) 倒置的樹形圖表示方法 ( c ) 凹入表的表示方法圖6 . 2 樹形結構中分支與層次特性的表示本書中描述 樹形結構 的方式 樹的基本術語 ?節(jié)點 ?節(jié)點的度 ?葉子或終端節(jié)點 ?非終端節(jié)點或分支節(jié)點 ?內部節(jié)點 ?樹的度 ?孩子 ?雙親 ?兄弟 ?祖先 ?子孫 ?節(jié)點的層次 ?樹的深度或高度 ?有序樹 ?無序樹 ?森林 樹的 ADT ADT Tree { 數(shù)據(jù)對象為 D: D是具有相同特性的數(shù)據(jù)元素的集合 數(shù)據(jù)間的關系 R: (1) 若 D為空集 ,則稱為空樹 。這樣的節(jié)點序列稱為從 根到節(jié)點 e的一條路徑 。 除了 首元 （ 唯一存在 ，在樹形結構中稱為 “根” 節(jié)點）沒有前驅元素以外，樹中其他所有元素（ 節(jié)點 ）都有且只有一個直接前驅元素（ 父 節(jié)點）；直接后繼元素則沒有限制：沒有直接后繼元素的節(jié)點（ 葉 節(jié)點）可以有多個；存在直接后繼元素的節(jié)點，其直接后繼元素的個數(shù)也可以有多個。 樹的定義與表示 ? 樹的定義 ： 樹的 邏輯結構 可以這樣描述： 樹是包含 N(N0)個節(jié)點的 有窮集合 D，且在 D上定義了一個 關系 R，關系 R滿足以下條件： (1) 有且僅有一個 節(jié)點 e0?D， 它對于關系R來說 沒有前驅 ， 節(jié)點 e0稱作樹的 根 。 樹的遞歸定義： 樹是由一個或多個節(jié)點組成的有限集 T，它滿足下面兩個條件： (1)有一個特定的節(jié)點稱之為 根 。 (2) 若 D為非空集且僅含有一個數(shù)據(jù)元素 ,則 R為空集 ,樹只包含一個根節(jié)點 。 幾種基本操作 : treeCreate(amp。tree,elem) treeDelete(amp。 同時 ， 集合 T具有下列的性質： (1) 如果 T是空集 ， 則稱 T是空的二叉樹 。 ?性質 (3)：對任何一棵二叉樹 T，如果其葉節(jié)點數(shù)為 n0，度為 2的節(jié)點數(shù)為 n2，則n0=n2+1。 完全二叉樹： （ 1）葉子節(jié)點只可能在層次最大的兩層上出現(xiàn)；
教學課件相關推薦
鄂ICP備17016276號-1