[電腦基礎(chǔ)知識]第7章樹(已修改)
2025-01-31 15:32 本頁面
【正文】 第 7 章 樹 授課班級：可視化、數(shù)據(jù)庫 學(xué)習(xí)目標(biāo) ? 理解樹的定義和與樹相關(guān)的結(jié)點、度、路徑等術(shù)語 ? 理解樹是一個非線性層次數(shù)據(jù)結(jié)構(gòu) ? 掌握樹的前序遍歷、中序遍歷和后序遍歷方法 ? 了解樹的父結(jié)點數(shù)組表示法 ? 了解樹的兒子鏈表表示法 ? 了解樹的左兒子右兄弟表示法 ? 理解二叉樹和 ADT二叉樹的概念 ? 了解二叉樹的順序存儲結(jié)構(gòu) ? 了解二叉樹的結(jié)點度表示法 ? 掌握用指針實現(xiàn)二叉樹的方法 ? 理解線索二叉樹結(jié)構(gòu)及其適用范圍 樹的定義 ? 樹型結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu)。樹型結(jié)構(gòu)是結(jié)點之間有分支，并且具有層次關(guān)系的結(jié)構(gòu)，它非常類似于自然界中的樹。樹結(jié)構(gòu)在客觀世界國是大量存在的，例如家譜、行政組織機構(gòu)都可用樹形象地表示。樹在計算機領(lǐng)域中也有著廣泛的應(yīng)用，例如在編譯程序中，用樹來表示源程序的語法結(jié)構(gòu)；在數(shù)據(jù)庫系統(tǒng)中，可用樹來組織信息；在分析算法的行為時，可用樹來描述其執(zhí)行過程。等等。 ? 樹是由一個集合以及在該集合上定義的一種層次關(guān)系構(gòu)成。 ? 定義：樹 (Tree)是 n(n=0)個結(jié)點的有限集 T，T為空時稱為空樹，否則它滿足如下兩個條件： （ 1）有且僅有一個特定的稱為根 (Root)的結(jié)點； （ 2）其余的結(jié)點可分為 m(m=0)個互不相交的子集 T1,T2,T3… Tm，其中每個子集又是一棵樹，并稱其為子樹 (Subtree)。 圖 樹的層次結(jié)構(gòu) ? 樹結(jié)構(gòu)中的一些基本概念和常用術(shù)語 – 結(jié)點：包含一個數(shù)據(jù)元素及若干指向其它結(jié) 點的分支信息。 – 結(jié)點的度：一個結(jié)點的子樹個數(shù)稱為此結(jié)點的度。 – 樹的度： 樹中所有結(jié)點的度的最大值。 – 葉結(jié)點：度為 0的結(jié)點，即無后繼的結(jié)點，也稱為終端結(jié)點。 – 分支結(jié)點：度不為 0的結(jié)點，也稱為非終端結(jié)點。除根結(jié)點外的分支結(jié)點統(tǒng)稱為 內(nèi)部結(jié)點 。 – 結(jié)點的高度：從該結(jié)點到各葉結(jié)點的最長路徑的長度。樹的高度是指根結(jié)點的高度。 – 路徑（道路）：若存在樹中的一個結(jié)點序列k1,k2,…… ,kj，使得結(jié)點 ki是結(jié)點 ki+1的父結(jié)點，則稱該結(jié)點序列是樹中從結(jié)點 k1到 kj的一條路徑。 – 路徑長度：該路徑所經(jīng)過的邊（即連接兩個結(jié)點的線段）的數(shù)目。 – 祖先結(jié)點：一個結(jié)點的祖先結(jié)點是指從根結(jié)點到該結(jié)點的路徑上的所有結(jié)點。在圖 ，結(jié)點 F的祖先是 A、 B、 F。 – 子孫結(jié)點：一個結(jié)點的直接后繼和間接后繼稱為該結(jié)點的子孫結(jié)點。在圖 ，結(jié)點 F的子孫是 F、 I、 J。 注意：任一結(jié)點既是它自己的祖先也是它自己 的子孫。 – 真祖先、真子孫： 樹中一個結(jié)點的非自身祖先和子孫分別稱為該結(jié)點的真祖先和真子孫。 – 兄弟結(jié)點：同一雙親結(jié)點的孩子結(jié)點之間互稱兄弟結(jié)點。在圖 ，結(jié)點 F的兄弟是 E。 – 結(jié)點的深度或?qū)訑?shù)： 從根結(jié)點開始定義，根結(jié)點的層次為 0，其余結(jié)點的深度為其父結(jié)點的深度加 1，如根的直接后繼的層次為 1，依此類推。 – 有序樹：在樹 T中， 如果將樹中結(jié)點的各子樹看成從左至右是有次序的，則稱該樹為 有序樹 ，否則稱為 無序樹 。在有序樹中最左邊的子樹的根稱為 第一個孩子 （最左兒子或簡稱為左兒子），最右邊的稱為 最后一個孩子（最右兒子或簡稱為右兒子） 。 – 森林 是 m(m=0)棵互不相交的樹的集合。如果我們刪去一棵樹的樹根，留下的子樹就構(gòu)成了一個森林。當(dāng)我們刪去的是一棵有序樹的樹根時，留下的子樹也是有序的，這些樹組成一個樹表。在這種情況下，稱這些樹組成的森林為 有序森林 或 果園 。 樹的遍歷 ? 定義：按某條搜索路徑巡訪樹中的每一個結(jié)點，使得每一個結(jié)點均被訪問一次，而且僅被訪問一次。 ? 遍歷方式： – 前序遍歷 – 中序遍歷 – 后序遍歷 ? 三種遍歷方式的定義 : (1)若 T是一棵空樹，對 T進行三種遍歷操作都是空操作； (2)若 T是一棵單結(jié)點樹，對 T進行三種遍歷操作都只訪問單結(jié)點； 否則，設(shè)以 n為樹根，樹根的子樹從左到右依次是 T1,T2,…… ,TK，那么 ① 對 T進行前序遍歷是先訪問樹根 n,然后依次前序遍歷 T1,T2,…… ,TK。 ② 對 T進行中序遍歷是先中序遍歷 T1，然后訪問樹根 n,接著依次對 T2,…… ,TK進行中序遍歷。 ③ 對 T進行后序遍歷是先依次對T1,T2,…… ,TK進行后序遍歷，最后訪問樹根 n。 n T1 TK T2 …… 圖 樹 T ? 例如，對圖 、中序遍歷和后序遍歷的結(jié)果分別為： – 前序： A B E F I J C D G H – 中序： E B I F J A C G D H – 后序： E I J F B C G H D A ? 練習(xí)：寫出下 圖所示的樹， 其先序、 中序、 后序遍歷的序列。 CEHGFBDA? 解答： – 先序遍歷： A、 B、 D、 F、 G、 C、 E、 H 。 – 中序遍歷： B、 F、 D、 G、 A、 C、 E、 H 。 – 后序遍歷： F、 G、 D、 B、 H、 E、 C、 A 。 ? 非遞歸方式產(chǎn)生三種遍歷的序列： 從樹根出發(fā)，依逆時針方向沿樹的外緣繞行， – 若按第一次經(jīng)過的時間次序?qū)⒏鱾€結(jié)點列出，就可以得到前序列表； – 若按最后一次經(jīng)過的時間次序?qū)⒏鱾€結(jié)點列出，就可以得到后序列表； – 若將葉結(jié)點按第一次經(jīng)過時列出，而內(nèi)部結(jié)點在第 2次經(jīng)過時列出，就可以得到中序列表； A B 1
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1