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

1、6.1 6.1 樹的定義和基本術(shù)語樹的定義和基本術(shù)語6.2 6.2 二叉二叉樹樹6.3 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.4 6.4 樹和森林樹和森林6.6 6.6 哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用第六章第六章 樹和二叉樹樹和二叉樹 何謂線索二叉樹？何謂線索二叉樹？ 線索鏈表的遍歷算法線索鏈表的遍歷算法 如何建立線索鏈表？如何建立線索鏈表？6.3.2 二叉樹的線索化二叉樹的線索化6.3 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹一、一、何謂線索二叉樹？何謂線索二叉樹？遍歷二叉樹的結(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)的二叉樹，稱作 “線索二叉樹線索二叉樹”包含 “線索” 的存儲(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)的左子樹不空，若該結(jié)點(diǎn)的左子樹不空，則lchild域的指針指向其左子樹， 且左標(biāo)志域的值為“指針 link”； 否則，lchild域的

3、指針指向其“前驅(qū)”， 且左標(biāo)志的值為“線索 thread” 。若該結(jié)點(diǎn)的右子樹不空，若該結(jié)點(diǎn)的右子樹不空，則rchild域的指針指向其右子樹， 且右標(biāo)志域的值為 “指針 link”；否則，rchild域的指針指向其“后繼”， 且右標(biāo)志的值為“線索 thread”。 如此定義的二叉樹的存儲(chǔ)結(jié)構(gòu)稱作如此定義的二叉樹的存儲(chǔ)結(jié)構(gòu)稱作“線索鏈表線索鏈表”6.3.2 二叉樹的線索化二叉樹的線索化 當(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)過程中才能得到。為了保存這種在遍歷過程中得到的信信息只有在遍歷的動(dòng)態(tài)過程中才能得到。為了保存這種在遍歷過程中得到的信息，我們利用二叉鏈表中的空鏈域（由于結(jié)點(diǎn)沒有左子樹或右子樹），來存放息，我們利用二叉鏈表中的空鏈域（由于結(jié)點(diǎn)沒有左子樹或右子樹），來存放結(jié)點(diǎn)的前驅(qū)和后繼信息。結(jié)點(diǎn)的前驅(qū)和后繼信息。作如下規(guī)定：作如下規(guī)定： 若結(jié)點(diǎn)有左子樹，則其若結(jié)點(diǎn)有左子樹，則其lchild域指示其左孩子，否則令域指示其左孩子，否則令lchild域指示其前驅(qū)；域指示其前驅(qū)； 若結(jié)點(diǎn)有右子樹，則其若結(jié)點(diǎn)有右子樹，則其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)成的二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)，稱之：以上述結(jié)點(diǎn)結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)，稱之為線索鏈表。為線索鏈表。（3）相關(guān)術(shù)語）相關(guān)術(shù)語線索化線索化：對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€性二叉樹的過程。：對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€性二叉樹的過程。線索二叉樹（線索二叉樹（threaded binary tree）：加上線索的二叉樹。：加上線索的二叉樹。線索線索：在線索鏈表中指向結(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á)式的二叉樹表達(dá)式的二叉樹(b) 中序線索二叉樹中序線索二叉樹圖圖6.11線索二叉樹及其存儲(chǔ)結(jié)構(gòu)線索二叉樹及其存儲(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í)線為指針（指向左、右子樹），虛線為線索（指向前驅(qū)和后繼）。圖中，實(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ū)”和“后繼”的信息，從而簡化了遍歷的算法。例如例如: 對(duì)中序線索化鏈表的遍歷算法對(duì)中序線索化鏈表的遍歷

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

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

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