Binary tree

A tree is a finite set of nodes having a distinct node
called root.

**Binary Tree** is a tree which is either empty or has at most two subtrees,
each of the subtrees also being a binary tree. It means each node in a binary
tree can have 0, 1 or 2 subtrees. A left or right subtree can be empty.

A binary tree is made of nodes, where each node contains a
"left" pointer, a "right" pointer, and a data element. The
"root" pointer points to the topmost node in the tree. The left and
right pointers point to smaller "subtrees" on either side. A null
pointer represents a binary tree with no elements -- the empty tree. The formal
recursive definition is: a binary tree is either empty (represented by a null
pointer), or is made of a single node, where the left and right pointers
(recursive definition ahead) each point to a binary tree.

**Representation of Binary
Tree**

The
structure of each node of a binary tree contains one data field and two
pointers, each for the right & left child. Each child being a node has also
the same structure.

```
```

```
Struct
node
```

{

struct node *lc **; /* **points to the left child */

int data; /* data field */

struct node *rc; **/* **points to the right child */

}

1. Array Representation of Binary Tree:

A single array can be used to represent a binary tree.

For these nodes are numbered / indexed according to a scheme
giving 0 to root. Then all the nodes are numbered from left to right level by
level from top to bottom. Empty nodes are also numbered. Then each node having
an index i is put into the array as its ith element.

In the figure shown below the nodes of binary tree are
numbered according to the given scheme.

The figure shows how a binary tree is represented as an
array. The root 3 is the 0 th element while its left child 5 is the 1 st
element of the array. Node 6 does not have any child so its children ie 7 th
& 8 th element of the array are shown as a Null value.

It is found that if n is the number or index of a node, then
its left child occurs at (2n + 1) th position & right child at (2n + 2) th
position of the array. If any node does not have any child, then null value is
stored at the corresponding index of the array.

```
```

`/* Prorgram to implement the above array representation * /`

```
```

`Struct node `

`{ `

`struct node * lc; `

`int data; `

`struct node * rc; `

`}; `

`struct node * buildtree(int); /* builds the tree*/ `

```
void inorder(struct node *); /* Traverses the tree
in inorder*/
```

```
int a[]={
3,5,9,6,8,20,10,/0,/0,9,/0,/0,/0,/0,/0,/0,/0,/0,/0,/0,/0};
```

`void main( ) `

`{ `

`struct node * root; `

`root= buildtree(0); `

`printf(“\n Inorder Traversal”); `

`inorder(root); `

`getch( ); `

`} `

`struct node * buildtree(int n); `

`{ `

`struct node * temp=NULL; `

`if( a[n] != NULL) `

`{ `

`temp = (struct node *) malloc(sizeof(struct node)); `

`temp-> lc=buildtree(2n + 1); `

`temp-> data= a[n]; `

`temp-> rc=buildtree(2n + 2); `

`} `

`return temp; `

`} `

`void inorder(struct node * root); `

`{ `

`if(root != NULL) `

`{ `

`if(root!= NULL) `

`{ `

`inorder(root-> lc); `

`printf(“%d\t”,root->data); `

`inorder(root->rc); `

`} `

`} `

`Courtesy : NPTEL `

```
```

```
```