The concept of trees

Trees are used to impose a hierarchical structure on a collection of data items. For example, we need to impose a hierarchical structure on a collection of data items while preparing organizational charts and geneologies to represent the syntactic structure of a source program in compilers. So the study of trees as one of the data structures is important.
 
Definition of a Tree
A tree is a set of one or more nodes T such that:
 
(i) there is a specially designated node called a root
 
(ii) The remaining nodes are partitioned into n disjointed set of nodes T1, T2,…,Tn, each of which is a tree.
 
A tree strucutre is shown in following Figure.



This is a tree because it is a set of nodes {A,B,C,D,E,F,G,H,I}, with node A as a root node and the remaining nodes partitioned into three disjointed sets {B,G,H,I}, { C,E,F} and {D}, respectively. Each of these sets is a tree because each satisfies the aforementioned definition properly.
 
Shown in following Figure is a structure that is not a tree.



Even though this is a set of nodes {A,B,C,D,E,F,G,H,I}, with node A as a root node, this is not a tree because the fact that node E is shared makes it impossible to partition nodes B through I into disjointed sets.
 

Degree of a Node of a Tree

The degree of a node of a tree is the number of subtrees having this node as a root. In other words, the degree is the number of descendants of a node. If the degree is zero, it is called a terminal or leaf node of a tree.
 

Degree of a Tree

The degree of a tree is defined as the maximum of degree of the nodes of the tree, that is, degree of tree = max (degree(node i) for I = 1 to n)
 

Level of a Node

We define the level of the node by taking the level of the root node as 1, and incrementing it by 1 as we move from the root towards the subtrees. So the level of all the descendants of the root nodes will be 2. The level of their descendants will be 3, and so on. We then define the depth of the tree to be the maximum value of the level of the node of the tree.