樹 - 線索二叉樹 （二）

　　二叉樹的線索化

　　線索化和線索化實質

　　將二叉樹變為線索二叉樹的過程稱為 線索化

　　按某種次序將二叉樹線索化的實質是按該次序遍歷二叉樹在遍歷過程中用線索取代空指針

　　具體過程可

　　二叉樹的中序線索化

　　()分析

　　算法與中序遍歷算法類似只需要將遍歷算法中訪問結點的操作具體化為建立正在訪問的結點與其非空中序前趨結點間線索

　　該算法應附設一個指針pre始終指向剛剛訪問過的結點(pre的初值應為NULL)而指針p指示當前正在訪問的結點結點*pre是

　　結點*p的前趨而*p是*pre的後繼

　　()將二叉樹按中序線索化的算法

　　typedef enum { LinkThread} PointerTag; //枚舉值Link和Thread分別為

　　typedef struct node{

　　DataType data;

　　PointerTag ltagrtag; //左右標志

　　Struct node *lchild*rchild;

　　} BinThrNode;\\線索二叉樹的結點類型

　　typedef BinThrNode *BinThrTree;

　　BinThrNode *pre=NULL; //全局量

　　void lnorderThreading(BinThrTree p)

　　{//將二叉樹p中序線索化

　　if(p){ //p非空時當前訪問結點是*p

　　InorderThreading(p>lchild); //左子樹線索化

　　//以下直至右子樹線索化之前相當於遍歷算法中訪問結點的操作

　　p>ltag=(p>lchild)?LinkThread; //左指針非空時左標志為Link

　　//(即)否則為Thread(即)

　　p>rtag=(p>rchild)?LinkThread;

　　*(pre){ //若*p的前趨*pre存在

　　if(pre>rtag==Thread) //若*p的前趨右標志為線索

　　pre>rchild=p; //令*pre的右線索指向中序後繼

　　if(p>ltag==Thread) //*p的左標志為線索

　　p>lchild=pre; //令*p的左線索指向中序前趨

　　} // 完成處理*pre的線索

　　pre=p; //令pre是下一訪問結點的中序前趨

　　InorderThreeding(p>rehild); //右子樹線索化

　　}//endif

　　} //InorderThreading

　　()算法分析

　　和中序遍歷算法一樣遞歸過程中對每結點僅做一次訪問因此對於n個結點的二叉樹算法的時間復雜度亦為O(n)

　　二叉樹的前序線索化和後序線索化

　　前序線索化和後序線索化算法與二叉樹的中序線索化類似具體可【參見參考書】

From:http://tw.wingwit.com/Article/program/sjjg/201311/23879.html