binarytree二叉树节点BFS广度优先搜索遍历，递归，python

川长思鸟来 2023-10-02 15:16 2阅读 0赞

从左至右，逐层展开，递归实现。

import random
    
    from binarytree import build
    
    
    def app():
        data = []
        for i in range(10):
            data.append(i)
        random.shuffle(data)
    
        root = build(data)
        root.pprint(index=False, delimiter=',')
    
        visited = [root[0]]
    
        print('-----')
        my_bfs_travel(visited)
        print('广度遍历路径', bfs_path)
    
    
    bfs_path = []
    
    
    # 广度遍历，逐层遍历,从左至右，递归实现
    def my_bfs_travel(visited):
        if len(visited) == 0:
            return
    
        node = visited[0]
    
        if node not in bfs_path:
            bfs_path.append(node)
    
        left_child = node.left
        right_child = node.right
    
        if left_child is not None:
            bfs_path.append(left_child)
            visited.append(left_child)
        if right_child is not None:
            bfs_path.append(right_child)
            visited.append(right_child)
    
        # 弹出首位元素
        visited.pop(0)
    
        my_bfs_travel(visited)
    
    
    if __name__ == '__main__':
        app()

输出：

____9__
           /       \
        __5__       0
       /     \     / \
      2       6   3   7
     / \     /
    4   1   8
    
    -----
    广度遍历路径 [Node(9), Node(5), Node(0), Node(2), Node(6), Node(3), Node(7), Node(4), Node(1), Node(8)]