How to represent this "tree" data?

Ive got some data (not that the data actually exists until after I solved this...) I need to be able to manipulate within my program. However I cant work out a suitable structure for storing this in.

The data represents a set of paths and nodes. There is one input (which may in some cases no be present) then a number of paths between nodes ending with outputs (an end may not have an output, but an output is always at the end). Each input, node and output has a position, and the data overall can be manipulated graphically, so whatever structure I use needs to be easy to change the contents of at runtime in potentially unpredictable ways (such as changing the input to an output, and then making another output the input).

I considered using a tree structure where each item had a parent (except root) and a number of children, eg like:

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

However I can see a number of problems with this such as if there is no input, or its removed / changed / etc...

This is a visual example. The > i开发者_开发知识库s an input O nodes and [] outputs.

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

@Everyone suggesting using a tree structure like I already mentioned

If a tree is in fact suitable, how do I overcome the issues where a given set of data doesn't even have an input/root, like say the one below. What happens then? Do I need to totally rebuild the tree if the input node/point/whatever changes (via a remove then add)? How do I do that?

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

I'll take a look at graphs.

---

Seems you should really need more freeform structure than a tree. Each node can have a number of nodes connected to it; each connection has a direction. Any node can have input or output attached. Enforcing no circular connections and only one input would be up to you upon tree creation and update.

The structures could be multiply linked lists and go like this:

            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
            }

Example tree:

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

could go like this: (order is obviously wrong...)

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

---

You can create a class like this:

enum NodeType
{ Node, Output };

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

The Node and Output classes are taken from your listing. The difference is that the Node class can contain a list of TreeElement instances. This list represents the element's children.

---

The Composite pattern might be quite useful here. You can implement nodes as a sort of container which holds outputs or node objects again. In the link you'll see more code snippets as implementation hint.

---

Create a Node class which has a value and an array of siblings. The array of siblings may be empty in which case it is a value node. The value may be null in which case it is a joint.