What kind of object tree is this?

Question

I need to create a tree, constructed of nodes that may have any number (within reason, between 0 and 10 say) of outgoing transitions, like so:

               X 
             / | \
            X  X  X
           /
          X
         / \
        X   X

What sort of tree structure is this? What techniques are there for constructing and specifically modifying trees of this kind?

Thanks

Answer 1

It's a tree, pure and simple. It's just not a binary tree (which has a maximum of 2 children per node). Most any tree structure should be able to handle it.

Answer 2

This is just a generic tree. Maybe because binary trees are so common, this tree looks different, but in fact, it is the binary tree that is a special case of a tree.

You don't need any special techniques to handle a tree. If you're used to binary trees, you probably use a left and right pointer to hold the children. In this case, as you say, if you want between 0 and 10 children, you would replace left/right with an array of 10 pointers.

Answer 3

Sounds like a form of the 2-3 tree, but it hasn't to be 2 data entrys with 3 links to other nodes, you can expand it as you like.

Answer 4

From the information provided alone, this tree does not fall into any special category. I imagine that you're thinking along the lines of binary trees, but once you get nodes with a number of children other than 2 or 0, there's no special classification.

Depending on how exactly it's implemented and used, it may or may not be an ordered tree: ordered tree nodes store their children with an explicit intentional order rather than in an arbitrary order.

If it is an ordered tree (or at least is implemented as one), any given node can be expressed as a series of numbers indicating a sequence of node-to-child movements, starting at the base node. For example,

0, 0, 1

would represent the right child of the sole child of the left-most child of the base node. Storing references to nodes in this way can simplify a lot of things, and it's pretty easy to write a simple function to iterate through such a series and return the resulting node.

Answer 5

What you have is just a plain tree. Special cases are binary trees or balanced tree. It is neither.

There are libraries in most languages for manipulating these. Recursion is a popular technique. All College level textbooks on Data Structures will go in depth on how to CRUD the tree.

You can get an overview here.