binarytree二叉树节点BFS广度优先搜索遍历,基于队列,非递归,python

x33g5p2x  于2021-11-15 转载在 Python  
字(0.6k)|赞(0)|评价(0)|浏览(244)
import random

from binarytree import build

def app():
    data = []
    for i in range(9):
        data.append(i)
    random.shuffle(data)

    root = build(data)
    root.pprint(index=True, delimiter=',')
    print('binarytree标准遍历', root.values)

    print('-----')
    nodes = my_travel(root)
    print('广度遍历', nodes)

# 广度遍历,从左至右,自顶向下
def my_travel(root):
    nodes = []
    Q = [root[0]]
    while True:
        n = Q[0]
        nodes.append(n.value)
        del (Q[0])

        if n.left != None:
            Q.append(n.left)
        if n.right != None:
            Q.append(n.right)

        if len(Q) == 0:
            break

    return nodes

if __name__ == '__main__':
    app()

运行输出:

_____0,3_____
              /             \
       _____1,7_           _2,1_
      /         \         /     \
   _3,0_        4,8     5,2     6,5
  /     \
7,4     8,6

binarytree标准遍历 [3, 7, 1, 0, 8, 2, 5, 4, 6]
-----
广度遍历 [3, 7, 1, 0, 8, 2, 5, 4, 6]

相关文章