Non Linear Data Structure - Trees - Data Structure and Algorithm

The implementations of Stacks and Queues from linear data structures.  They cannot represent data items possessing hierarchical relationship such as between the grandfather and his descendants and in turns their descendants and so on.

We need a non-linear data structure to deal with such application in real life situation. Trees and graphs are two examples of the non-linear data structure.

A tree is simply known as the non-linear data structure in which items are arranged in a sorted sequence. It is used to represent hierarchical relationship existing amongst several data items.

A tree is an abstract model of a hierarchical structure that consists of nodes with a parent-child relationship.

The tree is a sequence of nodes. There is starting node known as the root note. Every node other than the root has a parent node. Nodes may have any number of children.

Non Linear Data Structure - Trees
The above figure is known as a tree which has A as the root node and others as the sub trees or leaf nodes. 

Simply it has three levels level 0 - root node (A), level 1 - sub-tree or nodes (B, C,D), level 2 - sub node (e). 

Node: Each data item in a tree is called a node. It is the fundamental structure in a tree. It specifies the data and links (branches) to other data items. 

Root: It is the first data item (or node) in the hierarchical arrangement of data items. In the above tree A is the root item.

The degree of a node: It is the number of subtrees of a node in a given tree. For example in above tree, 
  • The degree of node A is 3
  • The degree of node B is 2
  • The degree of node C is 1
  • The degree of node D is 0
  • The degree of node E is 0
The degree of tree: It is the maximum degree of nodes in a given tree. In the above tree the degree of node A is three In the whole tree, this value is the maximum. So the degree of the above tree is 3.

Terminal node: A node with degree zero is called a terminal node or leaf. In the above tree there are two terminal nodes E and D.

Non-terminal nodes: Any node except the root node whose degree is not zero is called non-terminal node. Non-terminal nodes are the intermediate nodes in traversing the given tree from its root node to the terminal nodes. In the above tree, there are two non-terminal nodes (B,C).

Siblings: the children nodes of a given parent node are called siblings. They are also called brothers.

Level: The entire tree structure is leveled in such a way that the root node is always at level 0. Then its immediate children are at level 1 and their immediate children are at level 2 and so on up to the terminal nodes. The level starts from 0 and children are at level n+1.

Edge: It is a connecting line of two nodes. That is the line drawn from one node to another is called an edge.

Path: It is a sequence of consecutive edges from the source to the destination node.

Depth: It is the maximum level of any leaf in a given tree. This equals the length o f the longest path from root to the terminal nodes. The term height is also used to denote the depth. The depth of the above tree is 2.

Forest: It is a set of disjoint trees. In a given tree, if we remove its root, then it becomes a forest. In the above tree there is forest with three trees if we remove the root node.