Site Overlay

两分钟讲明白树的广度优先遍历的非递归实现

这是一棵树
        1
       / \
      2   3
      \   /\
       5 6  7

这是一个队列,用于遍历时使用
<<
这是一个记录用的栈,用于记录遍历过的元素
[<

       [1]
       / \
      2   3
      \   /\
       5 6  7

先将根元素 1 入队
<1<
[<

下面进入循环操作

队头的 1 出队,存放到记录栈。1 的子节点 2, 3 入队
<2 3<
[1<

队头的 2 出队,存放到记录栈,2 的子节点 null, 5 入队
<3, null, 5<
[1 2<

队头的 3 出队,存放到记录栈,3 的子节点 6, 7 入队
<null, 5, 6 7<
[1 2 3<

队头的 null 出队,存放到记录栈,null 代表空,无可出队者
<5, 6 7<
[1 2 3 null<

队头的 5 出队,存放到记录栈,5 的子节点 null, null 入队。
<6 7 null null<
[1 2 3 null 5<

队头的 6 出队,存放到记录栈,6 的子节点 null, null 入队。
<7 null null null<
[1 2 3 null 5 6<

队头的 7 出队,存放到记录栈,7 的子节点 null, null 入队。
<null null null null<
[1 2 3 null 5 6<

队头的 null 出队,存放到记录栈,没啥能入队的了。
<null null null<
[1 2 3 null 5 6 null<

队头的 null 出队,存放到记录栈,没啥能入队的了。
<null null<
[1 2 3 null 5 6 null null<

队头的 null 出队,存放到记录栈,没啥能入队的了。
<null<
[1 2 3 null 5 6 null null null<

队头的 null 出队,存放到记录栈,没啥能入队的了。
<<
[1 2 3 null 5 6 null null null null<

队列空了。遍历结果是 [1 2 3 null 5 6 null null null null<

发表评论

电子邮件地址不会被公开。 必填项已用*标注