14. The TREE

The QUEUE and the STACK are linear lists. This means each data item only points to the one before it and after it.They have the idea of order built into them, such as 'last' or 'first'. But they do not imply there is any relationship between the data items themselves.

The TREE on the other hand, is designed to represent the relationship between data items.

Just like a family tree, a TREE data structure is illustrated below.

Each data item within a tree is called a 'node'.

The highest data item in the tree is called the 'root' or root node.

Below the root lie a number of other 'nodes'. The root is is the 'parent' of the nodes immediately linked to it and these are the 'children' of the parent node.

If nodes share a common parent, then they are 'sibling' nodes, just like a family.

The link joining one node to another is called the 'branch'.

The tree structure above is a general tree. But there is a very specific form of tree described on the next page