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