返回信息流void buildPostThread(TBTnode *p, TBTnode *&pre) {
if (p != nullptr) {
buildInThread(p->lchild, pre);
buildInThread(p->rchild, pre);
//对下一个结点操作时 才对前驱结点的rtag和rchild进行改变，则中序遍历下最后一个结点（最右）的rtag仍然为0
//但是第一个结点的ltag和lchild会改变
if (p->lchild == nullptr) {
p->ltag = 1;
p->lchild = pre;
}
if (pre != nullptr && pre->rchild == nullptr) {
pre->rtag = 1;
pre->rchild = p;
}
pre = p;
}
}
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #100399同步于 2022/4/4
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
请教一下关于线索二叉树的问题
yb7858833
2022/4/4镜像同步7 回复
订阅后，新回复会通过你的通知中心匿名送达。
7 条回复
这个是构建中序线索二叉树的算法，很多博客和指导书都这样写的，但是有一个问题是最后一个遍历的结点（最右边的那个结点）的rtag为0，正常来说不是应该是1嘛？
比如这样一个结点
// 1
// / \
// 2 7
// / \ /
// 3 4 8
// / \
// 5 6
他这个结点7的右子结点应该也是个线索，但是这个代码运行下来实际上rtag是0
如果按我改成这样 7的rtag就是1了
void buildInThread(TBTnode *p, TBTnode *&pre) {
if (p != nullptr) {
if (p->lchild == nullptr) {
p->ltag = 1;
p->lchild = pre;
} else {
buildInThread(p->lchild, pre);
}
if (pre != nullptr && pre->rchild == nullptr) {
pre->rchild = p;
}
if (p->rchild == nullptr) {
p->rtag = 1;
}
pre = p;
p = p->rchild;
buildInThread(p, pre);
}
}
天勤上后面写了解释我没看到 他的意思是函数结束后在外部手动pre.rtag=1
【 在 Beegerous 的大作中提到: 】
: 最后那个节点的右儿子标不标成线索反正都是nullptr，应该无所谓吧，虽然按照定义来说需要rtag=1，不过应该不用那么较真
写其他遍历算法要用到 比如查找最右子树 如果不把这个rtag设为1 那么在判断是否继续往右下走时还要判断rchild ！= nullptr了
【 在 Beegerous 的大作中提到: 】
: 最后那个节点的右儿子标不标成线索反正都是nullptr，应该无所谓吧，虽然按照定义来说需要rtag=1，不过应该不用那么较真