бинарное дерево - печать элементов в соответствии с уровнем

Question

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

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

2 7 5 2 6 9 5 11 4

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

Кто-нибудь может рассказать кому-нибудь о том, как мы можем этого достичь?

Answer 1

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

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

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

    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.

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

Answer 2

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

Теперь единственная проблема состоит в том, как проверить, находимся ли мы, наконец, на каком-либо уровне.По этой причине мы должны добавить разделитель (в данном случае NULL), чтобы отметить конец уровня.

Алгоритм: 1. Поместить root в очередь.
2. Поместить NULL в очередь.
3. Пока очередь не пуста
4. x = извлечь первый элемент из очереди
5. Если x не равен NULL
6. x-> rpeer <= верхний элемент очереди. <br>7. поместите левого и правого дочернего элемента x в очередь
8. else
9. если очередь не пуста
10. поместите NULL в очередь
11. end, если
12. end end
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;
}

Answer 3

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

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

Answer 4

Термин для этого равен обход уровня порядка .Википедия описывает алгоритм для этого с использованием очереди :

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)

Answer 5

Обход в вашем вопросе называется 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

Для этого дерева (прямо из Википедии):

Answer 6

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

levels[level].push_back(&node);

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

Answer 7

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

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