Python二叉树的遍历：深度优先（前序、中序、后序）和广度优先（层次）

分手后的思念是犯贱 2023-07-24 05:48 1阅读 0赞

# 准备 #

**二叉树（Binary Tree）**是一种特殊的树型结构，它的特点是每个结点至多有两棵子树（即二叉树中不存在度大于2的结点），且二叉树的子树有左右之分，其次序不能任意颠倒（有序树）。在 Python 中，已有别人实现好的二叉树模块，即 binarytree，但是本文主要是学习二叉树遍历，就不介绍了。二叉树相关内容可自行学习。

深度优先遍历：沿着每一个分支路径进行深入访问。前序、中序、后序都是深度优先遍历的特例。可以用递归实现，非递归一般借助Stack栈容器。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmdqaWFuYm8xOTky_size_16_color_FFFFFF_t_70][]

广度优先遍历：又叫层次遍历，对每一层依次访问。可以借助Queue队列容器来实现。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmdqaWFuYm8xOTky_size_16_color_FFFFFF_t_70 1][]

先定义和创建一颗二叉树

class Node():
        ''' 定义节点 '''
    
        def __init__(self, value, left=None, right=None):
            ''' 构造节点 
            :param value:节点值
            :param left:左子树
            :param right:右子树
            '''
            self.value = value
            self.left = left
            self.right = right
    
    
    class BinaryTree():
        ''' 二叉树 '''
    
        def __init__(self, args: list):
            self.__root = None  # 根节点
            self.create(args)
    
        def create(self, args: list):
            ''' 根据参数构建一棵二叉树，这里我们用最简单的层级式构建，生成完全二叉树 
            :param args:参数列表，类型为list
            '''
            if not isinstance(args, list):
                # 类型判断
                # raise ValueError('Parameter type must be list')
                return
            list_len = len(args)
            if list_len <= 0:
                return
            node_list = []
            # 根据元素生成节点
            for value in args:
                node_list.append(Node(value))
            index = 0
            # 把节点串起来，成为一棵完全二叉树
            while index < list_len:
                if index*2+1 < list_len:
                    node_list[index].left = node_list[index*2+1]
                if index*2+2 < list_len:
                    node_list[index].right = node_list[index*2+2]
                index += 1
            self.__root = node_list[0]
    
        def preorder(self):
            ''' 前序遍历 '''
            pass
    
        def inorder(self):
            ''' 中序遍历 '''
            pass
    
        def postorder(self):
            ''' 后序遍历 '''
            pass
    
        def breadthFirst(self):
            ''' 广度优先-层级遍历 '''
            pass
    
    
    if __name__ == "__main__":
        print("龚建波1992")
    
        mytree = BinaryTree(list(range(1, 10)))  # 元素为 1-9
        mytree.preorder()  # 前序遍历
        mytree.inorder()  # 中序遍历
        mytree.postorder()  # 后续遍历
        mytree.breadthFirst()  # 层级遍历

# 前序遍历  #

前序遍历先访问根节点，再访问左右子树。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmdqaWFuYm8xOTky_size_16_color_FFFFFF_t_70 2][]

代码如下：

def preorder(self):
            ''' 前序遍历 '''
            def order1(rootnode: Node):
                ''' 递归的方式遍历 '''
                if rootnode == None:
                    return
                print(rootnode.value, end=' ')  # 先访问根节点
                order1(rootnode.left)  # 递归遍历左子树
                order1(rootnode.right)  # 递归遍历右子树
            print("前序遍历(递归式)：", end=' ')
            order1(self.__root)
            print()
    
            def order2(rootnode: Node):
                ''' 非递归的方式遍历 '''
                node_stack = []  # 用list来当stack栈
                cursor = rootnode
                while cursor != None or len(node_stack) != 0:
                    if cursor != None:
                        print(cursor.value, end=' ')
                        node_stack.append(cursor)
                        cursor = cursor.left
                    else:
                        cursor = node_stack.pop()
                        cursor = cursor.right
            print("前序遍历(非递归)：", end=' ')
            order2(self.__root)
            print()

# 中序遍历  #

中序遍历，访问根节点的次序在其左右子树之间。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmdqaWFuYm8xOTky_size_16_color_FFFFFF_t_70 3][]

代码如下：

def inorder(self):
            ''' 中序遍历 '''
            def order1(rootnode: Node):
                ''' 递归的方式遍历 '''
                if rootnode == None:
                    return
                order1(rootnode.left)  # 递归遍历左子树
                print(rootnode.value, end=' ')  # 左右之间访问根节点
                order1(rootnode.right)  # 递归遍历右子树
            print("中序遍历(递归式)：", end=' ')
            order1(self.__root)
            print()
    
            def order2(rootnode: Node):
                ''' 非递归的方式遍历 '''
                node_stack = []  # 用list来当stack栈
                cursor = rootnode
                while cursor != None or len(node_stack) != 0:
                    if cursor != None:
                        node_stack.append(cursor)
                        cursor = cursor.left
                    else:
                        cursor = node_stack.pop()
                        print(cursor.value, end=' ')
                        cursor = cursor.right
            print("中序遍历(非递归)：", end=' ')
            order2(self.__root)
            print()

# 后序遍历 #

后序遍历先访问左右子树，最后才访问根节点 。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmdqaWFuYm8xOTky_size_16_color_FFFFFF_t_70 4][]

代码如下：

def postorder(self):
            ''' 后序遍历 '''
            def order1(rootnode: Node):
                ''' 递归的方式遍历 '''
                if rootnode == None:
                    return
                order1(rootnode.left)  # 递归遍历左子树
                order1(rootnode.right)  # 递归遍历右子树
                print(rootnode.value, end=' ')  # 最后访问根节点
            print("后序遍历(递归式)：", end=' ')
            order1(self.__root)
            print()
    
            def order2(rootnode: Node):
                ''' 非递归的方式遍历 '''
                node_stack = []  # 用list来当stack栈
                cursor = rootnode  # cursor存当前节点
                prev = None  # prev存之前访问过的节点
                # 先把cursor移动到左子树最底层
                while cursor:
                    node_stack.append(cursor)
                    cursor = cursor.left
                while len(node_stack) != 0:
                    cursor = node_stack.pop()
                    # 没有右节点 或者已访问过该右节点，才去访问根节点
                    if cursor.right == None or cursor.right == prev:
                        print(cursor.value, end=' ')  # 最后访问根节点
                        prev = cursor
                    # 或者有为访问的右节点
                    else:
                        node_stack.append(cursor)
                        # 进入右子树
                        cursor = cursor.right
                        # 把cursor移动到该节点左子树最下边
                        while cursor:
                            node_stack.append(cursor)
                            cursor = cursor.left
            print("后序遍历(非递归)：", end=' ')
            order2(self.__root)
            print()

# 层次遍历  #

层次遍历从上到下一层一层的遍历。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmdqaWFuYm8xOTky_size_16_color_FFFFFF_t_70 5][]

用队列的话，每访问一层，都把左右子树入栈，相当于把下一层入栈。出栈时，顺序也就是一层一层的了。

def breadthFirst(self):
            ''' 广度优先-层级遍历 '''
            def order(rootnode):
                if rootnode == None:
                    return
                from queue import Queue
                node_queue = Queue()
                node_queue.put(rootnode)
                cursor = None
                while not node_queue.empty():
                    cursor = node_queue.get()
                    print(cursor.value, end=' ')
                    if cursor.left != None:
                        node_queue.put(cursor.left)
                    if cursor.right != None:
                        node_queue.put(cursor.right)
            print("层级遍历：", end=' ')
            order(self.__root)
            print()

# 参考 #

参考博客：[https://blog.csdn.net/gongjianbo1992/article/details/88378805][https_blog.csdn.net_gongjianbo1992_article_details_88378805]

参考博客：[https://www.jianshu.com/p/bf73c8d50dc2][https_www.jianshu.com_p_bf73c8d50dc2]

参考博客：[https://www.jianshu.com/p/9503238394df][https_www.jianshu.com_p_9503238394df]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmdqaWFuYm8xOTky_size_16_color_FFFFFF_t_70]: /images/20230528/9e9d36ebcffe45b3bde92c2ad6b9aebb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmdqaWFuYm8xOTky_size_16_color_FFFFFF_t_70 1]: /images/20230528/e006b5308cf242fb8a1ba791ac5d946e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmdqaWFuYm8xOTky_size_16_color_FFFFFF_t_70 2]: /images/20230528/845be3950e124192b18f99787c99cd20.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmdqaWFuYm8xOTky_size_16_color_FFFFFF_t_70 3]: /images/20230528/83c38b5641084743be8bfbf13f461468.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmdqaWFuYm8xOTky_size_16_color_FFFFFF_t_70 4]: /images/20230528/5a6ec4ad21c84f7f9c944da8ced477fb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmdqaWFuYm8xOTky_size_16_color_FFFFFF_t_70 5]: /images/20230528/523832fd795b4a50b7edca4e7f86eaa4.png
[https_blog.csdn.net_gongjianbo1992_article_details_88378805]: https://blog.csdn.net/gongjianbo1992/article/details/88378805
[https_www.jianshu.com_p_bf73c8d50dc2]: https://www.jianshu.com/p/bf73c8d50dc2
[https_www.jianshu.com_p_9503238394df]: https://www.jianshu.com/p/9503238394df