学步园

对于任一结点，可以按某种次序执行三个操作：

• 访问结点本身（N）
• 遍历该结点的左子树（L）
• 遍历该结点的右子树（R）

用来表示顺序,即,前序NLR/中序LNR/后序LRN.

下面我们用namedtuple来表达树,而通杀的遍历函数带一个order参数,只要我们把指定顺序传进去即可实现对应的遍历.

#coding=utf-8
'''
         1
        / \
       /   \
      /     \
     2       3
    / \     /
   4   5   6
  /       / \
 7       8   9
'''

from collections import namedtuple
from sys import stdout

Node = namedtuple('Node', ['data','left','right'])
tree = Node(1,
            Node(2,
                 Node(4,
                      Node(7, None, None),
                      None),
                 Node(5, None, None)),
            Node(3,
                 Node(6,
                      Node(8, None, None),
                      Node(9, None, None)),
                 None))

def visitor(i):
    stdout.write("%i "%i)

def traversal(node, order):#这个是主角,通杀函数
    if not node:return
    op = {
            'N':lambda:visitor(node.data),
            'L':lambda:traversal(node.left, order),
            'R':lambda:traversal(node.right, order),
    }
    for x in order:
        op[x]()

for order in ['NLR', 'LNR', 'LRN']:
    traversal(tree, order)
    print