山東廣播電視大學(xué)開放教育數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)第四部分-文庫吧
2025-04-01 22:54 本頁面
【正文】 儲結(jié)構(gòu)類型定義 【參見教材】（二）鏈?zhǔn)酱鎯Y(jié)構(gòu) 1．結(jié)點的結(jié)構(gòu) 二叉樹的每個結(jié)點最多有兩個孩子。用鏈接方式存儲二叉樹時，每個結(jié)點除了存儲結(jié)點本身的數(shù)據(jù)外，還應(yīng)設(shè)置兩個指針域lchild和rchild，分別指向該結(jié)點的左孩子和右孩子。結(jié)點的結(jié)構(gòu)為：2．結(jié)點的類型說明 typedef char DataType； /*用戶可根據(jù)具體應(yīng)用定義DataType的實際類型*/ typedef struct node{ DataType data； Struct node *lchild，*rchild； /*左右孩子指針*/ }BinTNode； /*結(jié)點類型*/ typedef BinTNode *BinTree；/*BinTree為指向BinTNode類型結(jié)點的指針類型*/3．二叉鏈表（二叉樹的常用鏈?zhǔn)酱鎯Y(jié)構(gòu)） 在一棵二叉樹中，所有類型為BinTNode的結(jié)點，再加上一個指向開始結(jié)點(即根結(jié)點)的BinTree型頭指針(即根指針)root，就構(gòu)成了二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)，并將其稱為二叉鏈表。（示例參見教材）注意：① 一個二叉鏈表由根指針root惟一確定。若二叉樹為空，則root=NULL；若結(jié)點的某個孩子不存在，則相應(yīng)的指針為空。 ② 具有n個結(jié)點的二叉鏈表中，共有2n個指針域。其中只有n1個用來指示結(jié)點的左、右孩子，其余的n+1個指針域為空。4．帶雙親指針的二叉鏈表 經(jīng)常要在二叉樹中尋找某結(jié)點的雙親時，可在每個結(jié)點上再加一個指向其雙親的指針parent，形成一個帶雙親指針的二叉鏈表。注意：二叉樹存儲方法的選擇，主要依賴于所要實施的各種運(yùn)算的頻度。五、二叉樹的遍歷ACFEDB（一） 中序序列 中序遍歷二叉樹時，對結(jié)點的訪問次序為中序序列 【例】中序遍歷上圖所示的二叉樹時，得到的中序序列為： D B A E C F（二） 先序序列 先序遍歷二叉樹時，對結(jié)點的訪問次序為先序序列 【例】先序遍歷上圖所示的二叉樹時，得到的先序序列為： A B D C E F（三） 后序序列 后序遍歷二叉樹時，對結(jié)點的訪問次序為后序序列 【例】后序遍歷上圖所示的二叉樹時，得到的后序序列為： D B E F C A 注意： ?。?） 在搜索路線中，若訪問結(jié)點均是第一次經(jīng)過結(jié)點時進(jìn)行的，則是先序遍歷；若訪問結(jié)點均是在第二次(或第三次)經(jīng)過結(jié)點時進(jìn)行的，則是中序遍歷(或后序遍歷)。只要將搜索路線上所有在第一次、第二次和第三次經(jīng)過的結(jié)點分別列表，即可分別得到該二叉樹的先序序列、中序序列和后序序列。（2） 上述三種序列都是線性序列，有且僅有一個開始結(jié)點和一個終端結(jié)點，其余結(jié)點都有且僅有一個前趨結(jié)點和一個后繼結(jié)點。為了區(qū)別于樹形結(jié)構(gòu)中前趨(即雙親)結(jié)點和后繼(即孩子)結(jié)點的概念，對上述三種線性序列，要在某結(jié)點的前趨和后繼之前冠以其遍歷次序名稱。六、哈夫曼樹用哈夫曼算法構(gòu)造哈夫曼樹的要注意以下問題。① 初始森林中的n棵二叉樹，每棵樹有一個孤立的結(jié)點，它們既是根，又是葉子 ② n個葉子的哈夫曼樹要經(jīng)過n1次合并，產(chǎn)生n1個新結(jié)點。最終求得的哈夫曼樹中共有2n1個結(jié)點。③ 哈夫曼樹是嚴(yán)格的二叉樹，沒有度數(shù)為1的分支結(jié)點。下面對教材中的哈夫曼編碼加以補(bǔ)充，以幫助同學(xué)們理解。（一）編碼方案 數(shù)據(jù)壓縮過程稱為編碼。
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1