二叉树的遍历——递归非递归实现

baike 2020-05-09

一、简介 


   二叉树的三种遍历方式我相信大家都了然于心,前序遍历、中序遍历、后序遍历。对于这三种遍历的递归实现,我们都不容易忘记。不过,对于非递归实现,我相信会有很多人会跟我一样,背了忘,再背再忘......(很多算法题都是这样,比如各种排序算法的实现)。经过认真观察思考后,发现实现起来是那么的简单,只要记住三者遍历顺序就够了。前序遍历,先访问父节点(中)、然后左子树(左)、最后右子树(右);中序遍历:左、中、右;后序遍历:左、右、中。如果还不明白这三种遍历方式的访问顺序,建议去看看动画的教程。

二、递归实现


递归实现结构很好记,上来写两递归,递归左子树,递归右子树。前序遍历,访问节点(打印节点)在两个递归前面——中、左、右;中序遍历,访问放递归中间——左中右;后序遍历,先两递归,最后才访问——左、中、右。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


def preorder_with_recursion(root):          
        if root is None:
            return
      
        print(root.val)
        preorder_with_recursion(root.left)
        preorder_with_recursion(root.right) 


def inorder_with_recursion( root):
        if root is None:
            return 

        inorder_with_recursion(root.left)
        print(root.val)
        inorder_with_recursion(root.right)


def postorder_with_recursion(self, root):
        if root is None:
            return 

        postorder_with_recursion(root.left)
        postorder_with_recursion(root.right)
        print(root.val)

三、非递归实现


  非递归不外乎就是我们自己维护一个栈结构,来控制出栈、进栈的时机。对于前序遍历(中、左、右),因为先打印父节点 , 可以理解为访问到就要打印;中序遍历(左、中、右),因为先打印最左子树,因此,我们不断地将左节点压入栈中,直到左子节点为空,出栈打印。后序遍历(左、右、中),访问左子树跟中序遍历的方式相同,唯一区别的是,因为得先打印右子树,因此得把这节点继续存入栈(并处理为已访问),让右子树先进栈出栈,最后才轮到该节点打印。

def preorder_with_loop(root):
    if root is None:
        return

    stack = []
    stack.append(root)
    while stack:
        cur = stack.pop()
        print(cur.val)
        if cur.right:
            stack.append(cur.right)
        if cur.left:
            stack.append(cur.left)


def inorder_for_loop(root):
    if root is None:
        return

    stack = []
    cur = root
    while cur or stack:
        if cur:
            stack.append(cur)
            cur = cur.left
        else:
            cur = stack.pop()
            print(cur.val)
            cur = cur.right


def postorder_with_loop(root): 
    if root is None:
        return

    stack = []
    cur = root
    while cur or stack:
        if cur:
            stack.append(cur)
            cur = cur.left
        else:
            cur = stack.pop()
            # 先判断有没有右子树,如果没有直接打印,如果有,继续入栈,等右子树先出栈打印。
            if cur.right:
                right = cur.right
                """
                第二次入栈,右子树也随后入栈,因此将右子树设置为None来控制
                下次出栈时到可以打印,而不是再次访问右子树进入死循环。
                """
                cur.right = None
                stack.append(cur)
                cur = right
            else:
                print(cur.val)
                cur = None

   
  

相关推荐