二叉树级别顺序遍历

Question

三种类型的树遍历是有序,预订和后置顺序.

第四种不经常使用的遍历是水平顺序遍历.在水平顺序traveresal中,深度为"d"的所有节点在深度为d + 1的任何节点之前被处理.级别顺序遍历与其他遍历的不同之处在于它不是递归地完成的; 使用队列,而不是隐含的递归堆栈.

我对上述文字片段的疑问是

1. 为什么级别订单遍历不是递归完成的？
2. 如何在级别顺序遍历中使用队列？使用伪代码澄清请求会很有帮助.

谢谢!

Answer 1

级别顺序遍历实际上是一个BFS,它本质上不是递归的.它使用Queue而不是Stack来保存应该打开的下一个顶点.其原因在于此遍历,您希望以FIFO顺序打开节点,而不是通过递归获得的LIFO顺序

正如我所提到的,级别顺序实际上是BFS,其[BFS]伪代码[取自维基百科]是:

1  procedure BFS(Graph,source):
2      create a queue Q
3      enqueue source onto Q
4      mark source
5      while Q is not empty:
6          dequeue an item from Q into v
7          for each edge e incident on v in Graph:
8              let w be the other end of e
9              if w is not marked:
10                 mark w
11                 enqueue w onto Q

(*)在树中,不需要标记顶点,因为您无法到达2个不同路径中的同一节点.

Answer 2

void levelorder(Node *n)
{    queue < Node * >q;

     q.push(n);


     while(!q.empty())
     {
             Node *node = q.front();
             cout<<node->value;
             q.pop();
             if(node->left != NULL)
             q.push(node->left);
             if (node->right != NULL)
             q.push(node->right);

     }

}