树的遍历

数据结构

• 创建树：

#!/bin/python
#-*- coding = utf-8 -*-
class tree:
    def __init__(self,data):
        self.left = None
        self.right = None
        self.data = data
    def insert(self,data):
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = tree(data)
                else:
                    self.left.insert(data)
            if data >  self.data:
                if self.right is None:
                    self.right = tree(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data
    def printTree(self):
        if self.left:
            self.left.printTree()
        print(self.data)
        if self.right:
            self.right.printTree()

• 数据测试

root = tree(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
root.printTree()
print(root.inorder(root))

中序遍历

将每个节点理解成一棵树，然后按照从左子树-根-右子树的顺序逐级遍历，从最底层开始。

    def inorder(self,root):
        result = []
        if root:
            result = self.inorder(root.left)
            result.append(root.data)
            result += self.inorder(root.right)
        return result

前序遍历

将每个节点理解成一棵树，然后按照从根-左子树-右子树的顺序逐级遍历，从根开始。

    def preorder(self,root):
        result = []
        if root:
            result.append(root.data)
            result += self.inorder(root.left)
            result += self.inorder(root.right)
        return result

后序遍历

将每个节点理解成一棵树，然后按照从左子树-右子树-根的顺序逐级遍历，从最底层左子树开始。

    def postorder(self,root):
        result = []
        if root:
            result += self.inorder(root.left)
            result += self.inorder(root.right)
            result.append(root.data)
        return result