java - 一般树的后序遍历

Question

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

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

我的结果是:A C E F G D H L I B

Answer 1

我觉得你的回答是正确的。

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

沿着虚线走，找到黑点就访问节点。

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

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

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

postorder traversal visits the root last. To do a postorder traversal of a general tree:

Do a postorder traversal each of the subtrees of the root one-by-one in the order given; and thenvisit the root.