[理學]數(shù)據(jù)結構7樹形結構(已修改)
2025-10-23 21:14 本頁面
【正文】 第七章 樹形結構 在前面幾章中介紹了各種常用的線性結構 ， 本章介紹非線性結構 ， 其中樹型結構就是一種典型的非線性結構 。 線性結構可以表示元素或結點的相鄰關系 ， 而在樹型結構中 ， 由于一個結點與多個結點相對應 ， 所以樹型結構除用于表示相鄰關系外 ， 還可以表示層次關系 。 樹型結構是一類重要的非線性數(shù)據(jù)結構 ， 其中又以樹和二叉樹最為常用 。 直觀角度看 ， 樹是以分支關系定義的層次結構 。 樹在計算機領域中得到廣泛應用 ，如文件管理中的目錄結構 、 數(shù)據(jù)庫系統(tǒng)中的信息組織形式等 。 樹結構在客觀世界中也廣泛存在 ， 如人類社會的族譜和各種社會組織機構等都可用樹來形象表示 。 樹應用舉例 書名 第一章 第二章 … 第 … 章 第 1節(jié) … …… ┇ ┇ ┇ + * * a b f c / d e a*b+(cd/e)*f 本章重點討論二叉樹的存儲結構及各種操作 ,并研究樹和森林與二叉樹之間的轉換關系 。 樹的定義和基本術語 樹的定義： 一 、 非數(shù)學語言定義 樹 (Tree)是 n(n≥ 0， n=0為空樹 )個結點的有限集合 。 在任意一棵非空樹中： 1. 當 n 0 時有且僅有一個特定的稱為根 (Root)的結點； 2. 其余結點可分為 m 個 (m0)互不相交的有限集 T1,T2,… ,Tm 其中每一個集合 Ti 本身又是一棵樹 ， 并且稱為根的 子樹 (SubTree)。 例 ： 只有根結點的樹 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ù)結構 ， 具有以下特點： ?它的每個節(jié)點都可以有不止一個后繼 (除根以外的所有結點 )， 都有且只有一個前驅 ； ?這些數(shù)據(jù)結點按分支關系組織起來 ， 清晰地反映了數(shù)據(jù)元素之間的層次關系 。 可以看出 ， 數(shù)據(jù)元素之間存在的關系是一對多的 ， 或者多對一的關系 。 補充說明 樹的分類： (1) 自由樹 (無根樹 )：結點的排列無關緊要 。 結點 數(shù)為 1 結點 數(shù)為 2 結點 數(shù)為 3 結點 數(shù)為 4 (2) 有根樹：根結點位于樹的頂 。 (默認討論的樹 ) 結點 數(shù)為 1 結點 數(shù)為 2 結點 數(shù)為 3 結點 數(shù)為 4 (3) 有序樹：能表示第一個孩子 、 第二孩子 …… (如族譜 、 二叉樹就是有序的 ) 二 、 樹的形式化定義： (數(shù)學語言定義 ) 樹定義為集合： T＝ {K,R}。 K是包含 n 個結點的有窮集合 (n≥ 0)， 關系 R滿足以下條件： (1) 有且僅有一個結點 k0∈K ， 它對于關系 R 來說 沒有前驅結點 ， 結點 k0稱作樹的根 。 (2) 除結點 k0外 ， K中的每個結點 對于關系 R來說都 有且僅有一個前驅結點 。 (3) K中 每個結點 對于關系 R來說 可以有多個后繼結點 。 三 、 抽象數(shù)據(jù)類型樹的定義： ADT Tree { 數(shù)據(jù)對象： D={ai|1≤i≤n,n 0， ai∈ElemType 類型 } 數(shù)據(jù)關系： R={ai,aj|ai,aj∈D, 1≤i≤n, 1≤j≤n, 其中每個元素只有一個前驅 ， 可以有零個或多個后繼結點 ， 有且僅有一個元素沒有前驅 } 基本運算： InitTree(amp。t)。 /*初始化樹：構造一個只有一個元素的樹 */ ClearTree(amp。t)。/*銷毀樹：釋放樹 t占用的存儲空間 */ Parent(t)。/*求元素 t的前驅 */ Sons(t)。 /*求元素 t的后繼 */ … } 樹的邏輯表示方法 (其它表示形式 ) 1. 樹形表示法：這是樹的最基本的表示 ， 使用一棵倒置的樹表示樹結構 ， 非常直觀和形象 。 A B C D E F G H I J K L M 2. 集合法 TreeA的結構： 結點 A包括 {B,C,D} 結點 B包括 {E,F} 結點 C包括 {G} 結點 D包括 {H,I,J} 結點 E包括 {K,L} 結點 H包括 {M} A B C D E F G H I J K L M 3. 范式圖法或文氏圖法 (Venn Diagram) 每棵樹對應一個圓圈 ， 圓圈包含根結點和子樹的圓圈 ， 同一棵根結點下的各子樹對應的圓圈是不能相交的 。 A B C D E F G H I J K L M A:{B,C,D} B:{E,F} C:{G} D:{H,I,J} E:{K,L} H:{M} 4. 縮格法 (Indentation) 或凹入表示法 A B C D
教學課件相關推薦
鄂ICP備17016276號-1