Question

二叉树的线索化以及输出问题 数据结构

#include<stdio.h>#include<stdlib.h>
#define maxsize 1024

struct node{
int data;
struct node * lchild , * rchild;
int ltag,rtag;
};

typedef struct node bitree;
bitree * pre;
/*creat*/bitree * creat()
{
char ch;
int front,rear;
bitree * root,* s,* Q[maxsize];
root = NULL;
front = 1;
rear = 0;
printf("enter the Binary Tree:\n");
ch = getchar();
while(ch != '#')
{
s = NULL;
if(ch != '@')
{
s = (bitree *)malloc(sizeof(bitree));
s->data = ch;
s->lchild = NULL;
s->rchild = NULL;
}
rear ++;
Q[rear] = s;
if(rear == 1) root = s;
else
{
if(s && Q[front])
if(rear % 2 == 0) Q[front]->lchild = s;
else
Q[front]->rchild = s;
if(rear % 2 == 1) front ++;
}
ch = getchar();
}
return root;
}

/*overitPR*/bitree PREORDER(bitree * p)
{
if(p)
{
printf(" %c",p->data);
PREORDER(p->lchild);
PREORDER(p->rchild);
}
}

/*overitME*/bitree INORDER(bitree * p)
{
if(p)
{
INORDER(p->lchild);
printf(" %c",p->data);
INORDER(p->rchild);
}
}

/*overitPO*/bitree POSTORDER(bitree * p)
{
if(p)
{
POSTORDER(p->lchild);
POSTORDER(p->rchild);
printf(" %c",p->data);
}
}

/*set a clue*/bitree INTHREAD(bitree * p)
{

if(p != NULL)
{
INTHREAD(p->lchild);
if(p->lchild == NULL) p->ltag = 1;
if(p->rchild == NULL) p->rtag = 1;
if(pre != NULL)
{
if(pre->rtag == 1) pre->rchild = p;
if(p->ltag == 1) p->lchild = pre;
}
pre = p;
INTHREAD(p->rchild);
}
}

/*find*/bitree * INORDERNEXT(bitree * p)
{
bitree * q;
if(p->rtag == 1) return (p->rchild);
else
{
q = p->rchild;
while(q->ltag == 0);
q = q->lchild;
return(q);
}
}

/*over it within clue*/bitree TRAVERSEINTHREAD(bitree * p)
{
if(p != NULL)
{
while(p->ltag == 0);
p = p->lchild;
do
{
printf(" %d",p->data);
p = INORDERNEXT(p);
}while(p != NULL);
}
}

void main()
{
bitree * p;
p = creat();
// PREORDER(t);
// printf("\n");
INORDER(p);
printf("\n");
// POSTORDER(t);
// printf("\n");
INTHREAD(p);
// INORDERNEXT(p);
TRAVERSEINTHREAD(p);

}
不知道怎么输出线索化的二叉树 请大家指点

Answer 1

利用遍历后继结点输出线索化的二叉树
如下：

//在中序线索二叉树中确定x所指结点的直接后继结点
//1.当x->rbit=0时，x->rchild指出的结点就是x的直接后继结点
//2.当x->rbit=1时，沿着x结点右子树的根的左指针链往下找，直到某结点的lchild域为线索
TBTree Insucc(TBTree x)
{
TBTree s;
s=x->rchild;
if(x->rbit==1)
while(s->rbit==1)
s=s->lchild;
return s;
}

//利用线索二叉树遍历二叉树
void TInOrder(TBTree Head)
{
TBTree p=Head;
while(1)
{
p=Insucc(p);
if(p==Head)
break;
printf("%c ",p->data);
}
printf("\n");
}

追问

没有看懂，
我的程序里面也没有定义头结点
所以还是不知道该什么解决，
能就上面我给出的程序给出解决方案吗？谢谢

追答

我那个不是头结点，是根结点，名起的不好……你的p不就是根结点吗，你在creat（）方法里不是返回了一个root吗，那个就是我的函数里的head啊，遍历的时候是用的这两个函数联合的，你在主函数里面加上那个TInOrder（p）的方法，再把我的TBTree改成你那个bitree的类型，然后加到主函数前面去就好了……

追问

TBTree Insucc(TBTree x) 做了相应的修改 但编译说return 返回不兼容的类型
void TInOrder(TBTree Head) 里面是要把head直接换成我的root吗？