Question

一道数据结构题，请问，中序遍历二叉树过程时，用如图的例子，比如，当中序时，从D结点开始，D结点

RTag放的是线索，那么怎样知道D的线索指向的是B结点，也就是怎么样知道D的后继是B？谢谢指点

Answer 1

先序遍历为ABDFGEHC A是根

中序遍历为FDGBEHAC 可知A的左子树是FDGBEH 右叶结点C F是 叶结点
后序遍历为 FGDHEBCA 结合上面FGDHEB中B是根，再看中序FDGBEH(找B的左右)，可知FDG就B的左子树 EH是右子树
后序中有FGD，所以，D是根，F是左叶， G是右叶
后序中的HE说明H是叶，E是根
结果为：
A
/ \
B C
/ \
D E
/ \ \
F G H

追问

净瞎说

Answer 2

应该是进栈记录的

追问

可以再详细说明一下吗

怎样找后继？

您能根据代码帮忙分析一下，G点以后的几个结点的情况吗？

这个清楚点

谢谢，我一定采纳

这里边并没有用到栈

追答

哦，你说的是不用栈的中序遍历啊，那就是morris遍历算法，参考这篇文章讲的比较详细：网页链接

追问

具体点，我这里看不懂，您看，按常理说，G的后继结点是k，但是，我看代码里并不是这个意思，代码里j指向G以后，此时根据p=p->rchild，此时p指向G，访问G，然后回去执行while(p！=T)循环，走走走走到p->RTag==Link，然后，执行p=p->rchild，同理，p又指向N，这时N的p->LTag==Thread，p->RTag==thread，执行代码中p=p->rchild

这里糊涂了，到底访问G点之后，k点，N点是怎么处理的

谢谢您啦

追答

在这之前，因为你的这个算法和我看到的不太一样，能不能解释一下LTag，Link，Thread的含义和他们的初始值是多少？

追问

LTag意思是对应结点左标志域，RTag是对应结点的右标志域

LTag为0，表示有左子树；RTag为0，表示有右子树

若p->RTag为1，表示没有右子树，右指针域可以用来线索

p->LTag同理

Link表示和左子树或者右子树有连接

Thread表示没有子树，只有线索

追答

我理解这个过程之前是不是每个节点的LTag和RTag都已经标记好了？

追问

嗯嗯

对的

不好意思刚才在忙