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

冷回清风暖

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

1. //先序遍历
   
2. bool PreOrder(BiTree t)
   
3. {
   
4.     if (!t)
   
5.         return false;
   
6.     visit(t);
   
7.     //printf("%2c", t->data);
   
8.     PreOrder(t->lchild);
   
9.     PreOrder(t->rchild);
   
10.     return true;
    
11. }
    
12. //中序遍历
    
13. bool InOrder(BiTree t)
    
14. {
    
15.     if (!t)
    
16.         return false;
    
17.     InOrder(t->lchild);
    
18.     printf("%2c", t->data);
    
19.     InOrder(t->rchild);
    
20.     return true;
    
21. }//后序遍历
    
22. bool LastOrder(BiTree t)
    
23. {
    
24.     if (!t)
    
25.         return false;
    
26.     LastOrder(t->lchild);
    
27.     LastOrder(t->rchild);
    
28.     printf("%2c", t->data);
    
29.     return true;
    
30. }

复制代码

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

最佳答案

月排行榜 / 总排行榜

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
你这个应该去悬赏。。。

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

心驰神往

学习