c++ - 如何表示这个 "tree"数据？

Question

我得到了一些数据(在我解决这个问题之前这些数据并不存在......)我需要能够在我的程序中进行操作。但是我无法找到合适的结构来存储它。

数据表示一组路径和节点。有一个输入(在某些情况下可能不存在)然后节点之间的许多路径以输出结尾(一端可能没有输出，但输出总是在最后)。每个输入、节点和输出都有一个位置，整体数据可以图形化操作，所以无论我使用什么结构，都需要在运行时以潜在不可预测的方式轻松更改内容(例如将输入更改为输出，以及然后将另一个输出作为输入)。

我考虑过使用树结构，其中每个项目都有一个父项(根除外)和一些子项，例如:

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

但是我可以看到一些问题，例如没有输入，或者它被删除/更改/等等......

这是一个视觉示例。 >是一个输入O节点和[]输出。
http://unisonmodules.co.uk/wjnewbery/data.png

@Everyone 建议使用我已经提到的树结构

如果一棵树实际上是合适的，我该如何克服给定数据集甚至没有输入/根的问题，如下面的例子。那么会发生什么？如果输入节点/点/任何更改(通过删除然后添加)，我是否需要完全重建树？我该怎么做？

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 };