Дерево с несколькими дочерними узлами и следующим узлом

Question

Я хочу построить дерево со следующими характеристиками:

1. Каждый узел может иметь 1 «следующий узел».
2. Каждый узел может иметь несколько дочерних узлов.
3. Количество дочерних узлов может варьироваться от одного узла к другому

Я думал о структуре, которая выглядела так:

struct tree {
  int value;
  struct tree* nextnode;
  struct tree** childnode;
};

Количество детей в каждом узле должно быть параметризовано. Я не уверен, как это сделать. Заранее спасибо!

Редактировать : Позвольте мне попытаться определить это, используя пример: Давайте возьмем начальный узел. Теперь я определю во время компиляции, что будет 3 NextNodes, и каждый из этих NextNodes будет иметь 2 ChildNodes. Это на Depth=0. В Depth = 1 (то есть для каждого дочернего узла из Depth=0) я указываю, что будет 4 NextNodes, и для каждого из этих NextNodes будет 3 ChildNodes и так далее. Надеюсь, я смогу передать это правильно. Пожалуйста, спросите, если я где-то не ясно.

Edit2 : Вот картинка:

Answer 1

Вы можете использовать библиотеку Boost.Graph .

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

С сайта:

Алгоритмы

Алгоритмы BGL состоят из базового набора шаблонов алгоритмов (реализованных в виде общих алгоритмов) и большего набора графовых алгоритмов.Основные шаблоны алгоритмов:

• Поиск по ширине
• Поиск по глубине
• Поиск по равномерной стоимости

Сами по себе шаблоны алгоритмовне вычисляйте какие-либо значимые величины на графиках;они являются просто строительными блоками для построения графовых алгоритмов.Графические алгоритмы в BGL в настоящее время включают

• Кратчайшие пути Дейкстры
• Кратчайшие пути Беллмана-Форда
• Кратчайшие пути Джонсона на всех парах
• КрускалаМинимальное связующее дерево
• Минимальное остовное дерево Прима
• Связанные компоненты
• Сильно связанные компоненты
• Динамически связанные компоненты (с использованием несвязанных наборов)
• Топологическая сортировка транспонирования
• Обратное упорядочение Кутхилла Макки
• Наименьшее последнее упорядочение вершин
• Последовательное окрашивание вершин

Структуры данных

TheВ настоящее время BGL предоставляет два класса графов и адаптер списка ребер:

• adjacency_list
• adjacency_matrix
• edge_list

Класс adjacency_listявляется универсальным «швейцарским армейским ножом» графовых классов.Он сильно параметризован, так что его можно оптимизировать для различных ситуаций: график направлен или ненаправлен, разрешить или запретить параллельные ребра, эффективный доступ только к ребрам или к ребрам, быструю вставку и удаление вершин назатраты на дополнительное пространство и т. д.

Класс adjacency_matrix хранит ребра в | V |x | V |матрица (где | V | - количество вершин).Элементы этой матрицы представляют ребра в графе.Представления матрицы смежности особенно подходят для очень плотных графов, т. Е. Тех, где число ребер приближается к | V | 2.

Класс edge_list является адаптером, который принимает любой вид итераторов ребер и реализует реброГрафик списка.

Answer 2

Это N-арное дерево.Я предлагаю вам разделить дерево и узел

typedef struct tree tree;
typedef struct node node;

struct tree {
    node * root;
};

struct node {
    int value;
    node * next_node;
};

, теперь вы можете выполнить все операции с древовидной структурой

, вот пример

node * add_child(node *parent, int child_value){
    node * child = malloc(sizeof(node));
    child->value = child_value;
    if(parent->next == NULL)
        parent->next = child;
    else{
        node * temp = parent->next;
        while(temp->next != NULL)
            temp = temp->next;
        temp->next = child;
    }
    return child;
}