如何表示这个“树”数据？

Question

我得到了一些数据（不是数据实际上存在，直到我解决了这个......）我需要能够在我的程序中操作。但是我不能找出一个合适的结构来存储它。

数据表示一组路径和节点。有一个输入（在某些情况下可能不存在），那么节点之间以输出结尾的一些路径（一端可能没有输出，但输出总是在结尾）。每个输入，节点和输出都有一个位置，整体数据可以用图形方式处理，所以无论我使用什么结构都可以很容易地以潜在的不可预知的方式改变运行时的内容（例如将输入更改为输出，以及然后使另一个输出成为输入）。

我使用树结构，其中每个项目有一个父（除了root）和一些儿童，例如象认为：

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

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

创建一个具有值和一个兄弟数组的节点类。在这种情况下，它是一个值节点，兄弟姐妹阵列可能是空的。在这种情况下，它的值可能为零。