Question

线索二叉树问题

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define thread 1
#define link 0
typedef struct tnode
{
char data;
struct tnode *lchild;
struct tnode *rchild;
int ltag;
int rtag;
}TNode;
TNode *pre;
/*
**创建二叉树
*/
TNode *
creat_tree()
{
TNode *p;
char data;
scanf("%c",&data);
if(data=='@')return NULL;
else {
p=(TNode *)malloc(sizeof(TNode));
assert(p!=NULL);
p->data=data;
p->lchild=creat_tree();
p->rchild=creat_tree();
}
return p;
}
/*
**建立线索二叉树
*/
void
creat_threadtree(TNode *p)
{
if(p){
creat_threadtree(p->lchild);
if(p->lchild==NULL){
p->ltag=thread;
p->lchild=pre;
}
if(pre->rchild==NULL){
pre->rtag=thread;
pre->rchild=p;
}
pre=p;
creat_threadtree(p->rchild);
}
}
/*
**输出二叉树中的值
*/
void
show_tree(TNode *T)
{
TNode *p;
p=T->lchild;
while(p!=T){
while(p->lchild!=NULL)p=p->lchild;
printf("%c",p->data);
while(p->rtag==thread&&p->rchild!=T){
p=p->rchild;
printf("%c",p->data);
}
p=p->rchild;
}
}
int
main()
{
TNode *T;
T->ltag=link;
T->lchild=creat_tree();
pre=T;
creat_threadtree(T->lchild);
show_tree(T);
return 0;
}
请哪位大虾看下我的程序哪里错了？谢谢！

Answer 1

线索二叉树问题
觉得你主要是不清楚pre指向的是什么。

我的数据结构书是严蔚敏版的，书上是这么说的：pre始终指向刚刚访问过的结点，若指针root指向当前访问的结点，则pre指向它的前续。
说的有点抽象。其实主要就是要清楚何时改变pre的值，“pre始终指向刚刚访问过的结点”就是说访问完一个结点后，就改变pre的值。
具体的思路是这样：首先书上建立线索的代码是一个中序遍历过程，其访问顺序分三步：左子树->本身结点->右子树。其中访问左子树就是指调用函数Inthread(root->Lchild)。任何一次访问结点的操作必然处在这三步中的第二步，因为第一步又可以分为三步。可见pre值的修改应该在第二步之后，且在第三步之前，即在Inthread(root->Rchild)之前。正如代码中一样。
另外要注意第一次调用Inthread前要先给pre赋值。

1.此代码中的root可能指向的是二叉树中的任意一结点，由于任意一结点可以看做一个子树的根节点，所以可以理解为root指向二叉树本身或其子树的根节点。
root->Lchild=pre这个代码是说让当前结点的左子树指向当前结点的前驱(pre)，即建立一个前续索引。

2.此代码主要是判断是否要给pre建立一个后续线索。那么建立后续线索的前提条件是要右结点为空，这就是if中的判断。
pre->Rchild=root就是给pre建立一个后续索引。pre是root的前续，反过来root就是pre的后续。

3.前续和后续结点的指向通过pre与root互为前续后续的关系实现的。以首结点为例的话比较特殊，因为如果root指向首结点，那么这就是第一次调用，在调用前要预先给pre赋值。

Answer 2

我自己想了一个简单的方法，用到队列，简单，易理解，其实自己遇到问题多画画就懂了，书上的比较绕一些，你的程序哪出错楼下的兄弟已经说了，好用的话求给分啊

先把二叉树给标记化：既设置两个标记Ltag，Rtag，如果左孩子指针为空，Ltag=1，如果右孩子指针为空，Rtag=1。

先序（中序，后序）遍历线索二叉树：
首先进行先序（中序，后序）遍历，然后把得到的节点依次入队

然后把队列里的节点依次根据标记（先把队里首节点Ltag=0，因为队首的前驱为空）线索化，如果Ltag=1，左指针指向队里前一个元素，如果Rtag=1，右指针指向队里后一个元素。