線索二叉樹算法的實驗與實現

郭小春，王 紅

(1.泰山學院信息科學技術學院，山東泰安 271021;2.泰山職業技術學院財經系，山東泰安 271000)

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

遍歷二叉樹是以一定規則將二叉樹中結點排列成一個線性序列，得到二叉樹中結點的先序序列、中序序列或后序序列.這實質上是對一個非線性結構進行線性化操作，使每個結點(除第一個和最后一個外)在這些線性序列中有且僅有一個直接前驅和直接后繼.但是，當以二叉鏈表作為存儲結構時，只能找到結點的左、右孩子信息，而不能直接得到結點在任一序列中的前驅和后繼信息，這種信息只有在遍歷的動態過程中才能得到.解決這個問題的方法是:當第一次遍歷二叉樹時，就在各結點的空余域中加線索，加線索的二叉樹就稱為線索二叉樹.加線索之后，當再遍歷時，就可在某些結點沿著線索走，從而簡化操作［3－8］.

經過算法分析和實驗發現現有絕大部分“數據結構”教科書中對二叉樹的線索化實現算法存在錯誤，沒有對線索樹中非線索結點的LTag和RTag的指針賦值.為了解決這一問題提高數據結構課程在理論方面教學的嚴格性和實用性，對二叉樹線索化的算法進行了修正和實現.

1 線索二叉樹的基礎知識

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

線索二叉樹的結點的存儲結構及意義如下:若結點有左子樹，則其lchild域指示其左孩子，否則令lchild指示其前驅;若結點有右子樹，則其rchild域指示其右孩子，否則令rchild域指示其后繼.

其中:

C語言表述的存儲結構如下:

2 線索二叉樹的實驗研究

在對線索化的二叉樹遍歷過程中發現大部分“數據結構”教材中實現二叉樹線索化的算法存在問題，容易引起死機.通過反復實驗，發現原來教材中沒有對線索樹中非線索結點的LTag和RTag的指針賦值.以中序線索化為例［3］，原程序如下:

其中pre指向當前訪問的結點p的前驅.在別的教科書也同樣存在這個問題.

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

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

當當前結點p有左孩子的時候，讓其左孩子的LTag標志域為Link.當當前結點p有右孩子的時候，讓其右孩子的RTag標志域為Link.

4 修正后的二叉樹算法線索化算法的實驗證明

用VC++對修改后的算法進行了實驗驗證，以二叉樹中序線索化算法為例.為了明確的輸出圖形，更好查看結果，論文對原數據結構做出了修改，加入了結點的位置信息.修改如下:

修正后的算法實現如下:

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

圖1 程序中輸入的二叉樹

運行程序后得到的遍歷結果如圖2所示:

圖2 二叉樹中序線索化結果

實驗證明，該程序經改正后算法運行是正確的、可行的.

5 結束語

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

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

［2］傅京孫.模式識別及其應用［M］.北京:科學出版社，1985.

［3］嚴蔚敏，吳偉民.數據結構(C語言版)［M］.北京:清華大學出版社，1997.

［4］譚卓群，楊冬青，唐世渭，等.數據結構與算法［M］.北京:高等教育出版社，2005

［5］王國均.數據結構－C語言描述［M］.北京:科學出版社，2005.

［6］嚴蔚敏.數據結構與算法分析［M］.北京:清華大學出版社，2004.

［7］吉根林，林波.數據結構教程(C++版)［M］.北京:電工工業大學出版社，2009.

［8］耿國華.數據結構—C語言描述［M］.北京:高等教育出版社，2005.