Binary Tree Representation

Binary Tree Representation:

Binary trees can be represented in in two ways.

1.       Sequential or Array representation.

2.       Linked List representation.

Sequential representation of Binary Trees:

In sequential representation binary tree is represented with help of a single dimensional array. The size of the array can be determined as 2^(d+1)-1, where d is the depth of the tree. The root element is always placed at first position of the array (i.e., 0) and the left child is placed at twice the root position +1 and right child is placed at twice the root position +2 positions.

Position of left child I = (2*root position) +1                  

Position of right child = (2*root position) +2

E.g.: size of array = 2^(d+1)-1=2⁽²⁺¹⁾-1=7

The binary tree can be represented as 

A	B	C	D		E	F
0	1	2	3	4	5	6

Representation of binary tree using arrays is very simplest and easiest. But array representation has so many drawbacks. The insertion and deletion of nodes in the middle of a tree requires the moment of many nodes to reflect the change in level number of these nodes. And also a binary tree with a few nodes will have lot of un utilized space in the array. More over the size of arrays is fixed in nature, adding new nodes is complex since the size of the array has to increase. To overcome this disadvantages Linked list representation is used.

Linked Representation:

In order to represent a binary tree using linked list a Double linked list is used. Since every node contains three fields one to hold the data and the other two fields to hold the address of left and right child nodes.

The structure of Node is as follows 

 Where Data/ info holds the data associated with the Node

Left and right are address fields which hold the address of the left and right sub trees.

class Node

{

                int idata;

                double fdata;

                Node left;

                Node right;

}

E.g.:

The binary can be represented as