logo标签列表

二叉树-按层级打印元素

c++binary-search-tree
6
这个问题是在我的一次面试中问到的：
假设我们有上面的二叉树，如何生成下面这样的输出结果：
2 7 5 2 6 9 5 11 4

我回答说，也许我们可以有一个层级计数变量，并通过检查每个节点的层级计数变量按顺序打印所有元素。可能我错了。

有人能给出任何关于如何实现这一点的想法吗？

二叉树的简单层序表示 - Badr
1
请查看Breadth-first_Traversal。 - Nick Dandoulakis
你的标签表明这是一个关于二叉搜索树的问题，但这不是它的一个例子。这并不重要；通常算法对于所有类型的树都适用。 - Rob Kennedy
7个回答
6
你需要对树进行广度优先遍历。 这里 描述了如下内容：
广度优先遍历：深度优先遍历并非遍历树元素的唯一方式。另一种方法是逐层遍历。例如，每个元素都存在于树的某个特定层级（或深度）中：
    tree
      ----
       j         <-- level 0
     /   \
    f      k     <-- level 1
  /   \      \
 a     h      z  <-- level 2
  \
   d             <-- level 3

人们喜欢从0开始编号。

因此，如果我们想要逐层(通常是从左到右)访问元素，我们会从第0层开始用j，然后转到第1层的f和k，再到第2层的a、h和z，最后到第3层的d。

这种逐层遍历称为广度优先遍历，因为我们在向下深入之前，会先探索给定级别的树的宽度。

你有没有任何关于广度优先遍历的资料可以分享？ - Vijay
2
您的问题中提到的遍历被称为层序遍历，这里是它的实现方法（我找到的非常简洁清晰的代码片段）。
基本上，您需要使用一个队列，操作顺序大致如下：
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

对于这棵树（直接来自维基百科）：
enter image description here
2
那个术语叫做“层序遍历”。维基百科描述了一种使用队列的算法来实现：链接。
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)
2

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);
}

迭代加深也可以起作用并节省内存使用，但以计算时间为代价。
2
如果我们能够获取同级别的下一个元素，那么我们就完成了。根据我们之前的知识，我们可以使用广度优先遍历来访问这些元素。
现在唯一的问题是如何检查我们是否到达了任何一层的最后一个元素。为此，我们应该附加一个定界符（在本例中为NULL）以标记一层的结尾。
算法： 1. 将根放入队列中。
2. 将NULL放入队列中。
3. 当队列不为空时
4. x = 从队列中获取第一个元素
5. 如果x不是NULL
6. x->rpeer <= 队列的顶部元素。
7. 将x的左右子节点放入队列中
8. 否则
9. 如果队列不为空
10. 将NULL放入队列中
11. 结束if
12. 结束while
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;
}
0

我会使用一个集合，例如std::list，来存储当前打印级别的所有元素：

  1. 在容器中收集当前级别中所有节点的指针
  2. 打印容器中列出的节点
  3. 创建一个新容器，添加容器中所有节点的子节点
  4. 用新容器覆盖旧容器
  5. 重复直到容器为空
0
作为面试中如果您不记得或不知道“官方”算法可以做的事情的一个例子，我的第一个想法是 - 按照常规的前序遍历遍历树，同时沿着一级计数器，维护每个级别指向节点的指针链表的向量，例如：
levels[level].push_back(&node);

最后打印出每个级别的列表。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接