線索二叉樹算法的實(shí)驗(yàn)與實(shí)現(xiàn)

郭小春，王 紅

(1.泰山學(xué)院信息科學(xué)技術(shù)學(xué)院，山東泰安 271021;2.泰山職業(yè)技術(shù)學(xué)院財(cái)經(jīng)系，山東泰安 271000)

在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)結(jié)構(gòu)是一個(gè)重要的基礎(chǔ)理論.它在軟件開發(fā)及程序設(shè)計(jì)中都有著不可替代的應(yīng)用價(jià)值.二叉樹是一種重要的數(shù)據(jù)結(jié)構(gòu)，它的應(yīng)用范圍非常廣泛.不僅在程序設(shè)計(jì)中，而且在圖像處理和模式識別等諸多新學(xué)科中也有很重要的應(yīng)用［1－2］，它是數(shù)據(jù)結(jié)構(gòu)中目前很活躍的研究課題之一，而對二叉樹加線索使其成為線索二叉樹是簡化二叉樹各種操作的重要手段.

遍歷二叉樹是以一定規(guī)則將二叉樹中結(jié)點(diǎn)排列成一個(gè)線性序列，得到二叉樹中結(jié)點(diǎn)的先序序列、中序序列或后序序列.這實(shí)質(zhì)上是對一個(gè)非線性結(jié)構(gòu)進(jìn)行線性化操作，使每個(gè)結(jié)點(diǎn)(除第一個(gè)和最后一個(gè)外)在這些線性序列中有且僅有一個(gè)直接前驅(qū)和直接后繼.但是，當(dāng)以二叉鏈表作為存儲結(jié)構(gòu)時(shí)，只能找到結(jié)點(diǎn)的左、右孩子信息，而不能直接得到結(jié)點(diǎn)在任一序列中的前驅(qū)和后繼信息，這種信息只有在遍歷的動態(tài)過程中才能得到.解決這個(gè)問題的方法是:當(dāng)?shù)谝淮伪闅v二叉樹時(shí)，就在各結(jié)點(diǎn)的空余域中加線索，加線索的二叉樹就稱為線索二叉樹.加線索之后，當(dāng)再遍歷時(shí)，就可在某些結(jié)點(diǎn)沿著線索走，從而簡化操作［3－8］.

經(jīng)過算法分析和實(shí)驗(yàn)發(fā)現(xiàn)現(xiàn)有絕大部分“數(shù)據(jù)結(jié)構(gòu)”教科書中對二叉樹的線索化實(shí)現(xiàn)算法存在錯(cuò)誤，沒有對線索樹中非線索結(jié)點(diǎn)的LTag和RTag的指針賦值.為了解決這一問題提高數(shù)據(jù)結(jié)構(gòu)課程在理論方面教學(xué)的嚴(yán)格性和實(shí)用性，對二叉樹線索化的算法進(jìn)行了修正和實(shí)現(xiàn).

1 線索二叉樹的基礎(chǔ)知識

n個(gè)結(jié)點(diǎn)的二叉鏈表中含有n+1個(gè)空指針域.利用二叉鏈表中的空指針域，存放指向結(jié)點(diǎn)在某種遍歷次序下的前趨和后繼結(jié)點(diǎn)的指針(這種附加的指針稱為“線索”).加上線索的二叉樹稱為線索二叉樹，對二叉樹以某種次序使其變?yōu)榫€索二叉樹的過程叫做線索化.對二叉樹的遍歷過程可以有先序、中序和后序三種順序，相應(yīng)的二叉樹的線索化也有三種順序，分別稱之為先序線索化、中序線索化和后序線索化.

線索二叉樹的結(jié)點(diǎn)的存儲結(jié)構(gòu)及意義如下:若結(jié)點(diǎn)有左子樹，則其lchild域指示其左孩子，否則令lchild指示其前驅(qū);若結(jié)點(diǎn)有右子樹，則其rchild域指示其右孩子，否則令rchild域指示其后繼.

其中:

C語言表述的存儲結(jié)構(gòu)如下:

2 線索二叉樹的實(shí)驗(yàn)研究

在對線索化的二叉樹遍歷過程中發(fā)現(xiàn)大部分“數(shù)據(jù)結(jié)構(gòu)”教材中實(shí)現(xiàn)二叉樹線索化的算法存在問題，容易引起死機(jī).通過反復(fù)實(shí)驗(yàn)，發(fā)現(xiàn)原來教材中沒有對線索樹中非線索結(jié)點(diǎn)的LTag和RTag的指針賦值.以中序線索化為例［3］，原程序如下:

其中pre指向當(dāng)前訪問的結(jié)點(diǎn)p的前驅(qū).在別的教科書也同樣存在這個(gè)問題.

3 二叉樹線索化算法的修正

對原算法做出了修正，以中序線索化為例，修改后的程序如下:

當(dāng)當(dāng)前結(jié)點(diǎn)p有左孩子的時(shí)候，讓其左孩子的LTag標(biāo)志域?yàn)長ink.當(dāng)當(dāng)前結(jié)點(diǎn)p有右孩子的時(shí)候，讓其右孩子的RTag標(biāo)志域?yàn)長ink.

4 修正后的二叉樹算法線索化算法的實(shí)驗(yàn)證明

用VC++對修改后的算法進(jìn)行了實(shí)驗(yàn)驗(yàn)證，以二叉樹中序線索化算法為例.為了明確的輸出圖形，更好查看結(jié)果，論文對原數(shù)據(jù)結(jié)構(gòu)做出了修改，加入了結(jié)點(diǎn)的位置信息.修改如下:

修正后的算法實(shí)現(xiàn)如下:

程序輸入的原二叉樹如圖1所示:

圖1 程序中輸入的二叉樹

運(yùn)行程序后得到的遍歷結(jié)果如圖2所示:

圖2 二叉樹中序線索化結(jié)果

實(shí)驗(yàn)證明，該程序經(jīng)改正后算法運(yùn)行是正確的、可行的.

5 結(jié)束語

在實(shí)驗(yàn)過程中，論文針對“數(shù)據(jù)結(jié)構(gòu)”課程中二叉樹的線索化算法中出現(xiàn)的指針未定義指向的問題進(jìn)行了研究，給出了解決方案，并通過實(shí)踐證明改正的正確性、可行性.對提高“數(shù)據(jù)結(jié)構(gòu)”課程在理論方面教學(xué)的嚴(yán)格性和實(shí)用性具有一定的意義.

［1］T.Pavlidis.Algorithms for Graphies and Image Processing，Computer Science Press，1982.

［2］傅京孫.模式識別及其應(yīng)用［M］.北京:科學(xué)出版社，1985.

［3］嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版)［M］.北京:清華大學(xué)出版社，1997.

［4］譚卓群，楊冬青，唐世渭，等.數(shù)據(jù)結(jié)構(gòu)與算法［M］.北京:高等教育出版社，2005

［5］王國均.數(shù)據(jù)結(jié)構(gòu)－C語言描述［M］.北京:科學(xué)出版社，2005.

［6］嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)與算法分析［M］.北京:清華大學(xué)出版社，2004.

［7］吉根林，林波.數(shù)據(jù)結(jié)構(gòu)教程(C++版)［M］.北京:電工工業(yè)大學(xué)出版社，2009.

［8］耿國華.數(shù)據(jù)結(jié)構(gòu)—C語言描述［M］.北京:高等教育出版社，2005.