[已解决]二叉树路径问题

冷回清风暖

问题：
在二叉树中有两个结点m和n，若m是n的祖先，则使用（）遍历可以找到从m到n的路径。
答案是 后序遍历
但是为什么先序和中序不行呢？
我认为递归过程中使用的栈可以说是程序过程间调用的栈 首先遍历m的过程 调用了遍历a的过程 然后返回到了m 然后遍历m的过程又调用了遍历d的过程 又返回到了m 不管是前中后序哪一种遍历都是这样一个过程调用的栈的结构 根总是最后一个出栈 栈中并不是只保存了有用的节点 被调用的过程 总是会返回到调用他的过程中 程序总是这样的一个过程。
所以无论先序，中序，后序使用递归算法执行的时候递归过程相同，只是在某递归语句前后执行的语句不同。

//先序遍历
bool PreOrder(BiTree t)
{
    if (!t)
        return false;
    visit(t);
    //printf("%2c", t->data);
    PreOrder(t->lchild);
    PreOrder(t->rchild);
    return true;
}
//中序遍历
bool InOrder(BiTree t)
{
    if (!t)
        return false;
    InOrder(t->lchild);
    printf("%2c", t->data);
    InOrder(t->rchild);
    return true;
}//后序遍历
bool LastOrder(BiTree t)
{
    if (!t)
        return false;
    LastOrder(t->lchild);
    LastOrder(t->rchild);
    printf("%2c", t->data);
    return true;
}

代码对应二叉树结构如图：

最佳答案

月排行榜 / 总排行榜

sunrise085

2020-9-7 11:21:00

遍历实际上是有入栈和出栈操作的。
若 n 是右节点，那么先序遍历和中序遍历在遍历到祖先节点 m 之后 m 就出栈了。那么再去遍历到 n 节点的时候就不知道如何从m到n的了
只有后序遍历中，祖先节点 m 是最后出栈的，所以能够追溯m到n的路径。

跳转到最佳答案楼层

sunrise085

遍历实际上是有入栈和出栈操作的。
若 n 是右节点，那么先序遍历和中序遍历在遍历到祖先节点 m 之后 m 就出栈了。那么再去遍历到 n 节点的时候就不知道如何从m到n的了
只有后序遍历中，祖先节点 m 是最后出栈的，所以能够追溯m到n的路径。

风过无痕1989

回复本帖可获得 1 鱼币奖励! 每人限 1 次

永恒的蓝色梦想

风过无痕1989 发表于 2020-9-7 12:13
回复本帖可获得 1 鱼币奖励! 每人限 1 次

……

wzdr

给你顶下

sinsoledad

加油

hornwong

看看

WangJS

鱼币

乐乐学编程

还有奖励吗？

温木zou

你这个应该去悬赏。。。

冷回清风暖

温木zou 发表于 2020-9-14 10:54
你这个应该去悬赏。。。

这个问题 想了好久没向懂 感觉比较难 就附上了悬赏

心驰神往

学习