2011年軟考程序員考試復習筆試知識點整理(18)

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

　　22、線索二叉樹

　　(1)以二叉鏈表結(jié)點數(shù)據(jù)結(jié)構(gòu)所構(gòu)成的二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，叫做線索二叉鏈表;指向結(jié)點的線性前驅(qū)或者線性后繼結(jié)點的指針叫做線索;加上線索的二叉樹稱為線索二叉樹(Threaded Binary Tree);對二叉樹以某種次序(前序、中序、后序)遍歷使其變?yōu)榫�索樹的過程叫做線索化。

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

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

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

　　由此，我們產(chǎn)生了線索二叉樹的概念。

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

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

　　要實現(xiàn)線索二叉樹，就必須定義二叉鏈表結(jié)點數(shù)據(jù)結(jié)構(gòu)如下(定義請看代碼)：

　　LnodeLtagDataRtagRnode

　　說明：

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

　　2. Ltag=1時，表示Lnode指向該結(jié)點的線性前驅(qū)結(jié)點;

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

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

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

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

　　檢索中序二叉樹某結(jié)點的線性前驅(qū)結(jié)點的算法：

　　1. 如果該結(jié)點的Ltag=1,那么Lnode就是它的線性前驅(qū);

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

　　(具體請看代碼)

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

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

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

　　(具體請看代碼)

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

　　//二叉樹線索化

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

　　#include

　　usingnamespace std;

　　enumPointerTag

　　{

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

　　};

　　structBiThrNode //線索二叉樹的結(jié)點類型

　　{

　　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("輸入先序序列('#'表示空節(jié)點)建立二叉樹：\n");

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

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

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

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

　　printf("\n");

　　return 0;

　　}

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

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

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