关于实现二叉树中序线索化的问题
这是我写的程序,可以运行但是结果不对,请大神指教#include"stdio.h"
#include"malloc.h"
typedef char DataType;
typedef struct Threadnode{
int ltag,rtag;
DataType data;
struct Threadnode *lchild,*rchild;
}Threadnode,*ThreadTree;
Threadnode *creat_Btree()
{
ThreadTree p;
char ch;
ch=getchar();
if(ch=='#')
p=NULL;
else{
p=(Threadnode *)malloc(sizeof(Threadnode));//生成新结点
p->data=ch;
p->ltag=0;
p->rtag=0;
p->lchild=creat_Btree();//创建新结点的左子树
p->rchild=creat_Btree();//创建新结点的右子树
}
return p;
}
ThreadTree InThread(ThreadTree t,ThreadTree pre){
if(t){
InThread(t->lchild,pre);
if(t->lchild==NULL){
t->ltag=1;
t->lchild=pre;
}
if(t->rchild==NULL)
t->rtag=1;
if((pre)&&(pre->rtag==1))
pre->rchild=t;
pre=t;
InThread(t->rchild,pre);
}
return t;
}
ThreadTree InPostNode(ThreadTree p){
ThreadTree post;
post=p->rchild;
if(p->rtag==1)
return post;
else
while(post->ltag==0)
post=post->lchild;
return post;
}
void InOrderTh(ThreadTree t){
ThreadTree p;
if(t){
p=t;
while(p->ltag==0)
p=p->lchild;
while(p){
printf("%c->",p->data);
p=InPostNode(p);
}
}
}
main(){
printf("输入先序线索二叉树:\n");
ThreadTree t=creat_Btree(),pre;
pre=NULL;
t=InThread(t,pre);
printf("中序线索化遍历:\n");
InOrderTh(t);
}