Trees in data Structure
Tree
Tree is one of the most important non-linear data structures in computer science. Tress are very flexible, versatile and powerful data structures that can be used represent the hierarchical relationship of an organization or traditional joint family.
A tree is a non-linear data structure which is a finite set of one or more nodes such that
- there is a special designated node, called the root R of the tree
- and its remaining nodes are partitioned into number of disjoint subsets (n>=0), each of which is itself a tree, such as T1, T2, …., Tn. These are called as subtrees.
Figure- (a) shows a typical tree structures.
Tree Terminology
When we talk about trees there are number of terms associated with trees, such as parent, children, height and so on, which must be known to programmer. Let us briefly study these terminology.
Node
Each data item in a tree is basically represented by a node. A tree node is a collection of data information and branches (links) to other data items. Figure-12.28 has 11 number of nodes.
Root
There is always a designated node, called root node. It is the very first node in the hierarchical arrangement of tree nodes. In figure-12.28 A is the root node.
Degree of a Node
The number of subtrees of a node is called its degree. In figure-12.28, the degree of A is 3, the degree of B is 1, the degree of C is 2, the degree of D is one and the degree of H is 3.
Degree of a Tree
The degree of a tree is maximum of degree of nodes in a given tree. The degree of a tree, shown in figure-12.28, is 3.
Leaf or Terminal Nodes
Nodes that have zero degree are called as leaf nodes or terminal nodes. In figure-12.28 , E, F, G, I, J and K are leaf nodes.
Non-terminal Nodes
Nodes that have one or more than one degree are called as non-terminal nodes. In figure-12.28, A, B, C, D, and H are non-terminal nodes.
Sibling
Children of the same parent are called as siblings. In figure-12.28 B, C and D are siblings of node A, F and G are siblings of C and I, J and K are siblings of H.
Ancestors of a Node
The ancestors of a node are all the nodes along the path from the root node to that node. The ancestors of node J is A, D and H.
Descendant of a Node
The descendant of a node are all the nodes along the path from that node to the terminal node. The descendant of node A is B and E. There can be other descendant of A, such as C and G, D, H and K, C and F, D, H and I, and D, H and J.
Level
Each node is assigned a level number in such a way that the root node is always at level 0, its immediate children are t level 1 and their immediate children are at level 2 and so on up to the leaf nodes. It means that if a node is at ith level then its children are at (i+1)th level.
Height or Depth of a Tree
It is the maximum levels of any node in a given tree.
Forest
Forest is a set of n>= 0 disjoint trees, where n represents number of nodes in the tree. In a given tree if we remove the root node we get forest. In figure-12.28 if we remove node A then we get the forest of three trees.
We will discuss a special type of tree that has at most two subtrees known as binary tree in my next article.
Like it on Facebook, Tweet it or share this article on other bookmarking websites.