# 思路说明

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

1. 前序遍历(PreorderTraversal,NLR):先访问根结点，然后遍历其左右子树
2. 中序遍历(InorderTraversal,LNR):先访问左子树，然后访问根节点，再访问右子树
3. 后序遍历(PostorderTraversal,LRN):先访问左右子树，再访问根结点
4. 层序遍历(levelorderTraversal):按照从上到下的层顺序访问

1. preorder: 1 2 4 7 5 3 6 8 9
2. inorder: 7 4 2 5 1 8 6 9 3
3. postorder: 7 4 5 2 8 9 6 3 1
4. level-order: 1 2 3 4 5 6 7 8 9

# 解决(Python)

#! /usr/bin/env python#coding:utf-8from collections import namedtuplefrom sys import stdoutNode= 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))#前序（pre-order，NLR）def preorder(node):if node isnotNone:print node.data,        preorder(node.left)        preorder(node.right)#中序（in-order，LNR）def inorder(node):if node isnotNone:        inorder(node.left)print node.data,        inorder(node.right)#后序（post-order，LRN）def postorder(node):if node isnotNone:        postorder(node.left)        postorder(node.right)print node.data,#层序（level-order）def levelorder(node, more=None):if node isnotNone:if more isNone:            more =[]        more +=[node.left, node.right]print node.data,if more:        levelorder(more[0], more[1:])if __name__=="__main__"print'  preorder: ',    preorder(tree)print'\t\n   inorder: ',    inorder(tree)print'\t\n postorder: ',    postorder(tree)print'\t\nlevelorder: ',    levelorder(tree)print'\n'