python实现二叉树层次遍历（宽度优先遍历或叫广度优先遍历）

今天药忘吃喽~ 2022-05-14 06:55 194阅读 0赞

## 1、何为层次遍历 ##

说白了，就是一层一层、由上至下、由左至右的搜索遍历二叉树中的元素。

![70][]

上面这个二叉树，那么层次遍历的输出应该是：1、2、3、4、5、6、7、8、9

## 2、解题思路 ##

利用**队列**，依次将根，左子树，右子树存入队列，按照**队列**的**先进先出**规则来实现层次遍历。

## 3、编程实现 ##

class Node():
        # 节点类
        def __init__(self, data=-1):
            self.data = data
            self.left = None
            self.right = None
    
    
    class Tree():
        # 树类
        def __init__(self):
            self.root = Node()
    
        def add(self, data):
            # 为树加入节点
            node = Node(data)
            if self.root.data == -1:  # 如果树为空，就对根节点赋值
                self.root = node
            else:
                myQueue = []
                treeNode = self.root
                myQueue.append(treeNode)
                while myQueue:  # 对已有的节点进行层次遍历
                    treeNode = myQueue.pop(0)
                    if not treeNode.left:
                        treeNode.left = node
                        return
                    elif not treeNode.right:
                        treeNode.right = node
                        return
                    else:
                        myQueue.append(treeNode.left)
                        myQueue.append(treeNode.right)
        def BFS(self,root):              #层次遍历核心代码
            if root == None:
                return
            queue = []
            queue.append(root)
    
            while queue:
                now_node = queue.pop(0)
                print(now_node.data)
                if now_node.left != None:
                    queue.append(now_node.left)
                if now_node.right != None:
                    queue.append(now_node.right)
    
        
    if __name__ == '__main__':
        # 主函数
        datas = [1,2, 3, 4, 5, 6, 7, 8, 9]
        tree = Tree()  # 新建一个树对象
        for data in datas:
            tree.add(data)  # 逐个加入树的节点
    
        print('递归实现前序遍历：')
        tree.BFS(tree.root)

## 4、输出结果 ##

![70 1][]

[70]: /images/20220514/bbbff6c0de3a44caaca38d1b1fd54d7c.png
[70 1]: /images/20220514/658da98634174e0b8b67f842ab736ec6.png