馬樂 李晨志 馬堯

四川大學(xué)/公共管理學(xué)院 四川 成都 610000

引言

在經(jīng)典的二叉樹線索化算法改進(jìn)方面，費洪曉、楊彥等人在改進(jìn)二叉樹線索化方面取得了相應(yīng)成果，簡化了二叉樹遍歷流程，但是并沒有將該改進(jìn)方法推廣至多叉樹。

1 傳統(tǒng)樹的線索化

相比于與一般的樹的節(jié)點，樹的線索化需要構(gòu)建的節(jié)點結(jié)構(gòu)新增加了標(biāo)識域，數(shù)據(jù)節(jié)點包含5個域，如圖1所示：

圖1

其中data域存儲節(jié)點相應(yīng)數(shù)據(jù)，ptr是指針域，tag是標(biāo)識 符，其具體含義如下面公式所示。

以這種方式線索化的樹會帶有因自身局限性而導(dǎo)致的非連續(xù)性，即會存在線索在某一結(jié)點中斷的情況。具體以前序線索二叉樹為例，如圖2所示，其中Lc指向節(jié)點的左孩子或直接后繼，Rc指向節(jié)點的右孩子或直接前驅(qū)，Lt是Lc的標(biāo)識符，Rt是Rc的標(biāo)識符。

圖2 先序線索化二叉樹

這種二叉樹存在不連貫性，導(dǎo)致在遍歷整棵樹的時候仍需要前序遍歷才能找到下一個節(jié)點。

2 改進(jìn)樹的線索化

通過觀察傳統(tǒng)的二叉樹線索化方法會發(fā)現(xiàn)，之所以會出現(xiàn)線索中斷的情況是因為有些節(jié)點因為存在左（右）孩子，指針域被占用，導(dǎo)致其不能進(jìn)行線索化。如果使得一個指針域可以同時滿足指向其孩子和指向線索兩種功能，這樣的不連續(xù)性就能得到解決[1-3]。

因為對于二叉樹的前序遍歷而言，一個節(jié)點（非葉子節(jié)點）的左孩子就是它的直接后繼。因此對于有左孩子的節(jié)點，左指針域不僅指向其左孩子，還指向直接后繼，而對于葉子節(jié)點而言，其左指針域自然也是指向其直接后繼。所以在這種改進(jìn)的方法下，節(jié)點的左孩子和直接后繼就統(tǒng)一了。Ltag無論是1還是0，節(jié)點的Lc始終指向其直接后繼。運用改進(jìn)的算法線索化二叉樹如圖3所示。

圖3 改進(jìn)的算法線索化二叉樹圖

改進(jìn)后的線索化方法與原先相比空間需求沒有增加，時間復(fù)雜度相同，但是在遍歷過程中，舊線索二叉樹在遍歷某些節(jié)點時需要使用遍歷非線索二叉樹的方法，但新的線索二叉樹只需以遍歷一個線性鏈表的方式進(jìn)行遍歷即可。

3 推廣到多叉樹和代碼實現(xiàn)

下面將該方法推廣到多叉樹，以三叉樹為例并附上相應(yīng)c語言代碼。三叉樹的線索化需要的節(jié)點結(jié)構(gòu)如圖4。其中Lc指向左孩子節(jié)點，Mc、Rc同理指向中間和右孩子，Lt為該指針域標(biāo)識符，Mt、Rt依此類推，da為數(shù)據(jù)域。

圖4

c語言代碼如下：

typedefstructTNode //定義三叉樹節(jié)點

{

intda，Lt ， Mt ， Rt ;

《二次函數(shù)》是一節(jié)概念課，重點內(nèi)容只有一個，就是二次函數(shù)的概念。如何去引入，如何把一個概念表述清楚，讓學(xué)生真正地理解、弄懂這個概念的來龍去脈，從而加深對它的認(rèn)識，這是件很不容易的事情，這也是值得我們在進(jìn)行教學(xué)設(shè)計時深入思考的地方。在這節(jié)課中，筆者主要運用啟發(fā)式教學(xué)法，提出問題進(jìn)行分析討論，不嚴(yán)密之處再和學(xué)生一起思考和補充，即使對于一些較為困難的問題，也是鼓勵和引導(dǎo)學(xué)生大膽思考，積極嘗試。這樣上課氣氛非?；钴S，學(xué)生之間常會因為某個觀點的不同而爭論，在爭論之中也逐步加深了對概念的理解和認(rèn)識，概念課教學(xué)的主要目的也就達(dá)到了。

structTNode* Lc ，* Mc;

}TNode;

voidpreThread(TNode* p， TNode*&pre) //前序線索化，其中p是一個已創(chuàng)建好的三叉樹

{

if (p != NULL)

{

if (p-＞Lc == NULL)

{

p-＞Lt = 1;

p-＞Lc = p-＞Lc;

}

if (p-＞Mc == NULL) p-＞Mc =NULL;

if (pre != NULL&&pre-＞Rc == NULL)

{

pre-＞Rc = p;

pre-＞Rt = 1;

}

pre = p;

if (p-＞Lc!=NULL)preThread(p-＞Lc， pre);

if(p-＞Mc!=NULL)preThread(p-＞Mc， pre);

if(p-＞Rc!=NULL)preThread(p-＞Rc， pre);

}

}

4 結(jié)束語

本文借鑒線索二叉樹改進(jìn)算法，將其推廣至多叉樹，并給出相應(yīng)C語言代碼。這種改進(jìn)后的線索化的意義在于：時間和空間復(fù)雜度不增加的情況下，線索多叉樹的線索不會中斷，每個節(jié)點都有其后繼節(jié)點（先序遍歷）， 使得對它進(jìn)行遍歷和對線性鏈表一樣方便快捷。