二叉树-根据级别打印元素

| 在采访中我问了这个问题：可以说我们上面有二叉树，我怎么能产生像下面这样的输出

2 7 5 2 6 9 5 11 4

我回答说可能是我们可以拥有一个级别计数变量，并通过检查每个节点的级别计数变量来依次打印所有元素。可能我错了。有人可以为我们如何实现这一目标提供想法吗？

已邀请:

7 个回复

蜂佬渺

您需要对树进行广度优先遍历。这里描述如下：广度优先遍历：深度优先不是通过一棵树的元素。另一种方法是逐级地经历它们。例如，每个元素都存在于树中的某个级别（或深度）：

    tree
      ----
       j         <-- level 0
     /   \\
    f      k     <-- level 1
  /   \\      \\
 a     h      z  <-- level 2
  \\
   d             <-- level 3

人们喜欢开始编号与0。）所以，如果我们要访问元素逐级（从左到右，如通常），我们将从0级开始 j，然后转到f和k的级别1，然后进入2级以获取a，h和z，然后最终进入d的3级。这种逐级遍历是称为广度优先遍历因为我们探索广度，即给定树的全宽水平，然后再深入。

弛保矮瘦敖

您的问题中的遍历称为level-order traversal，这就是它的完成方式（我发现的非常简单/简洁的代码段）。您基本上使用队列，操作顺序如下所示：

enqueue F
dequeue F
enqueue B G
dequeue B
enqueue A D
dequeue G
enqueue I
dequeue A
dequeue D
enqueue C E
dequeue I
enqueue H
dequeue C
dequeue E
dequeue H

对于这棵树（直接来自维基百科）：

蜗仓馈

术语是水平顺序遍历。维基百科使用队列描述了一种算法：

levelorder(root) 
  q = empty queue
  q.enqueue(root)
  while not q.empty do
    node := q.dequeue()
    visit(node)
    if node.left ≠ null
      q.enqueue(node.left)
    if node.right ≠ null
      q.enqueue(node.right)

末钉蹈泰唬

BFS：

std::queue<Node const *> q;
q.push(&root);
while (!q.empty()) {
    Node const *n = q.front();
    q.pop();
    std::cout << n->data << std::endl;
    if (n->left)
        q.push(n->left);
    if (n->right)
        q.push(n->right);
}

迭代加深也可以工作并节省内存使用，但要以计算时间为代价。

哭木算

如果我们能够获取相同级别的下一个元素，那么我们就完成了。根据我们的先验知识，我们可以使用广度优先遍历访问这些元素。现在唯一的问题是如何检查我们是否处于任何级别的最后一个元素。因此，我们应该附加一个定界符（在这种情况下为NULL）以标记级别的结尾。算法： 1.将root放入队列。 2.将NULL放入队列。 3.当队列不为空时 4. x =从队列中获取第一个元素 5.如果x不为NULL 6. x-> rpeer <=队列的顶部元素。 7.将x的左右子元素放入队列 8.其他 9.如果队列不为空 10.将NULL放入队列 11.如果结束 12.结束 13.返回

#include <queue>

void print(tree* root)
{
  queue<tree*> que;
  if (!root)
      return;

  tree *tmp, *l, *r;
  que.push(root);
  que.push(NULL);

  while( !que.empty() )
  {
      tmp = que.front();
      que.pop();
      if(tmp != NULL)
      {
          cout << tmp=>val;  //print value
          l = tmp->left;
          r = tmp->right;
          if(l) que.push(l);
          if(r) que.push(r);
      }
      else
      {
          if (!que.empty())
              que.push(NULL);
      }
  }
  return;
}