Как построить недвоичное дерево с рекурсией или без нее?

Question

У меня есть иерархические данные, которые выглядят так:

+----------------------+-------+
| name                 | depth |
+----------------------+-------+
| ELECTRONICS          |     0 |
| TELEVISIONS          |     1 |
| TUBE                 |     2 |
| LCD                  |     2 |
| PLASMA               |     2 |
| PORTABLE ELECTRONICS |     1 |
| MP3 PLAYERS          |     2 |
| FLASH                |     3 |
| CD PLAYERS           |     2 |
| 2 WAY RADIOS         |     2 |
+----------------------+-------+

TUBE, LCD и PLASMA являются потомками TELEVISIONS.FLASH - дитя MP3-плееров.MP3-плейеры, CD-плейеры и 2 WAY RADIOS - дети ПОРТАТИВНОЙ ЭЛЕКТРОНИКИ.Вы получаете упражнение.

Теперь у меня есть структурный узел, который содержит его идентификатор и его дочерние элементы, и так далее, чтобы построить дерево.Например:

struct Node
{
   int id;
   list<Node*> children;
}

Каждый элемент идентифицируется идентификатором, который является номером строки (ELECTRONICS = 0, TELEVISIONS = 1 и т. Д.), Поэтому легко определить, кто является детьмиузла.

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

Так как я могу это сделать?Помогите!

Answer 1

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

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

нет проблем с использованием рекурсии с недвоичным деревом, вам просто нужно вместо вызова left/right (или аналогичного) в вызове рекурсивной функции каждый в list<Node*>.

Answer 2

Вы можете использовать более одного указателя ссылок.т.е.

struct node
{
int id;
node *first_child;
node *second child;
node *third_child;
}

В вашем случае максимальное значение равно 3. Вы можете указать узлы с разными дочерними элементами и получить к ним доступ.Если у вас меньше 3 детей, вы можете сделать его пустым.

Answer 3

Примерно так:

int main()
{
    Node  flash(FLASH_ID);
    Node  mp3(MP3_ID);

    mp3.children.push_back(flash);
    // repeat
}

Answer 4

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

Для меня я бы построил дерево сверху вниз, то есть создал родительский узел перед дочерними. Я бы отсортировал входные данные, чтобы потребление было линейным. Чтобы добавить новый узел, просто укажите в качестве параметра глубину и уменьшайте (при переходе вниз от корня), пока он не достигнет 0, вот где должен быть узел. Конечно, требуется информация о родительском пути для узла.