特殊二叉樹ppt課件(編輯修改稿)
2025-05-28 12:11 本頁面
【文章內(nèi)容簡介】 右孩子為根的子樹又同樣各是一個堆。 大根堆的定義與上述類似，只要把小于等于改為大于等于就得到了。 25 3653 42742018 2273 4826 351860 35(a) (b) 堆的定義 堆的存儲結(jié)構(gòu) struct Heap { ElemType* heap。 int len。 int MaxSize。 }。 7 3 4 82 6 3 51 86 001 2345 0 1 2 3 4 5 6 7 8 9 18 26 35 73 48 60 堆的存儲結(jié)構(gòu) 堆的運算 （ 1）向堆中插入一個元素 將該元素寫入到堆尾，即堆中最后一個元素位置的后面，如果不滿足對的特征，向上逐層調(diào)整。 插入 15 （ 2）從堆中刪除元素 （刪除堆頂元素 ） 將棧頂結(jié)點刪除后，將堆尾結(jié)點移至堆頂，若破壞了堆的特征，從上往下逐層調(diào)整 堆的運算 練習： P247 習題 61中 3， 4 3. 40 64 12 38 15 26 48 52 55 73 （ 12 15 40 38 26 52 48 64 55 73） 4. 40 64 12 38 15 26 48 52 刪除 12 40 15 38 26 64 48 52 40 15 38 26 64 48 52 刪除 15 40 26 48 38 64 52 40 26 48 38 64 52 刪除 26 40 38 52 48 64 64 40 52 48 40 38 52 48 64 刪除 38 練習： ABCDEFG，其中序遍歷序列可能是＿＿＿＿ A. CABDEFG B. ABCDEFG C. DACEFBG D. ADCFEGB BD h的二叉樹中無單分支結(jié)點，問此樹所包含的結(jié)點數(shù)至少為＿＿＿＿ 、中、后序遍歷序列中的相對次序＿＿＿＿ A. 不發(fā)生改變 B. 發(fā)生改變 C. 不能確定 D. 以上均錯 2h1 A 哈夫曼樹 基本術(shù)語 ? 路徑和路徑長度 若在一棵樹中存在一個結(jié)點序列 k1,k2,… kj ,使得 ki是ki+1的雙親 (1≤i≤j), 則稱此結(jié)點序列是從 k1到 kj的 路徑 。從 k1～ kj所經(jīng)過的分支數(shù)稱為這兩結(jié)點間的 路徑長度 。 ? 結(jié)點的權(quán)和帶權(quán)路徑長度 在許多應(yīng)用中，常為樹中的結(jié)點賦上一有意義的實數(shù)，該實數(shù)稱為 結(jié)點的權(quán) 。 結(jié)點的帶權(quán)路徑長度 規(guī)定為從樹根結(jié)點到該結(jié)點之間的路徑長度與該結(jié)點的權(quán)的乘積。 ?樹的帶權(quán)路徑長度 樹的帶權(quán)路徑長度 為樹中所有葉子結(jié)點的帶權(quán)路徑長度之和，記為 WPL= d (a) b c a 9 4 5 2 WPL=9 2+4 2+5 2+2 2=40 ??niiilw1?哈夫曼樹 哈夫曼 (Huffman)樹又稱最優(yōu)二叉樹，它是n個帶權(quán)葉子結(jié)點構(gòu)成的所有二叉樹中帶權(quán)路徑長度 WPL最小的二叉樹。 例 :有四個葉結(jié)點 a,b ,c,d,分別帶權(quán)為 2,由它們構(gòu)成的三棵不同的二叉樹： b (b) d a c 9 5 2 4 WPL=4 1+2 2+5 3+9 3=50 d (a) b c a 9 4 5 2 WPL=9 2+4 2+5 2+2 2=40 a (c) c d b 2 4 5 9 WPL=9 1+5 2+4 3+2 3=37 其中 圖 (c)樹的 WPL最小 ，可以驗證，此樹就是哈夫曼樹。 特點： 權(quán)值大的葉子結(jié)點距離根結(jié)點近 權(quán)值小的葉子結(jié)點距離根結(jié)點遠 構(gòu)造哈夫曼樹 構(gòu)造算法如下： (1) 根據(jù)與 n個權(quán)值 {w1,w2… wn}對應(yīng)的 n個結(jié)點構(gòu)成具有 n棵二叉樹的森林 F={T1,T2… Tn},其中第 i棵二叉樹 Ti(1 ≤ i ≤ n) 都只有一個權(quán)值
教學課件相關(guān)推薦
鄂ICP備17016276號-1