- -
算法实现:
Bithptr *Q[maxsize]; //建队为指针类型
Bithptr *CreatTree(){
front=1;rear=0; //置空队
if(ch!='') //不是虚结点�.那么建立结点
s=(Bithptr *)malloc(sizeof(Bithptr));
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
s->rtag=0;
s->ltag=0;
if(s!=NULL&&Q[front]!=NULL) //孩子和双亲结点都不是虚结点
if(rear%2==0) Q[front]->lchild=s;
else Q[front]->rchild=s;
if(rear%2==1)front++; //结点*Q[front]的两个孩子处理完�front+1
线索化算法:
线索过程需要按照一定的顺序进展,此次程序使用的是中序遍历,所以线
索化也将使用中序线索化。
按照某种遍历顺序将二叉树线索化,只需在遍历的过程中将二叉树的每个
结点空的左右孩子的指针分别修改为指向其前驱和后继。假设其左右树为空,
那么将其左孩子域线索化,使其左孩子指针 lchild 指向其后继,并且 ltag 为 1.
要实现线索化,就要知道结点*pre 是*p 的前驱,而*p 是*pre 的后继。这
样,当遍历到结点*p 时,可以进展,假设*P 有空指针域,那么将相应的标志
为 1,;假设*p 的左线索标志已经建立 〔� p->ltag==1〕,那么可使其前驱线
索 化 , 令 p->lchild=pre ; 假 设 *pre 的 左 线 索 标 志 已 经 建 立 〔 pre-
>rtag==1〕,那么可使其后继线索化,令 pre->rchild=p;
算法实现;
void PreThread(Bithptr *root)
{
PreThread(p->lchild); //左子树线索化
if(pre&&pre->rtag==1)pre->rchild=p; //前驱结点后继线索化
if(p->lchild==NULL)
p->ltag=1;
p->lchild=pre;
if(p->rchild==NULL) //后继结点前驱线索化
- - word.zl-