Tree

A tree is a collection of nodes which is connected by directed edges. A tree is a non-linear data structure unlike Array, Linked Lists, stack and queue which are linear data structure. A tree can be empty with no nodes or with a single node which is known as root or tree could contain one or more subtrees. The following are the general properties of tree namely,

• One node is distinguished as root node,
• Every node is connected by directed edge from exactly one other node; A direction is parent->child.

Each node in the tree has arbitrary number of children. Any nodes with no children are called as leaves or external nodes. From the above image, E, F, C and H are called as external nodes. The nodes which are not leaves are called as internal nodes. For example, B, C, D and G are called as internal nodes.

Nodes with same parent are called as siblings. For example, from the above picture, the nodes B, C and D are siblings (as they have the same parent). The depth of a node represents the number of edges from the root to the node. The depth of node G is 2. The height of a node represents the number of edges from the node to the deepest leaf. The height of D is 2. The height of a tree is nothing but the height of the root. The height of the above tree is 3.

A General Tree

A general tree is a tree where each node may have zero or more children. General trees are used in model applications such as File Systems. The binary tree is a specialized case of general tree which has no more than two children.

Implementation

The general tree has an arbitrary number of children, and that number is not known in advance, the general tree can be implemented using a first child/next sibling method. This method has two pointers namely, one to the leftmost child and one to the rightmost sibling. The following image illustrates this:

From the above figure,

• From any single node, we could directly access its first kid, through the kids pointer.
• We could access the second kid through kids->siblings, the third kid through kids->siblings->siblings, and so on.
• Each node is a fixed size; no auxiliary arrays are needed. 

//Represents a node of an n-ary node
struct Node
{
    int key;
    struct Node *kids;
    struct Node *siblings;
};