數(shù)據(jù)結(jié)構(gòu)(本)課程輔導(dǎo)與練習(xí)第6章(已修改)
2025-06-29 06:43 本頁面
【正文】 數(shù)據(jù)結(jié)構(gòu)(本)課程輔導(dǎo)與練習(xí)第6章第6章 樹和二叉樹 樹是一種重要的非線性結(jié)構(gòu)，從邏輯角度看，其數(shù)據(jù)元素之間體現(xiàn)的是一對(duì)多的非線性關(guān)系，一切具有層次關(guān)系的問題都可以用樹來描述。一、相關(guān)術(shù)語 樹、二叉樹、樹根、子樹、有序樹、無序數(shù)、森林、終端結(jié)點(diǎn)（葉子）、非終端結(jié)點(diǎn)、結(jié)點(diǎn)的度、結(jié)點(diǎn)的層次、樹的深度、滿二叉樹、完全二叉樹、理想二叉樹、孩子、雙親、左孩子、右孩子、先序遍歷、中序遍歷、后序遍歷、層次遍歷、哈夫曼樹、最優(yōu)二叉樹、路徑、路徑長度、權(quán)、帶權(quán)路徑長度、哈夫曼編碼。二、樹的概念樹的定義 樹的遞歸定義： 樹(Tree)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集T，T為空時(shí)稱為空樹，否則它滿足如下兩個(gè)條件：(1)有且僅有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn)；(2)其余的結(jié)點(diǎn)可分為m(m≥0)個(gè)互不相交的子集Tl，T2，…，Tm，其中每個(gè)子集本身又是一棵樹，并稱其為根的子樹(Subree)?！ ∽⒁猓? 樹的遞歸定義刻畫了樹的固有特性：一棵非空樹是由若干棵子樹構(gòu)成的，而子樹又可由若干棵更小的子樹構(gòu)成。三、二叉樹的定義二叉樹是樹形結(jié)構(gòu)的一個(gè)重要類型。許多實(shí)際問題抽象出來的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹的形式，即使是一般的樹也能簡(jiǎn)單地轉(zhuǎn)換為二叉樹，而且二叉樹的存儲(chǔ)結(jié)構(gòu)及其算法都較為簡(jiǎn)單，因此二叉樹顯得特別重要。（1）二叉樹與無序樹不同 二叉樹中，每個(gè)結(jié)點(diǎn)最多只能有兩棵子樹，并且有左右之分。 二叉樹并非是樹的特殊情形，它們是兩種不同的數(shù)據(jù)結(jié)構(gòu)。 （2）二叉樹與度數(shù)為2的有序樹不同 在有序樹中，雖然一個(gè)結(jié)點(diǎn)的孩子之間是有左右次序的，但是若該結(jié)點(diǎn)只有一個(gè)孩子，就無須區(qū)分其左右次序。而在二叉樹中，即使是一個(gè)孩子也有左右之分。四、二叉樹的存儲(chǔ)結(jié)構(gòu)（一）順序存儲(chǔ)結(jié)構(gòu) 該方法是把二叉樹的所有結(jié)點(diǎn)按照一定的線性次序存儲(chǔ)到一片連續(xù)的存儲(chǔ)單元中。結(jié)點(diǎn)在這個(gè)序列中的相互位置還能反映出結(jié)點(diǎn)之間的邏輯關(guān)系。1．完全二叉樹結(jié)點(diǎn)編號(hào)（1） 編號(hào)辦法 在一棵n個(gè)結(jié)點(diǎn)的完全二叉樹中，從樹根起，自上層到下層，每層從左至右，給所有結(jié)點(diǎn)編號(hào)，能得到一個(gè)反映整個(gè)二叉樹結(jié)構(gòu)的線性序列?！ 纠咳缦聢D所示。（2） 編號(hào)特點(diǎn) 完全二叉樹中除最下面一層外，各層都充滿了結(jié)點(diǎn)。每一層的結(jié)點(diǎn)個(gè)數(shù)恰好是上一層結(jié)點(diǎn)個(gè)數(shù)的2倍。從一個(gè)結(jié)點(diǎn)的編號(hào)就可推得其雙親，左、右孩子，兄弟等結(jié)點(diǎn)的編號(hào)。假設(shè)編號(hào)為i的結(jié)點(diǎn)是ki(1≤i≤n)，則有： ①若i1，則ki的雙親編號(hào)為[i/2]；若i=1，則Ki是根結(jié)點(diǎn)，無雙親。 ?、谌?i≤n，則Ki的左孩子的編號(hào)是2i；否則，Ki無左孩子，即Ki必定是葉子。因此完全二叉樹中編號(hào)i[n/2]的結(jié)點(diǎn)必定是葉結(jié)點(diǎn)?！ 、廴?i+1≤n，則Ki的右孩子的編號(hào)是2i+1；否則，Ki無右孩子?！ 、苋鬷為奇數(shù)且不為1，則Ki的左兄弟的編號(hào)是i1；否則，Ki無左兄弟?！ 、萑鬷為偶數(shù)且小于n，則Ki的右兄弟的編號(hào)是i+1；否則，Ki無右兄弟。2．完全二叉樹的順序存儲(chǔ) 將完全二叉樹中所有結(jié)點(diǎn)按編號(hào)順序依次存儲(chǔ)在一個(gè)向量bt[0..n]中。 其中： bt[1．．n]用來存儲(chǔ)結(jié)點(diǎn) bt[0]不用或用來存儲(chǔ)結(jié)點(diǎn)數(shù)目。 【例】下表是上圖的完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)，bt[0]為結(jié)點(diǎn)數(shù)目，b[7]的雙親、左右孩子分別是bt[3]、bt[l4]和bt[15]。3．一般二叉樹的順序存儲(chǔ)（1） 具體方法 ?、?將一般二叉樹添上一些 虛結(jié)點(diǎn)，成為完全二叉樹 ?、?為了用結(jié)點(diǎn)在向量中的相對(duì)位置來表示結(jié)點(diǎn)之間的邏輯關(guān)系，按完全二叉樹形式給結(jié)點(diǎn)編號(hào)③ 將結(jié)點(diǎn)按編號(hào)存入向量對(duì)應(yīng)分量，其中虛結(jié)點(diǎn)用∮表示【例】上圖中單支樹的順序存儲(chǔ)結(jié)構(gòu)如下圖（2） 優(yōu)點(diǎn)和缺點(diǎn) ?、?對(duì)完全二叉樹而言，順序存儲(chǔ)結(jié)構(gòu)既簡(jiǎn)單又節(jié)省存儲(chǔ)空間?！ 、?一般的二叉樹采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，雖然簡(jiǎn)單，但易造成存儲(chǔ)空間的浪費(fèi)?！纠孔顗牡那闆r下，一個(gè)深度為k且只有k個(gè)結(jié)點(diǎn)的右單支樹需要2k1個(gè)結(jié)點(diǎn)的存儲(chǔ)空間?！ 、墼趯?duì)順序存儲(chǔ)的二叉樹做插入和刪除結(jié)點(diǎn)操作時(shí)，要大量移動(dòng)結(jié)點(diǎn)。4．二叉樹的順
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1