algorithm - 写出给定一棵树 : 的前序、中序和后序遍历

Question

好的，鉴于这棵树，我需要为它写出前序、中序和后序遍历。

                                     9
                                  /     \
                                 5       12
                                / \     /  \
                               2   7   11   15
                              /   /   /  \    \
                             3   6   10  13    16
                                                 \
                                                  17

这是我想出来的，我的老师没有很好地复习这个，所以我不确定我是否接近正确。

       pre-order: 9 5 2 3 7 6 12 11 10 13 15 16 17
       in-order: 3 2 5 7 6 9 12 11 10 13 15 16 17
       post-order: 3 2 6 7 5 10 11 17 16 15 13 12 9

任何帮助将不胜感激

Answer 1

预序:做一次深度优先遍历，第一次遇到节点就写出来。所以这是正确的 (9 5 2 3 7 6 12 11 10 13 15 16 17)。

后序:进行深度优先遍历并在处理完所有子节点后写出节点。所以正确的顺序是 (3 2 6 7 5 10 13 11 17 16 15 12 9)。

有序:进行深度优先遍历，首先写出左子树，然后是节点本身，最后是右子树。所以正确的顺序是(3 2 5 6 7 9 10 11 13 12 15 16 17)。这里单个 child 是左还是右是有区别的，对于其他方法无关紧要。