Luna Tech | Tree Traversal（树的遍历）

March 7, 2021 字数 849 2 min

0. 相关文章

1. Tree Traversals (树的遍历)

Reference: https://runestone.academy/runestone/books/published/pythonds3/Trees/TreeTraversals.html

树有三种常见的模式（Usage pattern）用来 access node，这些 pattern 的不同之处在于遍历 node 的顺序。

Traversal: visitation of the nodes，遍历节点。

三种方式分别是：

preorder
inorder
postorder

1. preoder

先找根节点，然后用preorder去遍历左边的subtree，再用preoder去遍历右边的subtree。

The code for writing tree traversals is surprisingly elegant, largely because the traversals are written recursively.

1
2
3
4
5


def preorder(tree):
    if tree:
        print(tree.get_root_val())
        preorder(tree.get_left_child())
        preorder(tree.get_right_child())

2. postorder

先在左边的subtree用postorder遍历一遍，然后再用postorder去遍历右边的subtree，最后visit root node。

从代码可以看到，跟 preorder 唯一的区别就是 access root 的顺序。

另外，postorder的逻辑其实在第三部分（parse tree）的时候就用到了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


def postorder(tree):
    if tree:
        postorder(tree.get_left_child())
        postorder(tree.get_right_child())
        print(tree.get_root_val())

# postorder pattern 可以用于 parse tree，唯一的区别是这里我们 return key，而不是 print key。
def postordereval(tree):
    operators = {
        "+": operator.add,
        "-": operator.sub,
        "*": operator.mul,
        "/": operator.truediv,
    }
    result_1 = None
    result_2 = None
    if tree:
        result_1 = postordereval(tree.get_left_child())
        result_2 = postordereval(tree.get_right_child())
        if result_1 and result_2:
            return operators[tree.get_root_val()](result_1, result_2)
        else:
            return tree.get_root_val()

3. inorder

先在左边的subtree用inorder遍历一遍，再去 root node，最后用inorder去遍历右边的subtree。

从代码可以看到，跟 preorder 唯一的区别就是 access root 的顺序。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


def inorder(tree):
    if tree:
        inorder(tree.get_left_child())
        print(tree.get_root_val())
        inorder(tree.get_right_child())
        
# 假如我们用 inorder 来遍历 parse tree 的话，我们可以得到一开始的表达式（不带任何括号）；
# 在经过简单的修改之后，我们也可以得到一个全括号的表达式（fully parenthesized version expression）；
# 唯一的修改就是打印左/右 subtree 的时候加上括号，但这个 function 有缺点，在每个数字上都有括号，需要进一步完善。
def print_exp(tree):
    result = ""
    if tree:
        result = "(" + print_exp(tree.get_left_child())
        result = result + str(tree.get_root_val())
        result = result + print_exp(tree.get_right_child()) + ")"
    return result

# 改进版 # TODO
def print_exp(tree):
    result = ""
    if tree:
        result = "(" + print_exp(tree.get_left_child())
        result = result + str(tree.get_root_val())
        result = result + print_exp(tree.get_right_child()) + ")"
    return result