考虑以下树形结构。
使用后序遍历、前序遍历和中序遍历，节点的访问顺序分别是什么？
A
/ \
B C
/ \ \
D E F
使用后序遍历、前序遍历和中序遍历，节点的访问顺序分别是什么？
后序遍历、先序遍历、中序遍历，二叉搜索树
3
- user3500147
7
http://en.wikipedia.org/wiki/Tree_traversal - Sotirios Delimanolis
1这与Java无关。 - Sotirios Delimanolis
4“嗅嗅声*，你闻到了吗？这闻起来像功课。” - rayryeng
4这个问题似乎不符合主题，因为它与编程无关。 - rayryeng
1嘿，重新打开它，我在这里学到了新东西。这对像我这样的半吊子程序员很有好处。这不是一个针对programmers.stackexchange.com的哲学问题，而是关于算法术语的具体问题。 - Boris Stitnicky
显示剩余2条评论
1个回答
9
我发现把后序遍历，先序遍历和中序遍历看作是递归算法很有帮助。
后序遍历 递归地进行左子树、右子树、自身的遍历。也就是说，先对左子树进行遍历，再对右子树进行遍历，最后访问当前节点。当节点没有子节点时，递归基本情况出现。
以此例为例：D, E, B, F, C, A
解释： 1. 从节点A开始。评估左子树。在B节点。评估左子树。在D节点。没有子节点 -> 访问D。 2. 回到B。评估右子树。在E节点。没有子节点 -> 访问E。 3. 回到B。访问B。 4. 回到A。评估右子树。在C节点。没有左子树，所以评估右子树。在F节点。没有子节点 -> 访问F。 5. 回到C。访问C。 6. 回到A。访问A。
先序遍历 递归地进行自身、左子树、右子树的遍历。
尝试使用后序遍历的逻辑自己得到答案。
中序遍历 递归地进行左子树、自身、右子树的遍历。
尝试使用后序遍历的逻辑自己得到答案。
如果您想检查您的答案， 先序遍历为A，B，D，E，C，F，中序遍历为D，B，E，A，C，F。
后序遍历 递归地进行左子树、右子树、自身的遍历。也就是说，先对左子树进行遍历，再对右子树进行遍历，最后访问当前节点。当节点没有子节点时，递归基本情况出现。
以此例为例：D, E, B, F, C, A
解释： 1. 从节点A开始。评估左子树。在B节点。评估左子树。在D节点。没有子节点 -> 访问D。 2. 回到B。评估右子树。在E节点。没有子节点 -> 访问E。 3. 回到B。访问B。 4. 回到A。评估右子树。在C节点。没有左子树，所以评估右子树。在F节点。没有子节点 -> 访问F。 5. 回到C。访问C。 6. 回到A。访问A。
先序遍历 递归地进行自身、左子树、右子树的遍历。
尝试使用后序遍历的逻辑自己得到答案。
中序遍历 递归地进行左子树、自身、右子树的遍历。
尝试使用后序遍历的逻辑自己得到答案。
如果您想检查您的答案， 先序遍历为A，B，D，E，C，F，中序遍历为D，B，E，A，C，F。
- Nick Meyer
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接