论坛 › C\C++交流 › 二叉树路径问题

冷回清风暖 发表于 2020-9-7 09:02:22

二叉树路径问题

问题：
在二叉树中有两个结点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的路径。

风过无痕1989 发表于 2020-9-7 12:13:08

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

永恒的蓝色梦想 发表于 2020-9-7 12:48:50

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

{:10_277:}……

wzdr 发表于 2020-9-7 14:42:48

{:10_256:}{:10_256:} 给你顶下

sinsoledad 发表于 2020-9-10 10:45:29

加油

hornwong 发表于 2020-9-10 18:04:23

看看

WangJS 发表于 2020-9-12 10:14:41

鱼币

乐乐学编程 发表于 2020-9-14 10:07:53

还有奖励吗？

温木zou 发表于 2020-9-14 10:54:13

你这个应该去悬赏。。。

冷回清风暖 发表于 2020-9-15 08:02:37

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

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

心驰神往 发表于 2020-9-15 08:41:42

学习

查看完整版本: 二叉树路径问题