Распечатать общие уровни дерева

Question

Извините за мой плохой английский.

Мне нужно напечатать уровни общего дерева или n-арного дерева.

Структура дерева:

struct GTnode{
    int data;
    nodeGT *fc; //first child
    nodeGT *nb; //next brother
}

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

Редактирование Если у меня есть это дерево, например:

              1
     2        7        8
  3    6            9     12
 4 5              10 11

Я должен напечатать:

1
2 7 8
3 6 9 12
4 5 10 11

Каждый конец представляет отдельный уровень в дереве

Редактирование Идея моего кода следующая:

void printLevel(GTnode *root){
   GTnode *aux = root;
   if(root != NULL){
      cout<<aux->data;
      printLevel(aux->nb);
      cout<<end; //Print the space between levels
      printLevel(aux->fc);
   }
}

Я знаю, что это неправильно, но это просто представление о том, что у меня есть.

Answer 1

Вам необходимо выполнить обход дерева в порядке порядка / ширины ( wp). Для этого вам нужна очередь. Поставь рут в очередь. Затем делайте это до тех пор, пока очередь не станет пустой: возьмите первый выход, добавьте его ->fc в очередь и перейдите к его ->nb (просматривайте все -> nb, пока не появится nomore, и каждый раз, когда вы добавляете его ->fc в очередь).