typedef char datatype;
typedef struct node{
datatype data;
struct node *lchild,*rchild;
}bintnode;
typedef bintnode *binthrtree;
binthrtree root;
binthrtree pre=NULL;
void createbintree(binthrtree *t)
{char ch;
if((ch=getchar())==' ')
*t=NULL;
else{
*t=(binthrnode *)malloc(sizeof(binthrnode));
(*t)->data=ch;
createbintree(&(*t)->lchild)); //引用传递，要看清
createbintree(&(*t)->rchild));
}
}
void inthreading(binthrtree *p)
{if(*p)
{inthreading(&((*p)->lchild)); //按照中序遍历先对左子树穿线遍历
(*p)->ltag=((*p)->lchild)?0:1;
(*p)->rtag=((*p)->rchild)?0:1;
if(pre) //如果前序结点存在
{if(pre->rtag==1) pre->rchild=*p;
if((*p)->ltag==1) (*p)->lchild=pre;
}
pre=*p; //中序向前遍历下一个结点（链式存储）
inthreading(&((*p)->rchild));
}
}
void createthrtree(binthrtree *p)
{createbintree(p);
inthreading(p);
}
发表评论 
打印本文
推荐本文
加入收藏
返回顶部
关闭窗口
