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

发布网友发布时间：2023-09-13 17:47

共1个回答

热心网友时间：2024-12-12 03:08

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