14數(shù)據(jù)結(jié)構(gòu)之三.ppt

數(shù)據(jù)結(jié)構(gòu)之二 樹型結(jié)構(gòu) 四 二叉樹的遍歷 二叉樹遍歷的定義按照一定的規(guī)律不重復(fù)地訪問(wèn) 或取出結(jié)點(diǎn)中的信息 或?qū)Y(jié)點(diǎn)作其它的處理 二叉樹中的每一個(gè)結(jié)點(diǎn) 2 二叉樹遍歷的順序如果用L D R分別表示遍歷左子樹 訪問(wèn)根結(jié)點(diǎn) 遍歷右子樹 則對(duì)二叉樹的遍歷可以有下列六種 3 6 組合 LDR LRD DLR DRL RDL RLD 若再限定先左后右的次序 則只剩下三種組合 LDR 中序遍歷 LRD 后序遍歷 DLR 前序遍歷 以下遍歷以該樹為例 前序遍歷 規(guī)則如下 若二叉樹為空 則退出 否則 訪問(wèn)處理根結(jié)點(diǎn) 前序遍歷左子樹 前序遍歷右子樹 如上圖的前序遍歷結(jié)果為abdehicfg 中序遍歷 規(guī)則如下 若二叉樹為空 則退出 否則 中序遍歷左子樹 訪問(wèn)處理根結(jié)點(diǎn) 中序遍歷右子樹 如上圖的中序遍歷結(jié)果為dbheiafcg 后序遍歷 規(guī)則如下 若二叉樹為空 則退出 否則 后序遍歷左子樹 后序遍歷右子樹 訪問(wèn)處理根結(jié)點(diǎn) 如上圖的后序遍歷結(jié)果為dhiebfgca 普通樹的遍歷 先根次序遍歷樹規(guī)則 若樹為空 則退出 否則先根訪問(wèn)樹的根結(jié)點(diǎn) 然后先根遍歷根的每棵子樹 后根次序遍歷樹規(guī)則 若樹為空 則退出 否則先依次后根遍歷每棵子樹 然后訪問(wèn)根結(jié)點(diǎn) 后根遍歷次序?yàn)閣hdexafbsmonijtucr 先根遍歷次序?yàn)閞awxdhebfcstimonju 五 根據(jù)兩種遍歷順序確定樹結(jié)構(gòu) 由兩種順序確定樹結(jié)構(gòu)遍歷二叉樹有三種規(guī)則 前序遍歷 根 左子樹 右子樹 中序遍歷 左子樹 根 右子樹 后序遍歷 左子樹 右子樹 根 由于前序遍歷的第一個(gè)字符和后序遍歷的最后一個(gè)字符為根 中序遍歷中位于根左方的子串和位于根右方的子串分別反映了左子樹和右子樹的結(jié)構(gòu) 因此二叉樹的形態(tài)可以由其中序與后序或者前序與中序唯一確定 但無(wú)法反映左子樹和右子樹結(jié)構(gòu)的前序遍歷與后序遍歷卻不能做到這一點(diǎn) 因此這兩個(gè)遍歷順序可對(duì)應(yīng)多種二叉樹的形態(tài) 試題 1 二叉樹T 已知其先根遍歷是1243576 數(shù)字為結(jié)點(diǎn)的編號(hào) 以下同 后根遍歷是4275631 則該二叉樹的可能的中根遍歷是 A 4217536B 2417536C 4217563D 24157362 已知一棵二叉樹的結(jié)點(diǎn)名為大寫英文字母 其中序與后序遍歷的順序分別為 CBGEAFHDIJ與CGEBHFJIDA 則該二叉樹的先序遍歷的順序?yàn)槭裁?六 二叉排序樹 所謂二叉排序樹是指具有下列性質(zhì)的非空二叉樹 若根結(jié)點(diǎn)的左子樹不空 則左子樹的所有結(jié)點(diǎn)值均小于根結(jié)點(diǎn)值 若根結(jié)點(diǎn)的右子樹不空 則右子樹的所有結(jié)點(diǎn)值均不小于根結(jié)點(diǎn)值 根結(jié)的左右樹也分別為二叉排序樹 顯然 對(duì)二叉排序樹進(jìn)行中序遍歷 可得出結(jié)點(diǎn)值遞增的排序序列 例 638192457 6 3 1 4 2 5 8 7 9 七 最優(yōu)二叉樹 哈夫曼樹 概念在具有n個(gè)帶權(quán)葉結(jié)點(diǎn)的二叉樹中 使所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和 即二叉樹的帶權(quán)路徑長(zhǎng)度 為最小的二叉樹 稱為最優(yōu)二叉樹 又稱最優(yōu)搜索樹或哈夫曼樹 即最優(yōu)二叉樹使 Wk 第k個(gè)葉結(jié)點(diǎn)的權(quán)值 Pk 第k個(gè)葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度 達(dá)到最小 哈夫曼樹的應(yīng)用 哈夫曼編碼發(fā)明Huffman于1952年提出一種編碼方法 該方法完全依據(jù)字符出現(xiàn)概率來(lái)構(gòu)造異字頭的平均長(zhǎng)度最短的碼字 有時(shí)稱之為最佳編碼 一般就叫作Huffman編碼 編碼過(guò)程例 編碼字符組成abcdef頻度 單位 次 4513121695 e f e f c e f c b e f c b d e f c b d a e f c b d a 0 1 1 1 1 1 0 0 0 0 每個(gè)編碼都不是另一個(gè)的前綴 試題 最優(yōu)前綴編碼 也稱Huffman編碼 這種編碼組合的特點(diǎn)是對(duì)于較頻繁使用的元素給與較短的唯一編碼 以提高通訊的效率 下面編碼組合哪一組不是合法的前綴編碼 A 00 01 10 11 B 0 1 00 11 C 0 10 110 111 D 1 01 000 001 用二叉樹來(lái)表示表達(dá)式 對(duì)于表達(dá)式a b c d e f g有如下二叉樹 如果按照中序遍歷此二叉樹 得到的中序序列就是a b c d e f g如果改用先序序列遍歷 就將得到 a bc de fg而后序遍歷將得到abc de fg 從表達(dá)式