TREE in Data Structure with C

TREE

It is a non-linear data structure that may contain several contents. In a tree the nodes are connected to each other a parent and child relationship where each parent node may have multiple children nodes but has exactly a single parent node. The node which has no parent at all is called a root node. All the other nodes in the tree are descendent of root node.

Root node:- The only node which has no parent at all is called root node. But itself it is a parent of all other nodes in the tree.

Leaf node – The node which has no child node at all are called leaf node/terminal node or external node.

Non-leaf node – The node which has at least one child node are called non-leaf nod / non-terminal or internal node.

Height of tree – The maximum distance of a leaf node form the root node is called height of the tree.

Level of a node – The distance of a particular node from the root node is called its level. The root node is itself considered a level zero; its children are at level one and so on.

NB – Maximum number of children in a binary tree can be only three.

Order / Degree of a tree – The maximum number of children at a node in tree have, is called order of tree of degree of a tree. In general a tree n has maximum children per node and (n-1) keys per node.

Binary Tree –
A tree in which each node can have maximum of two children is called a binary tree. In other words a tree of order two is called binary tree. In which each node can have only two children and single info field. The two children of a node are referred to as left and right son respectively.

Strictly Binary Tree –
A binary tree in which each node has exactly two children or no children at all is called strictly binary tree.

Complete or full Binary tree –
A strictly binary tree is which all the leaf node at the same level is called complete or full binary tree.

Binary Tree traverse –
Traversing a binary tree means to visit each and every node in the tree only once in a predetermine sequence. There are following technique to traverse a binary tree –
1. Pre-order traverse
2. In-order traverse
3. Post-order traverse
4. Level by level traverse

1. Pre-order traverse – In this technique of traverse to a binary tree, the root node is visited before visiting its left and right children. The sequence of traverse may be define recursive in following three steps –
a. Visit the root
b. Traverse the left sub-tree in pre-order
c. Traverse the right sub-tree in pre-order

2. In-order traverse – In this sequence of traversing a binary tree, the root node is visited after visiting the left children but before right child. The step for recursive definition is given as below –
a. Traverse the left sub-tree in in-order
b. Visit the root
c. Traverse the right sub-tree in in-order.

3. Post-order traverse – In this sequence of traversing, the root node visited after traversing both its left and right sub-tree. The steps are given below –
a. Traverse the left sub-tree in post-order
b. Traverse the right sub-tree in post-order
c. Visit the root node.

4. Level by level traverse – In this scheme of traversing a binary tree, the root node is visited first then the nodes at level one and then the nodes at level two and so on.

Posted in: CS 62