一般树的后序遍历

Question

我目前是一名学生，他的作业涉及将二叉树方法调整为通用树方法。我唯一的问题是，我对以下通用树的后序遍历是否正确？如果是这样，那么我知道我的算法正在工作，我只是无法正确掌握后序遍历的窍门，我觉得并认为该网站可以提供帮助。

                     B
--------------------|------------------
|                   |                 |
A             ------D-----         ---I---
             |      |    |        |       |
             C      E    G        H       L
                         |
                         F

我的结果是：ACEFGDHLIB

Answer 1

你的答案在我看来是正确的。

这个技巧适用于广义树，而不仅仅是二元树。

当您找到黑点时，沿着虚线并访问节点。

重用这个图进行前序遍历只是将所有黑点旋转 180 度。有序遍历将是 90 度，但如果这不是二叉树，则是不明确的。

见http://en.wikipedia.org/wiki/Tree_traversal

来自http://www.brpreiss.com/books/opus4/html/page259.html

后序遍历最后访问根。要对一般树进行后序遍历：

按照给定的顺序对根的每个子树进行后序遍历；然后访问根。