[電腦基礎(chǔ)知識(shí)]第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算-資料下載頁
2025-01-19 07:39本頁面
【正文】 子樹，則其 Rchild域指示其右孩子，否則令Rchild指示其后繼。 ?為了避免混淆，其結(jié)點(diǎn)結(jié)構(gòu)可增加標(biāo)志域 Lchild Lflag data Rflag Rchild 2022/2/14 穿線二叉樹的結(jié)點(diǎn)結(jié)構(gòu)（續(xù)） ? 以這種結(jié)點(diǎn)結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu) ,叫做 線索鏈表 ,其中指向結(jié)點(diǎn)前驅(qū)與后繼的指針叫做 線索 ,加上線索的二叉樹稱之為 穿線二叉樹（線索二叉樹）。 ? 對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程稱為 線索化 。 a b c d f e g a b c d f e g (a)一棵二叉樹 (b)中序穿線二叉樹 實(shí)線表示指針，虛線表示線索 以中序穿線二叉樹為例：先從穿線樹的根出發(fā)，一直沿左指針，找到 “ 最左 ” (中序的第一個(gè)結(jié)點(diǎn) )；然后反復(fù)地找結(jié)點(diǎn)的中序后繼。一個(gè)結(jié)點(diǎn)的右指針如果是線索，則右指針就是下一個(gè)要周游的結(jié)點(diǎn)，如果右指針不是線索，則它的中序后繼是其右子樹的 “ 最左 ” 結(jié)點(diǎn)。 樹、森林和二叉樹的轉(zhuǎn)換 將樹或森林轉(zhuǎn)換成其對(duì)應(yīng)二叉樹的方法為： (1)在所有兄弟結(jié)點(diǎn)之間添加一條連線，如果是森林，則在其所有樹的樹根之間同樣也添加一條連線； (2)對(duì)于樹、森林中的每個(gè)結(jié)點(diǎn)，除保留其到第一個(gè)子女的連線外，撤消其到其它子女的連線； (3)將以上得到的樹按照順時(shí)針方向旋轉(zhuǎn) 45度。 樹、森林到二叉樹的轉(zhuǎn)換 a b c d e f g a b c d e f g a b c d e f g a b c d e f g (a) (b) (c) (d) 樹到二叉樹的轉(zhuǎn)換 a b c d e f g h i a b c d e f g h i a b c d e f g h i a b c d e f g h i (a) (b) (c) (d) 森林到二叉樹的轉(zhuǎn)換 二叉樹到樹、森林的轉(zhuǎn)換 二叉樹到樹、森林也有一種對(duì)應(yīng)的轉(zhuǎn)換關(guān)系，其過程恰巧為上述過程的逆過程，具體方法如下： (1) 首先將二叉樹按照逆時(shí)針方向旋轉(zhuǎn) 45度； (2) 若某結(jié)點(diǎn)是其雙親的左子女，則把該結(jié)點(diǎn)的右 子女，右子女的右子女， …… 都與該結(jié)點(diǎn)的雙 親用線連起來； (3) 最后去掉原二叉樹中所有雙親到其右子女的連 線。 a b d e c f g h i a b d e c f g h i a b d e c f g h i a b d e c f g h i (a) (b) (c) (d) 二叉樹到樹、森林的轉(zhuǎn)換 表達(dá)式的線性化 有序樹：結(jié)點(diǎn)的所有子結(jié)點(diǎn)從左到右次序不能顛倒 將有序樹轉(zhuǎn)化成二叉樹的原則： (1)有序樹 T中的結(jié)點(diǎn)與二叉樹 BT中的結(jié)點(diǎn)一一對(duì)應(yīng)； (2)有序樹 T中某個(gè)結(jié)點(diǎn) N的第一個(gè)子結(jié)點(diǎn) （ 即最左邊的子 結(jié)點(diǎn) ） N1， 在二叉樹 BT中為對(duì)應(yīng)結(jié)點(diǎn) N的左子結(jié)點(diǎn)； (3)有序樹 T中某個(gè)結(jié)點(diǎn) N的第一個(gè)子結(jié)點(diǎn)以后的其他子結(jié) 點(diǎn) ， 在二叉樹 BT中被依次鏈接成一串起始于 N1的右子結(jié)點(diǎn) 。 a*(b＋ c/d)＋ e*h－ g*f(s， t， x＋ y) （波蘭表示） (1)將表達(dá)式用有序樹表示 ， 即構(gòu)造表達(dá)式樹 。 (2)將表達(dá)式樹化為二叉樹 。 (3)對(duì)相應(yīng)的二叉樹進(jìn)行中序遍歷 ， 其遍歷序列即為表達(dá)式的波蘭表示式 。 表達(dá)式 a*(b＋ c/d)＋ e*h－ g*f(s， t， x＋ y) 的波蘭表示式為 a b c d / ＋ * e h * g s t x y ＋ f * － ＋ 第 45 頁 小 結(jié) 定義和性質(zhì) 存儲(chǔ)結(jié)構(gòu) 遍歷 順序結(jié)構(gòu) 鏈?zhǔn)浇Y(jié)構(gòu) 二叉鏈表 三叉鏈表 樹 二叉樹 1:2， 性質(zhì)有 3+2條 中序遍歷 后序遍歷 先序遍歷 第 4節(jié)結(jié)束 1 : n 相關(guān)術(shù)語
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1