[理學]數(shù)據(jù)結構7樹形結構-wenkub
2022-10-31 21:14:47 本頁面
【正文】 A時遵守同樣的規(guī)則 。 例 ：求該樹的先序遍歷次序 。 樹的遍歷運算是指按某種方式訪問樹中的每一個結點 ， 且每一個結點只被訪問一次 。 例如高度為 3的滿 2次樹 (每個結點的度最大為 2)， 總結點數(shù) = (231)/(21)=7 1 2 3 4 5 6 7 性質 4： 具有 n 個結點的 m 次樹的最小高度為 ?logm(n(m1)+1)?。 假設對于第 (i1)層 (i＞ 1)命題成立 ， 即度為 m 的樹中第 (i1)層上至多有mi2個結點 。 A B C D E F G H I J K L M ?除樹根結點外 ， 每個結點與指向它的一個分支一一對應 。 反之 ， 只要給 n 棵獨立的樹加上一個結點 ， 并把這 n 棵樹作為該結點的子樹 ， 則森林就變成了樹 。 ⒍ 有序樹和無序樹： 若樹中各結點的子樹是按照一定的次序從左向右安排的 ， 且相對次序是不能隨意變換的 ， 則稱為 有序樹 ， 否則稱為 無序樹 。 ⒌ 結點的層次和樹的高度 樹中的每個結點都處在一定的層次上 。 A B C D E F G H I J K L M 例如： A 到 L 的路徑： A(ki)?B(ki1)?E(ki2)?L(kj) 也可以表示為： (A,B,E,J) 路徑長度： 3， 有以下兩種計算方法 結點數(shù) – 1 分支數(shù) ⒋ 孩子結點 、 雙親結點和兄弟結點： 在一棵樹中 ， 每個結點的后繼 ， 被稱作該結點的 孩子結點 (或子女結點 )。 ⒊ 路徑與路徑長度： 對于任意兩個結點 ki 和 kj， 若樹中存在一個結點序列 ki, ki1, ki2, … , kin, kj， 使得序列中除 ki 外的任一結點都是其在序列中的前一個結點的后繼 ,則稱該結點序列為由 ki 到 kj 的一條路徑 ， 用路徑所通過的結點序列 (ki, ki1, ki2, … , kj)表示這條路徑 。 (A(B ,C ,D )) (E ,F) (G) (H ,I,J) (K,L) (M)6. 層數(shù)號碼法 (Level Number Format) 用層數(shù)來表示結點所在的位置 1………………………… A 2………………………… B 2………………………… C 2………………………… D 3………………………… E 3………………………… F 3………………………… G 3………………………… H 3………………………… I 3………………………… J 4………………………… K 4………………………… L 4………………………… M A:{B,C,D} B:{E,F} C:{G} D:{H,I,J} E:{K,L} H:{M} 樹的基本術語 ⒈ 結點的度和樹的度： (1) 結點擁有的子樹的個數(shù)稱為該結點的度； A B C D E F G H I J K L M 結點 A的度為 B的度為 C的度為 D的度為 F, G, I, J, K, L 和 M 的度為 0； (2) 樹中各結點度的最大值稱為樹的度 ， 通常將度為 m 的樹稱為 m 次樹 。/*求元素 t的前驅 */ Sons(t)。t)。 K是包含 n 個結點的有窮集合 (n≥ 0)， 關系 R滿足以下條件： (1) 有且僅有一個結點 k0∈K ， 它對于關系 R 來說 沒有前驅結點 ， 結點 k0稱作樹的根 。 可以看出 ， 數(shù)據(jù)元素之間存在的關系是一對多的 ， 或者多對一的關系 。 例 ： 只有根結點的樹 A 例 ： 一般的樹 A B E C D F G H I 樹 T 該樹 T由子樹 T1和 T2和組成 B E D F H I T1 C G T2 T1包括： D T11 E H I T12 F T13 H T121 I T122 G T21 例 ： A B C D E F G H I J K L M 不是一棵樹 , 因為 : 子樹 TreeH={H， M} 子樹 TreeI={I， M} 出現(xiàn)了交叉 ， 違反樹的定義 。 樹結構在客觀世界中也廣泛存在 ， 如人類社會的族譜和各種社會組織機構等都可用樹來形象表示 。 線性結構可以表示元素或結點的相鄰關系 ， 而在樹型結構中 ， 由于一個結點與多個結點相對應 ， 所以樹型結構除用于表示相鄰關系外 ， 還可以表示層次關系 。 樹型結構是一類重要的非線性數(shù)據(jù)結構 ， 其中又以樹和二叉樹最為常用 。 樹應用舉例 書名 第一章 第二章 … 第 … 章 第 1節(jié) … …… ┇ ┇ ┇ + * * a b f c / d e a*b+(cd/e)*f 本章重點討論二叉樹的存儲結構及各種操作 ,并研究樹和森林與二叉樹之間的轉換關系 。 樹的定義是遞歸的 ， 因為在樹的定義中有用到樹的定義 。 補充說明 樹的分類： (1) 自由樹 (無根樹 )：結點的排列無關緊要 。 (2) 除結點 k0外 ， K中的每個結點 對于關系 R來說都 有且僅有一個前驅結點 。 /*初始化樹：構造一個只有一個元素的樹 */ ClearTree(amp。 /*求元素 t的后繼 */ … } 樹的邏輯表示方法 (其它表示形式 ) 1. 樹形表示法：這是樹的最基本的表示 ， 使用一棵倒置的樹表示樹結構 ， 非常直觀和形象 。 如左圖樹 A 的度為
教學課件相關推薦
鄂ICP備17016276號-1