二叉树的遍历

2019-01-05

二叉树的遍历分为先序遍历、中序遍历、后序遍历和层次遍历。我们在实现遍历的过程时，可以使用递归和非递归来解决。

其中二叉树的结构如下：

class BinaryTree(object):
    def __init__(self, data):
        self.__key = data
        self.__leftChild = None
        self.__rightChild = None

1 先序遍历

1.1 递归

若二叉树非空，则执行以下操作：

  • 访问根结点；
  • 先序遍历左子树；
  • 先序遍历右子树。
def preorder(root, nodelist = None):
        if nodelist is None:
            nodelist = []
        if root:
            nodelist.append(root.getKey())
            if root.getLeft():
                preorder(root.getLeft(), nodelist)
            if root.getRight():
                preorder(root.getRight(), nodelist)
        return nodelist

1.2 非递归

这里主要是借用栈这个结构，在Python中可以使用List代替Stack。
在同一层中，不可能同时有两个节点压入栈，因此栈的大小空间为$O(h)$，$h$为二叉树高度。时间方面，每个节点都被压入栈一次，弹出栈一次，访问一次，复杂度为$O(n)$，$n$为节点个数。
若二叉树非空，则执行以下操作：

  • 将根节点$Node$压入栈；
  • 取出栈顶将其进行打印，同时将取得元素的左右孩子节点分别入栈；
  • 直至栈中的元素全部取光。
def preOrderByStack(self, root, nodelist = None):
    if not root:
        return []
    if nodelist is None:
        nodelist = []  # 保存结果
    stack = []  # 建立一个栈
    stack.append(root)
    # 当栈不为空时
    while stack:
        # 取出栈顶节点
        tmp = stack.pop()
        nodelist.append(tmp.getKey())
        # 因为栈是先入后出的，左节点要比右节点先访问，所以先把右节点入栈，再把左节点入栈
        if tmp.getRight():
            stack.append(tmp.getRight())
        if tmp.getLeft():
            stack.append(tmp.getLeft())
    return nodelist

# 方法二
def preOrderByStack2(self, root):
        if root == None:
            return
        myStack = []
        nodelist = []
        node = root
        while node or myStack:
            while node:
                # 从根节点开始，一直找它的左子树
                nodelist.append(node.getKey())
                myStack.append(node)
                node = node.getLeft()
            # while结束表示当前节点node为空，即前一个节点没有左子树了
            node = myStack.pop()
            # 开始查看它的右子树
            node = node.getRight()
        return nodelist

2 中序遍历

2.1 递归

若二叉树非空，则执行以下操作：

  • 中序遍历左子树；
  • 访问根结点；
  • 中序遍历右子树。
def inorder(root, nodelist = None):
        if nodelist is None:
            nodelist = []
        if root:
            if root.getLeft():
                inorder(root.getLeft(), nodelist)
            nodelist.append(root.getKey())
            if root.getRight():
                inorder(root.getRight(), nodelist)
        return nodelist

2.2 非递归

中序遍历在使用栈是不能简单的按前序的做法进行操作，因为他最先需要输出的左孩子节点。时间复杂度和空间复杂度与先序遍历一致。
若二叉树非空，则执行以下操作：

  • 首选将当前节点root的各个左子节点压入栈；
  • 然后依次从栈中取数据，进行打印，将当前节点置为栈顶的右孩子节点，回到上一步；
  • 直至栈为空。
# 根据上面的先序遍历方法二，可以类似的构造出中序遍历。
# 需要的改动仅仅调换一下节点访问的次序，先序是先访问，再入栈；
# 而中序则是先入栈，弹栈后再访问。
def inOrderByStack(self, root):
    if root is None:
        return []
    stack = []
    nodelist = []
    node = root
    while node or stack:
        while node:
            # 从根节点开始，一直找它的左子树
            stack.append(node)
            node = node.getLeft()
        # while结束表示当前节点node为空，即前一个节点没有左子树了
        node = stack.pop()
        nodelist.append(node.getKey())
        # 开始查看它的右子树
        node = node.getRight()
    return nodelist

3 后序遍历

3.1 递归

若二叉树非空，则执行以下操作：

  • 后序遍历左子树；
  • 后序遍历右子树；
  • 访问根结点。
def postorder(root, nodelist = None):
        if nodelist is None:
            nodelist = []
        if root:
            if root.getLeft():
                postorder(root.getLeft(), nodelist)
            if root.getRight():
                postorder(root.getRight(), nodelist)
            nodelist.append(root.getKey())
        return nodelist

3.2 非递归

使用两个栈，其中一个栈存每个节点的左右节点，另一个节点存储后序遍历的逆序，最后通过出栈将后序遍历输出。

def postOrderByStack(self, root):
        if not root:
            return []
        stack1 = []  # 每个节点的左右节点
        stack2 = []  # 后序遍历逆序
        nodelist = []  # 保存后序遍历的节点值
        node = root
        stack1.append(node)  # 中
        while stack1:
            # 这个while循环的功能是找出后序遍历的逆序，存在stack2里面
            node = stack1.pop()
            if node.getLeft():  # 左
                stack1.append(node.getLeft())
            if node.getRight():  # 右
                stack1.append(node.getRight())
            stack2.append(node) # 入栈顺序：中 右 左，那么出栈顺序就是后序遍历的顺序
        while stack2:
            # 将stack2中的元素出栈，即为后序遍历次序
            tmp = stack2.pop()
            nodelist.append(tmp.getKey())
        return nodelist

4 层次遍历

使用队列实现层次遍历。

def levelOrder(self, root):
        if root == None:
            return []
        queue = []  # 模拟队列
        nodelist = []  # 存储层次遍历的值
        node = root
        queue.append(node)
        while queue:
            node = queue.pop(0)
            nodelist.append(node.getKey())
            if node.getLeft():
                queue.append(node.getLeft())
            if node.getRight():
                queue.append(node.getRight())
        return nodelist

递归版：

def levelOrder(self, root):
        level, res = 1, []
        self.helper(level, res, root)
        return res
    
def helper(self, level, res, root):
    if root:
        if level > len(res):
            res.append([])
        res[level-1].append(root.val)
        self.helper(level+1, res, root.left)
        self.helper(level+1, res, root.right)

5 总结

树的遍历主要有两种，一种是深度优先遍历，像前序、中序、后序；另一种是广度优先遍历，像层次遍历。在树结构中两者的区别还不是非常明显，但从树扩展到有向图，到无向图的时候，深度优先搜索和广度优先搜索的效率和作用还是有很大不同的。 深度优先一般用递归，广度优先一般用队列。一般情况下能用递归实现的算法大部分也能用堆栈来实现。