Luna Tech

Tutorials For Dummies.

Tree Traversal（树的遍历）

2021-03-07

0. 相关文章

  1. 聊聊数据类型（Data Type）
  2. 聊聊数据结构（Data Structure）
  3. 聊聊关联数组（Associative Array）
  4. 聊聊树结构（Tree）
  5. 聊聊自我平衡树（Self-balancing Tree）
  6. 树结构的两种实现方式
  7. Parse Tree

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，遍历节点。

三种方式分别是：

  1. preorder
  2. inorder
  3. postorder

1. preoder

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

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

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）的时候就用到了。

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 的顺序。

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