Как представить данные «дерева»?

Question

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

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

Я считал, используя древовидную структуру, где каждый элемент имел родитель (за исключением корня) и число детей, например, как:

Input 
| 
node--- 
| | | 
| | Output 
| | 
| Node---Output 
| |---Output 
| 
Node----Node 
|  | 
Node  Output  

Однако я вижу ряд проблем с этим, такими, как если бы нет ввода, или его удалены/изменены/etc ...

Это наглядный пример. «>» - это входные O-узлы и [] выходы.
http://unisonmodules.co.uk/wjnewbery/data.png

@Everyone предполагая, используя древовидную структуру, как я уже упоминал

Если дерево, на самом деле подходит, как я преодолеть проблемы, где данный набор данных не имеет даже вход/root, как говорят ниже. Что происходит тогда? Нужно ли мне полностью перестроить дерево, если входной узел/точка/все изменения (через удаление затем добавить)? Как мне это сделать?

http://unisonmodules.co.uk/wjnewbery/data2.png

Я буду смотреть на графики.

Answer 1

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

Структуры могут быть многократно связные списки и идти, как это:

  struct Node { 
       NodeContentType type; //Input, Output, None. 
       InOutNode* content; //pointer to input or output 
       Link* links;   //pointer to first connection (if any), NULL if none. 
      } 

      struct Link { 
       Node* node; //node this connection links to. 
       Link* next; //pointer to next connection 
      } 

Пример дерева:

INPUT 
| 
root 
| 
branch1---leaf2---output2 
| 
leaf1 
| 
output1 

может идти, как это: (приказ, очевидно, неправильно ...)

  Node root = { Input, &input_function, &link1 }; 
      Link link1 = { &branch1, NULL }; 
      Node branch1 = { None, NULL, &link2 }; 
      Link link2 = { &leaf1, &link3 }; 
      Link link3 = { &leaf2, NULL }; 
      Node leaf1 = { Output, &output_function1, NULL }; 
      Node leaf2 = { Output, &output_function2, NULL }; 

Answer 2

Вы можете создать класс, как это:

enum NodeType 
{ Node, Output }; 

class TreeElement 
{ 
    NodeType myType; 
    union 
    { 
    Node myNode; 
    Output myOutput; 
    } NodeVariant; 
}; 

В Node и Output классы взяты из вашего списка. Разница в том, что класс Node может содержать список TreeElement экземпляров. Этот список представляет дочерние элементы.

Answer 3

Composite pattern может быть весьма полезен здесь. Вы можете реализовать узлы как своего рода контейнер, который снова содержит выходные или узловые объекты. В ссылке вы увидите больше фрагментов кода в качестве подсказки реализации.

Answer 4

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