[Python知识库]数据结构与算法之二叉树的遍历

Python实现二叉树的遍历（先序、后序和中序）

建立示例二叉树

'''
例：二叉树
                  5
                 / \
               4    6
              / \
            2    1
'''
class TreeNode:
    def __init__(self,val):
        self.val = val
        self.left = None
        self.right = None

1 先序遍历

def preOrder(root):
    '''前序遍历:
    1) 压入根节点
    2) 若栈不为空，弹出一个节点，并且加入到结果列表中
    3) 若弹出的节点有子节点，先压右节点，再压左节点
    4) 返回2)，若栈为空，结束，打印结果列表
    '''
    if root != None:
        stack = []
        res = []
        stack.append(root)
        while len(stack)>0:
            node = stack.pop()
            res.append(node.val)
            if node.right != None:
                stack.append(node.right)
            if node.left != None:
                stack.append(node.left)
        return res

2 后序遍历

def postOrder(root):
    '''后序遍历:
    1) 压入根节点
    2) 若栈不为空，弹出一个节点，并且加入到结果列表中
    3) 若弹出的节点有子节点，先压左节点，再压右节点
    4) 返回2)，若栈为空，结束
    5) 反转结果列表，打印
    '''
    if root != None:
        stack = []
        res = []
        stack.append(root)
        while len(stack)>0:
            node = stack.pop()
            res.append(node.val)
            if node.left != None:
                stack.append(node.left)
            if node.right != None:
                stack.append(node.right)
        res.reverse()
        return res

3 中序遍历

def inOrder(root):
    '''中序遍历:
    1) 整个二叉树的左边界依次入栈
    2) 1)无法继续，则从栈中弹出节点，并放入结果列表
    3) 来到弹出节点的右树上,返回1)
    ''' 
    if root != None:
        stack = []
        res = []
        while len(stack)>0 or root != None:
            if root != None:
                stack.append(root)
                root = root.left
            else:
                node = stack.pop()
                res.append(node.val)
                root = node.right
        return res

完整示例

'''
例：二叉树
                  5
                 / \
               4    6
              / \
            2    1
'''
class TreeNode:
    def __init__(self,val):
        self.val = val
        self.left = None
        self.right = None
        
def preOrder(root):
    '''前序遍历:
    1) 压入根节点
    2) 若栈不为空，弹出一个节点，并且加入到结果列表中
    3) 若弹出的节点有子节点，先压右节点，再压左节点
    4) 返回2)，若栈为空，结束，打印结果列表
    '''
    if root != None:
        stack = []
        res = []
        stack.append(root)
        while len(stack)>0:
            node = stack.pop()
            res.append(node.val)
            if node.right != None:
                stack.append(node.right)
            if node.left != None:
                stack.append(node.left)
        return res
def postOrder(root):
    '''后序遍历:
    1) 压入根节点
    2) 若栈不为空，弹出一个节点，并且加入到结果列表中
    3) 若弹出的节点有子节点，先压左节点，再压右节点
    4) 返回2)，若栈为空，结束
    5) 反转结果列表，打印
    '''
    if root != None:
        stack = []
        res = []
        stack.append(root)
        while len(stack)>0:
            node = stack.pop()
            res.append(node.val)
            if node.left != None:
                stack.append(node.left)
            if node.right != None:
                stack.append(node.right)
        res.reverse()
        return res
def inOrder(root):
    '''中序遍历:
    1) 整个二叉树的左边界依次入栈
    2) 1)无法继续，则从栈中弹出节点，并放入结果列表
    3) 来到弹出节点的右树上,返回1)
    ''' 
    if root != None:
        stack = []
        res = []
        while len(stack)>0 or root != None:
            if root != None:
                stack.append(root)
                root = root.left
            else:
                node = stack.pop()
                res.append(node.val)
                root = node.right
        return res

if __name__=='__main__':
    root = TreeNode(5)
    root.left = TreeNode(4)
    root.right = TreeNode(6)
    root.left.left = TreeNode(2)
    root.left.right = TreeNode(1)
    print("先序遍历:", preOrder(root))
    print("后序遍历", postOrder(root))
    print("中序遍历", inOrder(root))