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