二叉树的遍历

首先是三种遍历的递归实现，思路简单，重要的是要清楚每种遍历的顺序：

1. 先序遍历： 根 --》 左子树 --》右子树
2. 中序遍历： 左子树 --》根--》右子树
3. 后序遍历： 左子树 --》右子树 --》根

首先是树的创建：

image.png

class binaryTree:
    def __init__(self, root):
        self.key = root
        self.left_child = None
        self.right_child = None
    def insert_left(self, new_node):
        if self.left_child == None:
            self.left_child = binaryTree(new_node)
        else:
            t = binaryTree(new_node)
            t.left_child = self.left_child
            self.left_child = t
    def insert_right(self, new_code):
        if self.right_child == None:
            self.right_child = binaryTree(new_code)
        else:
            t = binaryTree(new_code)
            t.right_child = self.right_child
            self.right_child = t
    def get_right_child(self):
        return self.right_child
    def get_left_child(self):
        return self.left_child
    def set_root_val(self, obj):
        self.key = obj
    def get_root_val(self):
        return self.key

递归方法：

def preOrder(root):
   if root == None:
       return
   print root.key,
   preOrder(root.left_child)
   preOrder(root.right_child)

def inOrder(root):
   if root == None:
       return
   inOrder(root.left_child)
   print root.key,
   inOrder(root.right_child)

def postOrder(root):
   if root == None:
       return
   postOrder(root.left_child)
   postOrder(root.right_child)
   print root.key,

层次遍历：

def cengci(root):
    if root == None:
        return
    stack = []
    stack.append(root)
    while len(stack):
        p = stack[0]
        print p.key ,
        del stack[0]
        if p.left_child:
            stack.append(p.left_child)
        if p.right_child:
            stack.append(p.right_child)

测试：

if __name__ == "__main__":
    r = binaryTree('a')
    r.insert_left('b')
    r.insert_right('c')
    l = r.left_child
    l.insert_left("d")
    l.insert_right("e")
    ri = r.right_child
    ri.insert_left("f")
    ri.insert_right("g")
    print "pre: "
    preOrder(r)
    print "\n"
    print "in: "
    inOrder(r)
    print "\n"
    print "post: "
    postOrder(r)

image.png

非递归方法：

1. 先序遍历：
   当p或者栈不为空时循环，为什么是这个条件（p很可能为None,但如果此时还能回溯的时候，程序就可以继续），首先一直压入左节点，（对应根节点）并且输出当前节点，当直到最左的时候，回溯（对应pop操作），考虑右节点

def preOrder1(root):
    if root == None:
        return
    p = root
    stack = []
    while p != None or len(stack):
        while p != None:
            print p.key,
            stack.append(p)
            p = p.left_child
        if len(stack):
            p = stack[-1]
            del stack[-1]
        p = p.right_child

2. 中序遍历，和前序遍历有点像，但是因为根是在中间遍历，所以要在出栈时候输出（相当于根节点被压栈了），最后考虑右节点

def inOrder1(root):
    if root == None:
        return
    p = root
    stack = []
    while p != None or len(stack):
        while p != None:
            stack.append(p)
            p = p.left_child
        if len(stack):
            p = stack[-1]
            print p.key,
            del stack[-1]
        p = p.right_child

3. 后序遍历：
   左--》右--》根
   当左节点和右节点不存在时，可以访问根节点，或者左节点或者右节点已经访问过的时候。
   然后先压栈右节点，然后左节点，这样输出的时候先左节点，后右节点

def postOrder1(root):
    if root == None:
        return
    p = root
    stack = []
    stack.append(p)
    pre = None
    while len(stack):
        cur = stack[-1]
        if (cur.left_child == None and cur.right_child == None) or (pre!=None and (pre == cur.left_child or pre == cur.right_child)):
            print cur.key,
            del stack[-1]
            pre = cur
        else:
            if cur.right_child != None:
                stack.append(cur.right_child)
            if cur.left_child != None:
                stack.append(cur.left_child)

image.png