Блог

Этот вопрос был задан мне в интервью:

допустим, у нас есть вышеупомянутое двоичное дерево, как я могу создать вывод, подобный приведенному ниже

 2 7 5 2 6 9 5 11 4
  

я ответил, что, возможно, у нас может быть переменная level count и печатать все элементы последовательно, проверяя переменную level count каждого узла.
возможно, я был неправ.

кто-нибудь может дать какие-либо идеи относительно того, как мы можем этого добиться?

Вам нужно сначала выполнить обход дерева по ширине. Здесь это описано следующим образом:

Обход в ширину: сначала в глубину — не единственный способ обхода элементов дерева. Другой способ — просмотреть их по уровням.

Например, каждый элемент существует на определенном уровне (или глубине) в дереве:

     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 .

Этот поэтапный обход называется обходом в ширину, потому что мы исследуем ширину, то есть полную ширину дерева на данном уровне, прежде чем углубляться.

Обход в вашем вопросе называется a, 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(amp;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 не равно НУЛЮ
6. x->rpeer <= верхний элемент очереди.
7. поместите левый и правый дочерние элементы x в очередь
8. else
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;
}
  

Я бы использовал коллекцию, например std::list , для хранения всех элементов текущего печатного уровня:

1. Соберите указатели на все узлы текущего уровня в контейнере
2. Выведите узлы, перечисленные в контейнере
3. Создайте новый контейнер, добавьте подузлы всех узлов в контейнере
4. Замените старый контейнер новым контейнером
5. повторяйте, пока контейнер не опустеет

в качестве примера того, что вы можете сделать на собеседовании, если вы не помните / не знаете «официального» алгоритма, моей первой идеей было — обойти дерево в обычном предварительном заказе, перетаскивая счетчик уровней, поддерживая вектор связанных списков указателей на узлы для каждого уровня, например

 levels[level].push_back(amp;node);
  

и в конце выведите список каждого уровня.