二叉树的线索化
#include "Stdio.h"#include "Conio.h"
#include "stdlib.h"
typedef struct threadNode/* 线索节点*/
{
char data;
int lTag,rTag;
struct threadNode *lChild,*rChild;
}threadNode,*threadTreePtr;
threadTreePtr initTree(void)/*建树*/
{
char ch;
threadTreePtr t;
ch=getchar();
if(ch=='0')
t=NULL;
else
{
t =(threadTreePtr) malloc(sizeof(threadNode));
t->data=ch;
t->lChild=initTree();
t->rChild=initTree();
}
return t;
}
void createThreadTree(threadTreePtr t,threadTreePtr pre)/*建成线索树*/
{
if(t)
{
createThreadTree( 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;
createThreadTree( t->rChild,pre);
}
}
threadTreePtr inPostNode(threadTreePtr p)
{
threadTreePtr post;
post=p->rChild;
if(p->rTag==0)
while(post->rTag==0)
post=post->lChild;
return post;
}
void showThTree(threadTreePtr t)/*遍历线索树*/
{
threadTreePtr p ;
if(t)
{
p=t;
while(p->lTag==0)
p=p->lChild;
while(p)
{
printf("%c\t",p->data);
inPostNode(p) ;
}
}
}
void show(threadTreePtr th)/*遍历树*/
{
if(th)
{
printf("%c\t",th->data);
show(th->lChild);
show(th->rChild);
}
}
int main(void)
{
threadTreePtr tree ,thTree;
tree =(threadTreePtr)malloc(sizeof(threadNode));
thTree=(threadTreePtr)malloc(sizeof(threadNode));
tree = initTree();
show(tree);
printf("\n");
createThreadTree(tree,thTree);
showThTree(tree);
getch();
return 0;
}
/*源码于上，问题出在线索化的过程中。哪位帮我改改，感激不尽*/
