6.8.3 建立线索二叉树及其销毁.pptxVIP

6.8.3建立线索二叉树及其销毁;算法思想：先创建一个头结点head，在进行中序遍历过程中需保留当前结点p的前驱结点的指针，设为pre（全局变量，初值时指向头结点）。

在p不空的情况下：;中序线索二叉树过程：;BthNode*CreaThread(BthNode*bt)

//对以bt为根结点的二叉树中序线索化,并增加一个头结点head

{BthNode*head;

head=(BthNode*)malloc(sizeof(BthNode));

head-ltag=0;head-rtag=1;//创建头结点head

head-rchild=bt;

if(bt==NULL) //bt为空树时

head-lchild=head;

else

{ head-lchild=bt;

pre=head; //pre是p的前驱结点,供加线索用

Thread(bt); //中序遍历线索化二叉树

pre-rchild=head; //最后处理,加入指向根结点的线索

pre-rtag=1;

head-rchild=pre; //根结点右线索化

}

returnhead;

};BthNode*pre; //定义pre为全局变量

voidThread(BthNode*p)

//对以p为根结点的二叉树进行中序线索化

{if(p!=NULL)

{Thread(p-lchild); //左子树线索化

if(p-lchild==NULL) //前驱线索

{p-lchild=pre; //给结点p添加前驱线索

p-ltag=1;

}

elsep-ltag=0;

if(pre-rchild==NULL)

{pre-rchild=p; //给结点pre添加后继线索

pre-rtag=1;

}

elsepre-rtag=0;

pre=p;

Thread(p-rchild); //右子树线索化

}

};当建立好一棵中序线索二叉树tb后，销毁tb的过程是先销毁原来的二叉链，最后释放头结点。