線索化

簡介

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

（1）分析

算法根據二叉樹遍歷的方式而定。只需要將遍歷算法中訪問結點的操作具體化為建立正在訪問的結點與其非空中序前趨結點間線索。

該算法應附設一個指針pre始終指向剛剛訪問過的結點（pre的初值應為NULL），而指針p指示當前正在訪問的結點。結點*pre是結點*p的前趨，而*p是*pre的後繼。

（2）將二叉樹按中序線索化的算法

typedef enum { Link，Thread} PointerTag； //枚舉值Link和Thread分別為0，1

typedef struct node{

DataType data；

PointerTag ltag，rtag； //左右標誌

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)?Link：Thread； //左指針非空時左標誌為Link

//(即0)，否則為Thread(即1)

p->rtag=(p->rchild)?Link：Thread；

*(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

（3）算法分析

遞歸過程中對每結點僅做一次訪問，因此對於n個結點的二叉樹，算法的時間複雜度亦為O(n)。