山東廣播電視大學(xué)開放教育數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)第四部分-免費閱讀
【正文】 A．哈夫曼樹 B．平衡二叉樹 C．二叉樹 D．完全二叉樹13．下列有關(guān)二叉樹的說法正確的是（ ）。A．2k B．2k1C．2k1 D．2k15. 設(shè)某一二叉樹先序遍歷為abdec，中序遍歷為dbeac，則該二叉樹后序遍歷的順序是（ ）。 strcpy(H[i].bits，amp。 }039。\039。 /*c和p分別指示T中孩子和雙親的位置*/ char bits[n+1]； /*存放編碼位串*/ 注意： ?、?由于生成的編碼與要求的編碼反序，將生成的代碼先從后往前依次存放在一個臨時向量中，并設(shè)一個指針start指示編碼在該向量中的起始位置（start初始時指示向量的結(jié)束位置）。而哈夫曼樹是WPL最小的二叉樹，因此編碼的平均碼長(或文件總長)亦最小。哈夫曼編碼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。 其中：最優(yōu)的前綴碼對文件的壓縮效果亦最佳。 根據(jù)計算公式： 101（2）變長編碼方案 數(shù)據(jù)壓縮過程稱為編碼。為了區(qū)別于樹形結(jié)構(gòu)中前趨(即雙親)結(jié)點和后繼(即孩子)結(jié)點的概念，對上述三種線性序列，要在某結(jié)點的前趨和后繼之前冠以其遍歷次序名稱。 先序遍歷二叉樹時，對結(jié)點的訪問次序為先序序列4．帶雙親指針的二叉鏈表 在一棵二叉樹中，所有類型為BinTNode的結(jié)點，再加上一個指向開始結(jié)點(即根結(jié)點)的BinTree型頭指針(即根指針)root，就構(gòu)成了二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)，并將其稱為二叉鏈表?！ 、?一般的二叉樹采用順序存儲結(jié)構(gòu)時，雖然簡單，但易造成存儲空間的浪費?！ 、苋鬷為奇數(shù)且不為1，則Ki的左兄弟的編號是i1；否則，Ki無左兄弟。結(jié)點在這個序列中的相互位置還能反映出結(jié)點之間的邏輯關(guān)系。（1）二叉樹與無序樹不同一、相關(guān)術(shù)語 樹、二叉樹、樹根、子樹、有序樹、無序數(shù)、森林、終端結(jié)點（葉子）、非終端結(jié)點、結(jié)點的度、結(jié)點的層次、樹的深度、滿二叉樹、完全二叉樹、理想二叉樹、孩子、雙親、左孩子、右孩子、先序遍歷、中序遍歷、后序遍歷、層次遍歷、哈夫曼樹、最優(yōu)二叉樹、路徑、路徑長度、權(quán)、帶權(quán)路徑長度、哈夫曼編碼。 樹的遞歸定義刻畫了樹的固有特性：一棵非空樹是由若干棵子樹構(gòu)成的，而子樹又可由若干棵更小的子樹構(gòu)成?！ 纠咳缦聢D所示?！ 、谌?i≤n，則Ki的左孩子的編號是2i；否則，Ki無左孩子，即Ki必定是葉子。 將完全二叉樹中所有結(jié)點按編號順序依次存儲在一個向量bt[0..n]中。 bt[0]不用或用來存儲結(jié)點數(shù)目。 【參見教材】（二）鏈?zhǔn)酱鎯Y(jié)構(gòu) Struct node *lchild，*rchild； /*左右孩子指針*/ typedef BinTNode *BinTree；/*BinTree為指向BinTNode類型結(jié)點的指針類型*/3．二叉鏈表（二叉樹的常用鏈?zhǔn)酱鎯Y(jié)構(gòu)） D B A E C F（二） 先序序列 后序遍歷二叉樹時，對結(jié)點的訪問次序為后序序列 【例】后序遍歷上圖所示的二叉樹時，得到的后序序列為： 注意： ?。?） 在搜索路線中，若訪問結(jié)點均是第一次經(jīng)過結(jié)點時進(jìn)行的，則是先序遍歷；若訪問結(jié)點均是在第二次(或第三次)經(jīng)過結(jié)點時進(jìn)行的，則是中序遍歷(或后序遍歷)。（一）編碼方案 數(shù)據(jù)解壓過程稱為解碼。 頻度（單
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1