1. 線索二叉樹存儲(chǔ)結(jié)點(diǎn)結(jié)構(gòu)
typedef struct BiThrNode{
//數(shù)據(jù)
CElemType data;
//左右孩子指針
struct BiThrNode *lchild,*rchild;
//左右標(biāo)記
PointerTag LTag;
PointerTag RTag;
}BiThrNode,*BiThrTree;
2. 構(gòu)造二叉樹
Status CreateBiThrTree(BiThrTree *T){
CElemType h;
//scanf("%c",&h);
//獲取字符
h = str[indexs++];
if (h == Nil) {
*T = NULL;
}else{
*T = (BiThrTree)malloc(sizeof(BiThrNode));
if (!*T) {
exit(OVERFLOW);
}
//生成根結(jié)點(diǎn)(前序)
(*T)->data = h;
//遞歸構(gòu)造左子樹
CreateBiThrTree(&(*T)->lchild);
//存在左孩子->將標(biāo)記LTag設(shè)置為Link
if ((*T)->lchild) (*T)->LTag = Link;
//遞歸構(gòu)造右子樹
CreateBiThrTree(&(*T)->rchild);
//存在右孩子->將標(biāo)記RTag設(shè)置為Link
if ((*T)->rchild) (*T)->RTag = Link;
}
return OK;
}
3. 中序遍歷二叉樹T, 將其中序線索化,Thrt指向頭結(jié)點(diǎn)
BiThrTree pre; /* 全局變量,始終指向剛剛訪問過的結(jié)點(diǎn) */
/* 中序遍歷進(jìn)行中序線索化*/
void InThreading(BiThrTree p){
/*
InThreading(p->lchild);
.....
InThreading(p->rchild);
*/
if (p) {
//遞歸左子樹線索化
InThreading(p->lchild);
//無左孩子
if (!p->lchild) {
//前驅(qū)線索
p->LTag = Thread;
//左孩子指針指向前驅(qū)
p->lchild = pre;
}else
{
p->LTag = Link;
}
//前驅(qū)沒有右孩子
if (!pre->rchild) {
//后繼線索
pre->RTag = Thread;
//前驅(qū)右孩子指針指向后繼(當(dāng)前結(jié)點(diǎn)p)
pre->rchild = p;
}else
{
pre->RTag = Link;
}
//保持pre指向p的前驅(qū)
pre = p;
//遞歸右子樹線索化
InThreading(p->rchild);
}
}
3. 中序遍歷二叉樹T,并將其中序線索化,Thrt指向頭結(jié)點(diǎn)
Status InOrderThreading(BiThrTree *Thrt , BiThrTree T){
*Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
if (! *Thrt) {
exit(OVERFLOW);
}
//建立頭結(jié)點(diǎn);
(*Thrt)->LTag = Link;
(*Thrt)->RTag = Thread;
//右指針回指向
(*Thrt)->rchild = (*Thrt);
/* 若二叉樹空,則左指針回指 */
if (!T) {
(*Thrt)->lchild=*Thrt;
}else{
(*Thrt)->lchild=T;
pre=(*Thrt);
//中序遍歷進(jìn)行中序線索化
InThreading(T);
//最后一個(gè)結(jié)點(diǎn)rchil 孩子
pre->rchild = *Thrt;
//最后一個(gè)結(jié)點(diǎn)線索化
pre->RTag = Thread;
(*Thrt)->rchild = pre;
}
return OK;
}
4.中序遍歷二叉線索樹T
Status InOrderTraverse_Thr(BiThrTree T){
BiThrTree p;
p=T->lchild; /* p指向根結(jié)點(diǎn) */
while(p!=T)
{ /* 空樹或遍歷結(jié)束時(shí),p==T */
while(p->LTag==Link)
p=p->lchild;
if(!visit(p->data)) /* 訪問其左子樹為空的結(jié)點(diǎn) */
return ERROR;
while(p->RTag==Thread&&p->rchild!=T)
{
p=p->rchild;
visit(p->data); /* 訪問后繼結(jié)點(diǎn) */
}
p=p->rchild;
}
return OK;
}