更多：2011年軟考程序員考試復習筆試知識點整理匯總

　　22、線索二叉樹

　　(1)以二叉鏈表結點數據結構所構成的二叉鏈表作為二叉樹的存儲結構，叫做線索二叉鏈表;指向結點的線性前驅或者線性后繼結點的指針叫做線索;加上線索的二叉樹稱為線索二叉樹(Threaded Binary Tree);對二叉樹以某種次序(前序、中序、后序)遍歷使其變為線索樹的過程叫做線索化。

　　(2)[為什么要有線索二叉樹]二叉樹是一種非線性結構，對二叉樹的遍歷實際上是將二叉樹這種非線性結構按某種需要轉化為線性序列，以便以后在對二叉樹進行某種處理時直接使用。因此如何保存遍歷二叉樹后得到的線性序列，以避免對二叉樹的重復遍歷，是一個需要解決的問題。

　　一種最簡單的方法是將得到的遍歷序列存放在另外的存儲空間內，但這需要付出額外的存儲花銷。我們能不能在不增加存儲空間的前提下，在原來二叉鏈表的存儲空間內反映出某種遍歷后結點的邏輯關系，即遍歷后某個結點的直接前驅和直接后繼呢?

　　另一種方法就是：當我們用標準形式存儲一棵二叉樹時，樹中有一半以上的指針是空的。對于一棵具有n個結點的二叉樹，如果按標準形式來存儲，那么總共有2n個指針(用來存放左孩子、右孩子的指針)其中只有(n-1)個用來指向子結點，另外(n+1)個指針時空的。這顯然是浪費，我們應該設法利用這些空的指針來實現保存遍歷二叉樹后得到的線性序列。

　　由此，我們產生了線索二叉樹的概念。

　　線索二叉樹主要是為了解決查找結點的線性前驅與后繼不方便的難題。它只增加了兩個標志性域，就可以充分利用沒有左或右孩子的結點的左右孩子的存儲空間來存放該結點的線性前驅結點與線性后繼結點。兩個標志性域所占用的空間是極少的，所有充分利用了二叉鏈表中空閑存的儲空間。

　　對一棵給定的二叉樹，按不同的遍歷規則進行線索化所得到的線索樹是不同的，分別用前序、中序、后序遍歷規則，對給定二叉樹進行線索化得到的二叉樹，分別稱之為前序線索樹、中序線索樹、后序線索樹。

　　要實現線索二叉樹，就必須定義二叉鏈表結點數據結構如下(定義請看代碼)：

　　LnodeLtagDataRtagRnode

　　說明：

　　1. Ltag=0時，表示Lnode指向該結點的左孩子;

　　2. Ltag=1時，表示Lnode指向該結點的線性前驅結點;

　　3. Rtag=0時，表示Rnode指向該結點的右孩子;

　　4. Rtag=1時，表示Rnode指向該結點的線性后繼結點;

　　中序次序線索化二叉樹算法：

　　中序次序線索化是指用二叉鏈表結點數據結構建立二叉樹的二叉鏈表，然后按照中序遍歷的方法訪問結點時建立線索;(具體看代碼)

　　檢索中序二叉樹某結點的線性前驅結點的算法：

　　1. 如果該結點的Ltag=1,那么Lnode就是它的線性前驅;

　　2. 如果該結點的Ltag=0，那么該結點左子樹最右邊的尾結點就是它的線性前驅點;

　　(具體請看代碼)

　　檢索中序二叉樹某結點的線性后繼結點和算法：

　　1. 如果該結點的Rtag=1,那么Rnode就是它的線性后繼結點;

　　2. 如果該結瞇的Rtag=0,那么該結點右子樹最左邊的尾結點就是它的線性后繼結點

　　(具體請看代碼)

　　解決方案中所有到二叉樹的中序線索二叉樹和中序線索鏈表的圖

　　//二叉樹線索化

　　//輸入二叉樹先序，建樹，然后中序線索化，遍歷輸出

　　#include

　　usingnamespace std;

　　enumPointerTag

　　{

　　Link,Thread //枚舉值Link和Thread分別為0，1

　　};

　　structBiThrNode //線索二叉樹的結點類型

　　{

　　char data;

　　PointerTag LTag; //左標志

　　PointerTag RTag; //右標志

　　BiThrNode *lchild; //左孩子指針

　　BiThrNode *rchild; //右孩子指針

　　};

　　typedefBiThrNode* BiThrTree;

　　BiThrNode*pre=NULL; //全局量

　　voidInOrderThreading(BiThrTree & Thrt,BiThrTree T);//線索化

　　voidInThreading(BiThrTree p);//中序遍歷線索化

　　boolPreOrderCreatBiTree(BiThrTree &T);//先序建立樹

　　voidInOrderTraverse_Thr(BiThrTree T);//中序遍歷線索樹

　　intmain()

　　{

　　BiThrTree T,Thrt;

　　printf("輸入先序序列('#'表示空節點)建立二叉樹：\n");

　　PreOrderCreatBiTree(T);//先序建立樹

　　InOrderThreading(Thrt,T);//中序線索化

　　printf("中序線索化，中序遍歷得中綴式：\n");

　　InOrderTraverse_Thr(Thrt);//中序遍歷線索樹

　　printf("\n");

　　return 0;

　　}

　　軟考程序員考試歷年真題重點題總結及答案

　　2011年上半年軟考報名時間及方式匯總

　　軟考程序員考試歷年真題匯總(2007年-2010年)