В древовидной структуре отображать узлы дерева уровень за уровнем - PullRequest
Новая
       10

В древовидной структуре отображать узлы дерева уровень за уровнем

0 голосов
/ 24 ноября 2010

Вопрос: как мы можем отображать узлы дерева уровень за уровнем?Не могли бы вы дать мне решение с эффективным использованием времени и пространства.

Пример: 

    A
   / \
  B   C
 / \  / \
D   E F  G

void PrintTree(struct tree *root);

Вывод: Вы должны напечатать узлы дерева на уровнеуровень 

  A
  B C
  D E F G

Ответы [ 3 ]

3 голосов
/ 24 ноября 2010

Для экономии места и времени на SO:

http://thecodecracker.com/c-programming/bfs-and-dfs/

3 голосов
/ 24 ноября 2010

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

  • Две очереди
  • AНебольшой поворот в подходе Джека

Итак, начните с корня.
Уложите его дочерние элементы в первую очередь.
Пройдите через них, отправляя их потомков во вторую очередь по ходу.1012 * Переключиться на вторую очередь, шаг за шагом, вытолкнув своих детей в первую очередь.
Воск включен, воск отключен.

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

2 голосов
/ 24 ноября 2010

Этот вид посещения называется в ширину или Уровень порядка .Вы можете увидеть дополнительную информацию здесь .

Обычно вы

  • сначала посещаете текущий узел
  • , а затем все дочерние элементы этого узла
  • затем все дети каждого ребенка и т. Д.

Этого легко добиться с помощью структуры FIFO:

  • протолкнуть корень
  • пока очередь не пуста
  • возьмите первый элемент, зайдите на него и отправьте все его дочерние элементы в конец очереди
  • repeat
...