2011年軟考程序員考試復(fù)習(xí)筆試知識(shí)點(diǎn)整理(18)

　　更多：2011年軟考程序員考試復(fù)習(xí)筆試知識(shí)點(diǎn)整理匯總

　　22、線索二叉樹

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

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

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

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

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

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

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

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

　　LnodeLtagDataRtagRnode

　　說明：

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

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

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

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

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

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

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

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

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

　　(具體請看代碼)

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

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

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

　　(具體請看代碼)

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

　　//二叉樹線索化

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

　　#include

　　usingnamespace std;

　　enumPointerTag

　　{

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

　　};

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

　　{

　　char data;

　　PointerTag LTag; //左標(biāo)志

　　PointerTag RTag; //右標(biāo)志

　　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é)點(diǎn))建立二叉樹：\n");

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

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

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

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

　　printf("\n");

　　return 0;

　　}

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

　　2011年上半年軟考報(bào)名時(shí)間及方式匯總

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