據(jù)結(jié)構(gòu)二叉樹(shù)的線索化

1、6.1 6.1 樹(shù)的定義和基本術(shù)語(yǔ)樹(shù)的定義和基本術(shù)語(yǔ)6.2 6.2 二叉二叉樹(shù)樹(shù)6.3 6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)6.4 6.4 樹(shù)和森林樹(shù)和森林6.6 6.6 哈夫曼樹(shù)及其應(yīng)用哈夫曼樹(shù)及其應(yīng)用第六章第六章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù) 何謂線索二叉樹(shù)？何謂線索二叉樹(shù)？ 線索鏈表的遍歷算法線索鏈表的遍歷算法 如何建立線索鏈表？如何建立線索鏈表？6.3.2 二叉樹(shù)的線索化二叉樹(shù)的線索化6.3 6.3 遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù)一、一、何謂線索二叉樹(shù)？何謂線索二叉樹(shù)？遍歷二叉樹(shù)的結(jié)果是， 求得結(jié)點(diǎn)的一個(gè)線性序列。abcdefghk例如:先序先序序列: a b c

2、 d e f g h k中序中序序列: b d c a h g k f e后序后序序列: d c b h k g f e a指向該線性序列中的“前驅(qū)”和 “后繼” 的指針指針，稱作“線線索索”與其相應(yīng)的二叉樹(shù)，稱作 “線索二叉樹(shù)線索二叉樹(shù)”包含 “線索” 的存儲(chǔ)結(jié)構(gòu)，稱作 “線索鏈線索鏈表表”a b c d e f g h k d c b e 對(duì)對(duì)線索鏈表線索鏈表中結(jié)點(diǎn)的約定：中結(jié)點(diǎn)的約定： 在二叉鏈表的結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域增加兩個(gè)標(biāo)志域，并作如下規(guī)定：若該結(jié)點(diǎn)的左子樹(shù)不空，若該結(jié)點(diǎn)的左子樹(shù)不空，則lchild域的指針指向其左子樹(shù)， 且左標(biāo)志域的值為“指針 link”； 否則，lchild域的

3、指針指向其“前驅(qū)”， 且左標(biāo)志的值為“線索 thread” 。若該結(jié)點(diǎn)的右子樹(shù)不空，若該結(jié)點(diǎn)的右子樹(shù)不空，則rchild域的指針指向其右子樹(shù)， 且右標(biāo)志域的值為 “指針 link”；否則，rchild域的指針指向其“后繼”， 且右標(biāo)志的值為“線索 thread”。 如此定義的二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)稱作如此定義的二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)稱作“線索鏈表線索鏈表”6.3.2 二叉樹(shù)的線索化二叉樹(shù)的線索化 當(dāng)以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí)，只能找到結(jié)點(diǎn)的左、右孩子信息，而不能直當(dāng)以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí)，只能找到結(jié)點(diǎn)的左、右孩子信息，而不能直接得到結(jié)點(diǎn)在任一序列（先序、中序或后序序列）中的前驅(qū)和后繼信息，這種接得到結(jié)點(diǎn)在

4、任一序列（先序、中序或后序序列）中的前驅(qū)和后繼信息，這種信息只有在遍歷的動(dòng)態(tài)過(guò)程中才能得到。為了保存這種在遍歷過(guò)程中得到的信信息只有在遍歷的動(dòng)態(tài)過(guò)程中才能得到。為了保存這種在遍歷過(guò)程中得到的信息，我們利用二叉鏈表中的空鏈域（由于結(jié)點(diǎn)沒(méi)有左子樹(shù)或右子樹(shù)），來(lái)存放息，我們利用二叉鏈表中的空鏈域（由于結(jié)點(diǎn)沒(méi)有左子樹(shù)或右子樹(shù)），來(lái)存放結(jié)點(diǎn)的前驅(qū)和后繼信息。結(jié)點(diǎn)的前驅(qū)和后繼信息。作如下規(guī)定：作如下規(guī)定： 若結(jié)點(diǎn)有左子樹(shù)，則其若結(jié)點(diǎn)有左子樹(shù)，則其lchild域指示其左孩子，否則令域指示其左孩子，否則令lchild域指示其前驅(qū)；域指示其前驅(qū)； 若結(jié)點(diǎn)有右子樹(shù)，則其若結(jié)點(diǎn)有右子樹(shù)，則其rchild域指示其右孩

5、子，否則令域指示其右孩子，否則令rchild域指示其后繼。域指示其后繼。 （1）線索鏈表的結(jié)點(diǎn)結(jié)構(gòu)）線索鏈表的結(jié)點(diǎn)結(jié)構(gòu)lchild ltag data rtag rchild其中：其中：data：數(shù)據(jù)域；：數(shù)據(jù)域； lchild：左指針域，指向該結(jié)點(diǎn)的左孩子；：左指針域，指向該結(jié)點(diǎn)的左孩子； rchild：右指針域，指向該結(jié)點(diǎn)的右孩子；：右指針域，指向該結(jié)點(diǎn)的右孩子； 0 lchild域指示結(jié)點(diǎn)的左孩子域指示結(jié)點(diǎn)的左孩子 ltag = 1 lchild域指示結(jié)點(diǎn)的前驅(qū)域指示結(jié)點(diǎn)的前驅(qū) 0 rchild域指示結(jié)點(diǎn)的右孩子域指示結(jié)點(diǎn)的右孩子 rtag = 1 rchild域指示結(jié)點(diǎn)的后繼域指示結(jié)點(diǎn)

6、的后繼（2）線索鏈表的定義）線索鏈表的定義 線索鏈表線索鏈表：以上述結(jié)點(diǎn)結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，稱之：以上述結(jié)點(diǎn)結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，稱之為線索鏈表。為線索鏈表。（3）相關(guān)術(shù)語(yǔ)）相關(guān)術(shù)語(yǔ)線索化線索化：對(duì)二叉樹(shù)以某種次序遍歷使其變?yōu)榫€性二叉樹(shù)的過(guò)程。：對(duì)二叉樹(shù)以某種次序遍歷使其變?yōu)榫€性二叉樹(shù)的過(guò)程。線索二叉樹(shù)（線索二叉樹(shù)（threaded binary tree）：加上線索的二叉樹(shù)。：加上線索的二叉樹(shù)。線索線索：在線索鏈表中指向結(jié)點(diǎn)前驅(qū)和后繼的指針。：在線索鏈表中指向結(jié)點(diǎn)前驅(qū)和后繼的指針。（4）圖形表示）圖形表示-+ /a * e fb -c d-+ /nil

7、nila * e fb -c d(a) ( a + b * (cd)e / f )表達(dá)式的二叉樹(shù)表達(dá)式的二叉樹(shù)(b) 中序線索二叉樹(shù)中序線索二叉樹(shù)圖圖6.11線索二叉樹(shù)及其存儲(chǔ)結(jié)構(gòu)線索二叉樹(shù)及其存儲(chǔ)結(jié)構(gòu)thrt 0 1bt0 0 0 0 0 / 0 1 a 1 0 * 0 1 e 1 1 f 10 01 b 11 c 11 d 1(c) 中序線索鏈表中序線索鏈表圖中，實(shí)線為指針（指向左、右子樹(shù)），虛線為線索（指向前驅(qū)和后繼）。圖中，實(shí)線為指針（指向左、右子樹(shù)），虛線為線索（指向前驅(qū)和后繼）。typedef struct bithrnod telemtype data; struct bithr

8、node *lchild, *rchild; / 左右指針 pointerthr ltag, rtag; / 左右標(biāo)志 bithrnode, *bithrtree;線索鏈表的類型描述： typedef enum link, thread pointerthr; / link=0:指針，thread=1:線索二、線索鏈表的遍歷算法二、線索鏈表的遍歷算法: for ( p = firstnode(t); p; p = succ(p) ) visit (p);由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息，從而簡(jiǎn)化了遍歷的算法。例如例如: 對(duì)中序線索化鏈表的遍歷算法對(duì)中序線索化鏈表的遍歷

9、算法 中序遍歷的第一個(gè)結(jié)點(diǎn)中序遍歷的第一個(gè)結(jié)點(diǎn) ？ 在中序線索化鏈表中結(jié)點(diǎn)的后繼在中序線索化鏈表中結(jié)點(diǎn)的后繼 ？左子樹(shù)上處于“最左下最左下”（沒(méi)有左子樹(shù)）的結(jié)點(diǎn)若若無(wú)右子樹(shù)，則為則為后繼線索后繼線索所指結(jié)點(diǎn)否則為否則為對(duì)其右子樹(shù)右子樹(shù)進(jìn)行中序遍歷遍歷時(shí)訪問(wèn)的第一個(gè)結(jié)點(diǎn)第一個(gè)結(jié)點(diǎn)void inordertraverse_thr(bithrtree t, void (*visit)(telemtype e) /t指向結(jié)點(diǎn)，頭結(jié)點(diǎn)的左鏈lchild指向根結(jié)點(diǎn)，可參照線索化算法。/中序遍歷二叉線索樹(shù)t的非遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit p = t-lchild; / p指向根結(jié)點(diǎn) whil

10、e (p != t) / 空樹(shù)或遍歷結(jié)束時(shí)，p=t while (p-ltag=link) p = p-lchild; / 第一個(gè)結(jié)點(diǎn) if (!visit(p-data) return error;/訪問(wèn)其左子樹(shù)為空的結(jié)點(diǎn) while (p-rtag=thread & p-rchild!=t) p = p-rchild; visit(p-data); / 訪問(wèn)后繼結(jié)點(diǎn) p = p-rchild; / p進(jìn)至其右子樹(shù)根 / inordertraverse_thr 在中序遍歷過(guò)程中修改結(jié)點(diǎn)的在中序遍歷過(guò)程中修改結(jié)點(diǎn)的左、右指針域，以保存當(dāng)前訪問(wèn)結(jié)左、右指針域，以保存當(dāng)前訪問(wèn)結(jié)點(diǎn)的點(diǎn)的“前

11、驅(qū)前驅(qū)”和和“后繼后繼”信息。遍歷過(guò)信息。遍歷過(guò)程中，附設(shè)指針程中，附設(shè)指針pre, 并始終保持指并始終保持指針針pre指向當(dāng)前訪問(wèn)的、指針指向當(dāng)前訪問(wèn)的、指針p所指所指結(jié)點(diǎn)的前驅(qū)。結(jié)點(diǎn)的前驅(qū)。三、如何建立線索鏈表？三、如何建立線索鏈表？void inthreading(bithrtree p) if (p) / 對(duì)以p為根的非空二叉樹(shù)進(jìn)行線索化 inthreading(p-lchild); / 左子樹(shù)線索化 if (!p-lchild) / 建前驅(qū)線索 p-ltag = thread; p-lchild = pre; if (!pre-rchild) / 建后繼線索 pre-rtag = thread; pre-rchild = p; pre = p; / 保持 pre 指向 p 的前驅(qū) inthreading(p-rchild); / 右子樹(shù)線索化 / if / inthreadingstatus inorderthreading(bithrtree &thrt, bithrtree t) / 構(gòu)建中序線索鏈表 if (!(thrt = new bithrnode) ) exit (overflow); thrt-ltag = link; thrt-rtag =thread; thrt-rchild = th