线索二叉树中关于线索的问题

来源：百度知道 编辑：UC知道 时间：2024/06/22 12:59:53
题目：线索二叉树
参考资料为《数据结构》- C语言描述 主编 王国钧 副主编 唐国民 苏哓萍 马 榆 科学出版社

书中P128 的 6.3.2线索二叉树

线索二叉树的数据定义为：
typedef struct Node
{
int data;
struct node *Lchild;
struct node *Rchild;
int Ltag, Rtag;
}ThreadTnode,*ThreadTtree;
void Inthread(ThreadTtree root)
if(root!=NULL)
{
Inthread(root->Lchild);
if(root->Lchild==NULl)
{
root->Ltag=1;root->Lchild=pre;
}
if(pre!=NULL&&pre->Rchild==NULL)
{
pre->Rchild=root;
pre->Rtag=1;
}
pre=root;
Inthread(root->Rchild);
}
对于此代码我有个疑问：
1.此代码中的root所指向的根结点是哪一个，root->Lchild=pre这个代码是什么意思。
2. “if(pre!=NULL&&pre->Rchild==NULL)// 此判断是什么意思
{
pre->Rchild=root; //这里是什么意思
pre->Rtag=1;
}”
此代码是如何指向后续结点的？
pre为全局变量， 这里的值是什么，
3.前续和后续结点是如何指向的，比如首结点的前续是什么，通过上面的代码是怎么表示出来的？

请各位老师帮忙详细解答一下，谢谢，最好有图解，谢谢。

我觉得你主要是不清楚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赋值。