8 Trees – Introduction to Data Structures in C

Chapter 8

Trees

Chapter Outline

8.1 INTRODUCTION

In the previous chapters, we have studied various data structures such as arrays, stacks, queues and linked list. All these are linear data structures. In these data structures the elements are arranged in a linear manner, i.e. one after another. Tree is an equally useful data structure of non-linear type. In tree, elements are arranged in non-linear fashion. A tree structure means data is organized in branches. The following Fig. 8.1 is a sample tree.

A tree is a non-linear data structure and its elements are arranged in sorted order.

Tree has several practical applications. It is immensely useful in manipulating data and to protect hierarchical relationship among data. The fundamental operations such as insertion, deletion etc. is easy and efficient in tree data structure than in linear data structures. Fig. 8.2 represents family hierarchy, which keeps relations among them. The hierarchy gives relations between associates of family members. In this tree, node ‘A’ can be assumed as a parent of ‘B’ and ‘C’, ‘D’ and ‘E’ are the children of ‘B’. ‘F’ is the child of ‘C’. This tree represents the relation between the family members.

Figure 8.1 Sample tree

Figure 8.2 A family hierarchy in tree structure

For example, suppose the left side member is male and right side member is female. Then, various relations such as sister, brother, grandfather, grandmother can also be implied.

The algebraic expression can be represented with a tree. Consider the following example of an algebraic expression.

Z=(J-K) / ((L*M)+N)

The operators of the above equation have different priority. The priority of the operators can be represented by the tree structure. The operators of high priority are at low level and operator and associated operands are represented in tree structure. The Fig. 8.3 illustrates the representation of an algebraic expression.

8.2 BASIC TERMS

Some of the basic concepts relevant to trees are described in this section. These are node, parents, roots, child, link, leaf, level, height, degree of node, sibling, terminal nodes, path length, and forest.

Figure 8.3 An algebraic expression in tree form

Root It is the mother node of a tree structure. This is the most important node of any tree. This node does not have parent. It is the first node in the hierarchical arrangement.

Node It is the main component of the tree. The node of a tree stores the data and its role is same as the linked list. Nodes are connected by means of links with other nodes. This is shown in Fig. 8.4.

Figure 8.4 Right and left nodes of a tree

Parent It is an immediate predecessor of a node. In the Fig. 8.5 A is parent of B and C.

Figure 8.5 Parent nodes with child nodes

Child When a predecessor of a node is parent then all successor nodes are called child nodes. In Fig. 8.5, B and C are child nodes of A. The node at left side is called left child node and node at right side is called right child node.

Link The link is nothing but pointer to node in a tree structure. In other words, link connects the two nodes. The line drawn from one node to other node is called a link. Fig. 8.5 shows left and right child. Here, two links are shown from node A. More than two links from a node may be drawn in a tree. In a few textbooks the term edge is used instead of link. Functions of both of them are same.

Leaf This node is located at the end of the tree. It does not have any child hence it is called as leaf node. Here, ‘H’, ‘I’, ‘F’, and ‘J’ are leaf nodes in Fig. 8.6.

Level Level is a rank of tree hierarchy. The whole tree structure is levelled. The level of root node is always at 0. The immediate children of root are at level 1 and their immediate children are at level 2 and so on. If children nodes are at level n+1 then parent node would be at level n. The Fig. 8.6 shows the levels of tree.

Figure 8.6 Levels of tree

Height The highest number of nodes that is possible in a way starting from the first node (root) to a leaf node is called the height of tree. In Fig. 8.6, the height of tree is 4. This value can be obtained by referring three different paths from the source node to leaf node. The paths A-B-D-H, A-B-E-I, and A-C-G-J have the same height. The height can be obtained from the number of levels, which exists in the tree. The formula for finding the height of the tree h = imax +1, where h is the height and imax is maximum level of the tree. In the above Fig. 8.6 the maximum level of the tree is 3(imax=3). By substituting the value into the formula the h will be 4. The term depth can be used in place of height.

Degree of a Node The maximum number of children that can exist for a node, is called as the degree of the node. In Fig. 8.6 the node A, B and C have maximum two Children. So, the degree of A, B and C is same and it is equal to 2.

Sibling The child nodes of same parent are called sibling. They are also called brother nodes. A, B and C nodes in the Fig. 8.6 have two child nodes. B and C are the siblings of the node A, whereas D and E are the siblings of the node B.

Terminal Node A node with degree zero is called terminal node or leaf. Fig. 8.6 shows 4 terminal nodes and they are H, I, F and J.

Path Length It is the number of successive edges from source node to destination node. In the above Fig. 8.6 the path length from the root node A to H is three because there are three edges.

Forest It is a group of disjoint trees. If we remove a root node from a tree then it becomes the forest. If we remove root node A then the two disjoint sub-trees will be observed. They are left sub-tree B and right sub-tree C.

Labelled Trees In the labelled tree the nodes are labelled with alphabetic or numerical values. The labels are the values allotted to the nodes in the tree. Fig. 8.7 shows the diagram of a labelled tree. Finally obtained tree is called as labelled tree.

Figure 8.7 Labelled tree

The Fig. 8.7 shows the labelled tree having 11 nodes; root node is 4 and leaf nodes 11,10,17, and 2. The parent and children relationship between them is shown in Table 8.1.

 

Table 8.1 Parent and children relationship

Parent nodes Children nodes
4
3,7
3
1,5
1
11
5
10
7
2,9
9
14
14
17

There is one more relationship, which is called left node left child and right node right child. This is useful for traversing the binary tree.

 

Table 8.2 Relationship between parent, left and right nodes

Parent node Left child Right child
4
3
7
3
1
5
1
11
5
10
7
2
9
9
14
14
17

Table 8.2 describes the relationship between the parents, left and right nodes, which is drawn from the Fig. 8.7. The ‘—’ indicate that root node (parent) does not have child node. The 11,10 and 17 labelled nodes are the leaf nodes of the tree.

A program is provided based on the above relationships. It finds the number of nodes in a tree and leaf nodes.

Example 8.1

Write a program to find number of nodes and leaf nodes in the given tree.

Solution

#include<stdio.h>

#include<conio.h>

struct tree

{

long data;

struct tree *left;

struct tree *right;

};

int node=1,lev;

struct tree *bt=NULL;

struct tree *insert(struct tree*bt,long no);

void lev_count(struct tree*bt);

void node_count(struct tree*bt);

main()

{

long no;

clrscr();

puts("Enter the nodes of tree in preorder: and 0 to quit");

scanf("%ld",&no);

while(no!=0)

{

bt= insert(bt,no);

scanf("%d",&no);

}

node_count(bt);

printf("The tree contains %d nodes\n",node);

lev_count(bt);

printf("\nThe tree contains %d leaf nodes\n", lev);

}

struct tree*insert(struct tree*bt,long no)

{

if(bt==NULL)

{

bt=(struct tree*) malloc(sizeof(struct tree));

bt->left=bt->right=NULL;

bt->data=no;

}

else

{

if(no<bt->data)

bt->left=insert(bt->left,no);

else

if(no>bt->data)

bt->right=insert(bt->right,no);

else

if(no==bt->data)

{

puts("Duplicates nodes: Program exited");

exit(0);

}

}

return(bt);

}

void node_count(struct tree*bt)

{

if(bt!=NULL)

{

if(bt->left!=NULL)

{

node++;

node_count(bt->left);

}

if(bt->right!=NULL)

{

node++;

node_count(bt->right);

}

}

}

void lev_count(struct tree*bt)

{

if(bt!=NULL)

{

if((bt->left==NULL)&&(bt->right==NULL))

lev++;

else

lev_count(bt->left);

lev_count(bt->right);

}

}

OUTPUT

Enter the nodes of tree in preorder: and 0 to quit

5 3 11 0

The tree contains 3 nodes

The tree contains 2 leaf nodes

Explanation This program contains three functions insert(), lev_count(), and node_count(). The insert() is used to insert the element into the binary tree. The lev_count() function is used to count the total leaf nodes of the binary tree. The global variable lev stores the total number of the leaf nodes. The function node_count() is initialized to count number of the nodes which are present in the binary tree. The global variable node is used to store the total number of nodes present in the tree.

8.3 BINARY TREES

A binary tree is a finite set of data elements. A tree is binary if each node of it has a maximum of two branches. The data element is either empty or holds a single element called root along with two disjoint trees called left sub-tree and right sub-tree, i.e. in a binary tree the maximum degree of any node is two. The binary tree may be empty. However, the tree cannot be empty. The node of tree can have any number of children whereas the node of binary tree can have maximum two children. Fig. 8.8 shows a sample binary tree.

Figure 8.8 A sample binary tree

In Fig. 8.8, A is the root and B and G are its child nodes. The nodes B and G are non-empty nodes, hence they are called left successor and right successor of the root A. The node root without successor is called the terminal node of that root. In Fig. 8.8 the node E, F, J, and K are the terminal nodes.

The right tree is G and left tree is B. Next B has left tree C and right tree D. The right tree further has left tree H and right tree I. This will be continued up to last level.

8.4 COMPLETE BINARY TREE

A tree is called complete binary tree if each of its nodes has two children, except the last nodes. In other words, every non-terminal node of it must have both children except the last leaf nodes. So, at any level the maximum number of nodes is equal to 2. At level 0, there must be only one node and that is the root node. A at level 1 the maximum nodes must be 2. At level 3 the maximum nodes must be equal to 8. A complete binary tree can be obtained from Fig. 8.8.

The advantage of this complete binary tree is that one can very easily locate the position of the parent and also left and right child nodes of a complete binary tree.Left child node and right child nodes are located at 2N and 2N+1. Similarly, the parent node of any node would be at floor (N/2).

Parent of D would be floor (5/2)=2, i.e. B is the parent and its left and right child are 2*2=4 and 2*2+1=5. 4 and 5 are the C and D child nodes in Fig. 8.8.

8.5 STRICTLY BINARY TREE

When every non-leaf node in binary tree is filled with left and right sub-trees, the tree is called strictly binary tree. It is shown in Fig. 8.9.

Figure 8.9 Strictly binary trees

In the strictly binary tree as shown in Fig. 8.9, L and I are non-terminal nodes with non-empty left and right sub trees.

8.6 EXTENDED BINARY TREE

When every node of a tree has either 0 or 2 children then such a tree is called extended binary tree or 2-tree. The nodes with two children are called internal nodes. The nodes without children are known as external nodes. At some places in order to identify internal nodes in figures 8.10 to 8.13 circles are used. To identify external nodes squares are used. The nodes in binary tree that have only one child can be extended with one more child. This extended binary tree can be used for implementing the algebraic equation because in the algebraic equation the left and right child nodes are operands and the parent of the child represents the operator.

Figure 8.10 Binary tree

Figure 8.11 Extended 2-tree

Figure 8.12 Binary trees

Figure 8.13 2-trees

8.7 BINARY TREE REPRESENTATION

Binary tree can be represented by two ways:

  1. Array representation
  2. Linked representation.

8.7.1 Array Representation of Binary Tree

In any type of data structure array representation plays an important role. The nodes of trees can be stored in an array. The nodes can be accessed in sequence one after another. In array, element counting starts from zero to (n−1) where n is the maximum number of nodes. In other words, the numbering of binary tree nodes will start from 0 rather than 1.

Assume an integer array. Its declaration is as follows:

int array tree[n];

The root node of the tree always starts at index zero. Then, successive memory locations are used for storing left and right child nodes. Consider the following Fig. 8.14,

Figure 8.14 Array representation of tree

TREE[0]

X

TREE[1]

Y

TREE[2]

Z

 

In the above figure, X is the root and Y and Z are children. X is father of child Y and Z. Consider the following Fig. 8.15 with one more level.

Figure 8.15 Array representation of a tree

The array representation with one more level would be as follows:

0
X
1
Y
2
Z
3
S
4
T
5
U
6
V

It is very easy in this representation to identify the father, left and right child of an arbitrary node. For any node n, 0 ≤ n ≤ (MAXSIZE −1), the following can be used to identify the father and child nodes.

Father (n) The location of the father node can be identified in a given tree by using the ((n−1)/2) where n is the index of child node, provided that n! =0 (not equal to zero). In case if n=0, the said node is root node. It has no father node. Consider the node 3 in Fig. 8.15 i.e. S. The father of node S is Y and the index of Y is 1. By substituting these values in the equation we identify the index of the father node.

Floor ( (3−1)/2) ) i.e. (2/2)=1

Lchild(n) The left child of a node (n) is at position (2n+1).

  1. Lchild(X) =lchild(0)

    =2 * 0+1

    =1

    The node with index 1 is Y.

  2. lchild (Z) = lchild(2)

    = 2*2+1 = 5

    The node with index 5 is U.

rchild (n) The right child of node n can be recognized by (2n+2)

  1. rchild (X)=rchild (0)

    = 2 * 0+2

    = 2

    The node with index 2 is Z.

  2. rchild (Y): rchild(1)

    = 2 *1+2=4

    The node with index 4 is T.

Siblings In case the left child at index n is known then its right sibling is at (n+1). Likewise, if the right child at index n is known then is left sibling is at (n−1). The array representation is perfect for complete binary tree. However, this is not appropriate for other tree types and if we use array for their representation, it results in inefficient use of memory. Consider the binai trees shown in Figs 8.16(a) and 8.16(b).

Figure 8.16(a) Left skewed binary tree

The above is skewed binary tree. Here, every left sub-tree again represents left sub-tree. Such type of binary tree is called left skewed binary tree. Similarly, right skewed binary tree is also present [See Figs 8.16(a) and 8.16(b)]. Fig. 8.17 shows array representation of left and right skewed trees.

Figure 8.16(b) Right skewed binary tree

Figure 8.17 Left-right skewed binary tree

8.7.2 Linked Representation of Binary Tree

Another way of representation of binary tree is linked list, which is known to be more memory efficient than array representation. The fundamental component of binary tree is node. We know that the node consists of three fields, which is shown in Fig. 8.18.

  • Data
  • Left child
  • Right child.

Figure 8.18 Link list representation of binary tree

We have already learnt about nodes in Chapter 6. The data field stores the given values. The lchild field is link field and holds the address of its left node. Similarly, the rchild holds the address of right node. The node can be logically represented as follows. Figs 8.19 and 8.20 show the linked list representation of binary tree.

struct node

{

int data;

struct node *rchild;

struct node *lchild;

};

Figure 8.19 Binary tree

Figure 8.20 Linked list representation of binary tree

Binary tree has one root node and few non-terminal and terminal nodes. The terminal nodes are called leafs. The non-terminal nodes have their left and right child nodes. However, the terminal nodes are without child. While implementing this, fields of lchild and rchid are kept NULL. The non-terminal nodes are known as internal nodes and terminal nodes are known as external nodes.

8.8 OPERATION ON BINARY TREE

Following fundamental operations are performed on binary tree:

Create This operation creates an empty binary tree.

Make This operation creates a new binary tree. The data field of this node holds some value.

Empty When binary tree is empty, this function will return true else it will return false.

Lchild A pointer is returned to left child of the node. When the node is without left child, a NULL pointer is returned.

Rchild A pointer is returned to right child and if the node is without right child a NULL pointer is returned.

Father A pointer to father of the node is returned or else the NULL pointer is returned.

Sibling (Brother) A pointer to brother of the node is returned or else NULL pointer is returned.

Data Value stored is returned.

In addition to above mentioned operations, following operations can also be performed on binary tree:

  1. Tree traversal
  2. Insertion of nodes
  3. Deletion of node
  4. Searching for a given node
  5. Copying the binary tree.
8.9 TRAVERSAL OF A BINARY TREE

Three parameters are needed for formation of binary tree. They are node, left and right sub-trees. Traversing is one of the most important operations done on binary tree and frequently this operation is carried on data structures. Traversal means passing through every node of the tree one by one. Every node is traversed only once. Assume, root is indicated by O, left sub-tree as L and right sub-tree as R. Then, the following traversal combinations are possible:

  1. ORL - ROOT - RIGHT - LEFT
  2. OLR - ROOT - LEFT -RIGHT
  3. LOR - LEFT - ROOT - RIGHT
  4. LRO - LEFT - RIGHT - ROOT
  5. ROL - RIGHT - ROOT - LEFT
  6. RLO - RIGHT - LEFT - ROOT

Out of six methods only three are standard and are discussed in this chapter. In traversing always right sub-tree is traversed after left sub-tree. Hence, the OLR is preorder, LOR is inorder and LRO is postorder.

Figure 8.21 A model tree

The inorder representation of above tree is P-N-Q-M-R-O-S-V.

Traversing is a common operation on binary tree. The binary tree can be used to represent an arithmetic expression. Here, divide and conquer technique is used to convert an expression into a binary tree. The procedure to implement it is as follows.

The expression for which the following tree has been drawn is (X*Y)+Z. Fig. 8.22 represents the expression.

Figure 8.22 An arithmetic expression in binary tree form

Using the following three methods, the traversing operation can be performed. They are:

  1. Preorder traversal
  2. Inorder traversal
  3. Postorder traversal.

All the above three types of traversing methods are explained below.

8.9.1 Inorder Traversal

The functioning of inorder traversal of a non-empty binary tree is as follows:

  1. Firstly, traverse the left sub-tree in inorder.
  2. Next, visit the root node.
  3. At last, traverse the right sub-tree in inorder.

In the inorder traversal firstly the left sub-tree is traversed recursively in inorder. Then the root node is traversed. After visiting the root node, the right sub-tree is traversed recursively in inorder. Fig. 8.21 illustrates the binary tree with inorder traversal. The inorder traversing for the tree is P-N-Q-M-R-O-S-V. It can be illustrated as per Fig. 8.23.

Figure 8.23 Inorder traversal

The left part constitutes P, N, and Q as the left sub-tree of root and R, O, S, and V are the right sub-tree.

Example 8.2

Write a program for inserting the elements into the tree and traverse the tree by the inorder.

Solution

#include<stdio.h>

#include<conio.h>

struct tree

{

long data;

struct tree *left;

struct tree *right;

};

struct tree *btree=NULL;

struct tree *insert(struct tree*btree,long digit);

void inorder(struct tree*btree);

main()

{

long digit;

clrscr();

puts("Enter integers: and 0 to quit");

scanf("%ld",&digit);

while(digit!=0)

{

btree= insert(btree,digit);

scanf("%d",&digit);

}

puts("Inorder traversing of btree:\n");

inorder(btree);

}

struct tree*insert(struct tree*btree,long digit)

{

if(btree==NULL)

{

btree=(struct tree*) malloc(sizeof(struct tree));

btree->left=btree->right=NULL;

btree->data=digit;

}

else

{

if(digit<btree->data)

btree->left=insert(btree->left,digit);

else

if(digit>btree->data)

btree->right=insert(btree->right,digit);

else

if(digit==btree->data)

{

puts("Duplicates nodes: Program exited");

exit(0);

}

}

return(btree);

}

void inorder(struct tree*btree)

{

if(btree!=NULL)

{

inorder(btree->left);

printf("%4ld",btree->data);

inorder(btree->right);

}

}

OUTPUT

Enter integers: and 0 to quit

6 1 2 3 7 8 9 0

Inorder traversing of btree:

1 2 3 6 7 8 9

Explanation This program is used to evaluate the inorder of the given tree. The given binary tree is stored in *btree. The elements are inserted by using the insert(). The inorder traversing, i.e. left, root and right is done by inorder(). The Fig. 8.24 illustrates the binary tree.

The inorder of binary tree is 1, 2, 3, 6, 7, 8, and 9 as shown in Fig. 8.24.

Figure 8.24 Binary tree for inorder

8.9.2 Preorder Traversal

The node is visited before the sub-trees. The following is the procedure for preorder traversal of non-empty binary tree.

  1. Firstly, visit the root node (N).
  2. Then, traverse the left sub-tree in preorder (L).
  3. At last, traverse the right sub-tree in preorder R.

The preorder is recursive in operation. In this type, first root node is visited and later its left and right sub-trees. Consider the following Fig. 8.25 for preorder traversing.

Figure 8.25 Tree for preorder traversal

The preorder traversing for Fig. 8.25 is M, N, P, Q, O, R, S, and V. This can also be shown in Fig. 8.26. In this traversing the root comes first and the left sub-tree and right sub-tree at last.

Figure 8.26 Preorder traversal

In the preorder the left sub-tree appears as N, P, and Q and right sub-tree appears as O,R,S, and V.

Example 8.3

Write a program for inserting the elements in the tree and display them in preorder.

Solution

#include<stdio.h>

#include<conio.h>

struct tree

{

long data;

struct tree *left;

struct tree *right;

};

struct tree *btree=NULL;

struct tree *insert(struct tree*btree,long digit);

void preorder(struct tree*btree);

main()

{

long digit;

clrscr();

puts("Enter integers: and 0 to quit");

scanf("%ld",&digit);

while(digit!=0)

{

btree= insert(btree,digit);

scanf("%d",&digit);

}

puts("Preorder traversing btree:\n");

preorder(btree);

}

struct tree*insert(struct tree*btree,long digit)

{

if(btree==NULL)

{

btree=(struct tree*) malloc(sizeof(struct tree));

btree->left=btree->right=NULL;

btree->data=digit;

}

else

{

if(digit<btree->data)

btree->left=insert(btree->left,digit);

else

if(digit>btree->data)

btree->right=insert(btree->right,digit);

else

if(digit==btree->data)

{

puts("Duplicates nodes: Program exited");

exit(0);

}

}

return(btree);

}

void preorder(struct tree*btree)

{

if(btree!=NULL)

{

printf("%4ld",btree->data);

preorder(btree->left);

preorder(btree->right);

}

}

OUTPUT

Enter integers: and 0 to quit

5 2 1 7 0

Preorder traversing btree:

5 2 1 7

Explanation The program stores the binary tree in *btree structure variable of the structure tree. By invoking the insert() the elements are inserted. The preorder traversing is done by using preorder(). Fig. 8.27 shows the *btree, which is inserted in this program.

The preorder of the binary tree is 5, 2, 1, 7.

Figure 8.27 Binary tree

8.9.3 Postorder Traversal

In the postorder traversal the traversing is done firstly left and right sub-trees before visiting the root. The postorder traversal of non-empty binary tree is to be implemented as follows:

  1. Firstly, traverse the left sub-tree in postorder style.
  2. Then, traverse the right sub tree in postorder.
  3. At last, visit the root node (N).

In this type, the left and right sub-trees are processed recursively. The left sub-tree is traversed first in postorder. After this, the right sub-tree is traversed in post order. At last, the data of the root node is shown. Fig. 8.28 shows the postorder traversal of a binary tree.

The postorder traversing for the above Fig. 8.28 is P, Q, N, R, V, S, O, and M. This can also be shown as in Fig. 8.29. In this traversing the left sub-tree is traversed first, then right sub-tree and at last root.

In the postorder the left sub-tree is P, Q and N and the right sub-tree is R, V, S and O.

Figure 8.28 Tree for post order

Figure 8.29 Postorder traverse

Example 8.4

Program for inserting the nodes in tree and traversing these nodes by using the postorder method.

Solution

#include<stdio.h>

#include<conio.h>

struct tree

{

long data;

struct tree *left;

struct tree *right;

};

struct tree *btree=NULL;

struct tree *insert(struct tree*btree,long digit);

void postorder(struct tree*btree);

main()

{

long digit;

clrscr();

puts("Enter integers: and 0 to quit");

scanf("%ld",&digit);

while(digit!=0)

{

btree= insert(btree,digit);

scanf("%d",&digit);

}

puts("Postorder traversing btree:\n");

postorder(btree);

}

struct tree*insert(struct tree*btree,long digit)

{

if(btree==NULL)

{

btree=(struct tree*) malloc(sizeof(struct tree));

btree->left=btree->right=NULL;

btree->data=digit;

}

else

{

if(digit<btree->data)

btree->left=insert(btree->left,digit);

else

if(digit>btree->data)

btree->right=insert(btree->right,digit);

else

if(digit==btree->data)

{

puts("Duplicates nodes: Program exited");

exit(0);

}

}

return(btree);

}

void postorder(struct tree*btree)

{

if(btree!=NULL)

{

postorder(btree->left);

postorder(btree->right);

printf("%4ld",btree->data);

}

}

OUTPUT

Enter integers: and 0 to quit

5 3 4 1 9 6 7 0

Postorder traversing btree:

1 4 3 7 6 9 5

Explanation In this program, *btree is used to store the binary tree. The *btree is the structure variable of the structure tree. In this program the insert() is invoked to insert the elements in the *btree. postorder() is used to traverse the binary tree in the post order manner. The Fig. 8.30 shows the btree which is inserted in the program.

The postorder traversing of the tree in Fig. 8.30 is 1, 4, 3, 7, 6, 9 and 5.

Figure 8.30 btree of the above program

Example 8.5

Write a menu-driven program for various traversals such as 1) inorder 2) preorder 3) postorder.

Solution

#include<stdio.h>

#include<conio.h>

struct tree

{

long data;

struct tree *left;

struct tree *right;

};

struct tree *btree=NULL;

struct tree *insert(struct tree*btree,long digit);

void inorder(struct tree*btree);

void preorder(struct tree*btree);

void postorder(struct tree*btree);

main()

{

long digit;

int ch;

clrscr();

puts("Enter integers: and 0 to quit");

scanf("%ld",&digit);

while(digit!=0)

{

btree= insert(btree,digit);

scanf("%d",&digit);

}

while(1)

{

clrscr();

printf(" 1] For Inorder traversal of btree\n");

printf(" 2] For Preorder traversal of btree\n");

printf(" 3] For Postorder traversal of btree\n");

printf(" 4] For Exit\n");

printf("Enter the choice:-");

scanf("%d",&ch);

switch(ch)

{

case 1: printf("The inorder traversing of tree\n");

        inorder(btree);

        getch(); break;

case 2: printf("The preorder traversing of tree\n");

        preorder(btree);

        getch(); break;

case 3: printf("The postorder traversing of tree\n");

        postorder(btree);

        getch(); break;

default: exit(0);

}

}

}

struct tree*insert(struct tree*btree,long digit)

{

if(btree==NULL)

{

btree=(struct tree*) malloc(sizeof(struct tree));

btree->left=btree->right=NULL;

btree->data=digit;

}

else

{

if(digit<btree->data)

btree->left=insert(btree->left,digit);

else

if(digit>btree->data)

btree->right=insert(btree->right,digit);

else

if(digit==btree->data)

{

puts("Duplicates nodes: Program exited");

exit(0);

}

}

return(btree);

}

void inorder(struct tree*btree)

{

if(btree!=NULL)

{

inorder(btree->left);

printf("%4ld",btree->data);

inorder(btree->right);

}

}

void preorder(struct tree*btree)

{

if(btree!=NULL)

{

printf("%4ld",btree->data);

preorder(btree->left);

preorder(btree->right);

}

}

void postorder(struct tree*btree)

{

if(btree!=NULL)

{

postorder(btree->left);

postorder(btree->right);

printf("%4ld",btree->data);

}

}

OUTPUT

Enter integers: and 0 to quit

5 3 1 4 11 8 12 0

1] For Inorder traversal of btree

2] For Preorder traversal of btree

3] For Postorder traversal of btree

4] For Exit

Enter the choice:-1

The inorder traversing of tree

1 3 4 5 8 11 12

1] For Inorder traversal of btree

2] For Preorder traversal of btree

3] For Postorder traversal of btree

4] For Exit

Enter the choice:-3

The postorder traversing of tree

1 4 3 8 12 11 5

Explanation This program uses the switch() and case for the menu-driven purpose, the structure tree is used to store the whole tree and the left and right pointer of the tree is used to maintain the left and right sub-tree. The function inorder() is used for displaying the tree in inorder and similarly, the postorder() and preorder() used for the traversing purpose. The tree, which is used in this program, is shown in Fig. 8.31.

Figure 8.31 Tree representation

8.10 CONVERSION OF EXPRESSION INTO POSTFIX

The arithmetic expression can be converted from infix to postfix. Consider the following example:

(A+B)*(D/E)

In the conversion of the expression into binary tree the operator divides the expression into two parts, and on that basis the binary tree is formed. Always the operators are at the root nodes and the operands are at the leaf nodes.

In above expression at first the ‘*’ operator divides the expression into the two parts, i.e. (A+B) and (D/E). The ‘*’ is at the root of the tree.

Figure 8.32 Expression in binary tree

Further, the (A+B) and (D/E) can be converted into the binary tree as shown below:

Example 8.1

Write a program to convert infix to postfix expression.

Solution

#include<stdio.h>

#include<conio.h>

#include<string.h>

char stack[50];

int top=−1;

void post(char inexp[]);

void push(char);

char pop();

int preced(char c);

main()

{

char inexp[25];

clrscr();

printf("\nEnter the inexp expression:- ");

scanf("%s",inexp);

post(inexp);

getch();

}

void push(char sy)

{

if(top>=49)

{

printf("\nstack overflow");

getch();

}

else

{

top=top+1;

stack[top]=sy;

}

}

char pop()

{

char item; if(top==−1)

{

printf("\nStack is empty");

getch();

return 0;

}

else

{

item=stack[top];

top−−;

}

return(item);

}

int preced(char ch)

{

if(ch==47)

return(5);

if(ch==42)

return(4);

if(ch==43)

return(3);

return(2);

}

void post(char inexp[])

{

int len;

static int index=0,pt=0;

char oper,temp;

char postf[40];

len=strlen(inexp);

push('#');

while(index<len)

{

oper=inexp[index];

switch(oper)

{

case '(': push(oper);

      break;

case ')': temp=pop();

while(temp!='(')

{

postf[pt]=temp;

pt++;

temp=pop();

}

break;

case '+':

case '-':

case '*':

case '/':

case '^':

while(preced(stack[top])>=preced(oper))

{

temp=pop();

postf[pt]=temp;

pt++;

}

push(oper);

break;

default: postf[pt++]=oper;

break;

}

index++;

}

while(top>0)

{

temp=pop();

postf[pt++]=temp;

}

postf[pt++]='\0';

printf("\nThe expression into postfix:-");

printf("%s",postf);

}

OUTPUT

Enter the inexp expression:- (A+B)*(C/D)

The expression into postfix:-AB+CD/*

8.11 BINARY SEARCH TREE

A binary search tree is also called as binary sorted tree. Binary search tree is either empty or each node N of tree satisfies the following property:

  1. The key value in the left child is not more than the value of root.
  2. The key value in the right child is more than or identical to the value of root.
  3. All the sub-trees, i.e. left and right sub-trees follow the two rules mentioned above.

Binary search tree is shown in Fig. 8.33.

In Fig. 8.33 number 7 is the root node of the binary tree. There are two sub-trees to root 7. The left sub-tree is 4 and right sub-tree is 8. Here, the value of left sub-tree is lower than root and value of right sub-tree is higher than root node. This property can be observed at all levels in the tree.

Figure 8.33 Binary search tree

8.11.1 Searching an Element in Binary Search Tree

The item which is to be searched is compared with the root node.If it is less than the root node then the left child of left sub tree is compared otherwise right child is compared. The process would be continued till the item is found. A program based on the above point is given below.

Example 8.5

Write a program to search an element from the binary tree.

Solution

#include<stdio.h>

#include<conio.h>

struct tree

{

long data;

struct tree *left;

struct tree *right;

};

int sn;

struct tree *bt=NULL;

struct tree *insert(struct tree*bt,long no);

void search(struct tree *bt, long sn);

main()

{

long no;

clrscr();

puts("Enter the nodes of tree in preorder: and 0 to quit");

scanf("%ld",&no);

while(no!=0)

{

bt= insert(bt,no);

scanf("%d",&no);

}

printf("\nEnter the number to search:-");

scanf("%d",&sn);

search(bt,sn);

}

struct tree*insert(struct tree*bt,long no)

{

if(bt==NULL)

{

bt=(struct tree*) malloc(sizeof(struct tree));

bt->left=bt->right=NULL;

bt->data=no;

}

else

{

if(no<bt->data)

bt->left=insert(bt->left,no);

else

if(no>bt->data)

bt->right=insert(bt->right,no);

else

if(no==bt->data)

{

puts("Duplicates nodes: Program exited");

exit(0);

}

}

return(bt);

}

void search(struct tree*bt, long fn)

{

if(bt==NULL)

puts("The number does not exit");

else

if(fn==bt->data)

printf("The number %d is present in tree",fn);

else

if(fn<bt->data)

search(bt->left,fn);

else

search(bt->right, fn);

}

OUTPUT

Enter the nodes of tree in preorder: and 0 to quit 3 5 11 17 34 0

Enter the number to search:-17

The number 17 is present in tree

Enter the nodes of tree in preorder: and 0 to quit

3 5 11 17 34 0

Enter the number to search:-4

The number does not exit

Explanation This program contains struct tree which is used to store the binary tree. The insert() function inserts the nodes into the binary tree. The search() function searches the number from the tree. The fn variable is used to store the number which the user will not find. The search function first compares thefn with the root node. If the value of fn is less than the root node then the function searches the number in the left sub-tree, else it finds the number in the right sub-tree.

8.11.2 Insertion of an Element in Binary Search Tree

Insertion of an element in binary search tree needs to locate the parent node. The element to be inserted in the tree may be on the left sub-tree or right sub-tree. If the inserted number is lesser than the root node then left sub-tree is recursively called, otherwise right sub-tree is chosen for insertion. A program based on the above notion is described below.

Example 8.1

Write a program to insert an element into the binary search tree.

Solution

#include<stdio.h>

#include<conio.h>

struct tree

{

long data;

struct tree *left;

struct tree *right;

};

int in;

struct tree *bt=NULL;

struct tree *insert(struct tree*bt,long no);

void inorder(struct tree *bt);

main()

{

long no;

clrscr();

puts("Enter the nodes of tree in preorder: and 0 to quit");

scanf("%ld",&no);

while(no!=0)

{

bt= insert(bt,no);

scanf("%d",&no);

}

printf("Enter the number to insert:- ");

scanf("%d",&in);

bt=insert(bt,in);

printf("The inorder of tree after insertion of an element\n");

inorder(bt);

}

struct tree*insert(struct tree*bt,long no)

{

if(bt==NULL)

{

bt=(struct tree*) malloc(sizeof(struct tree));

bt->left=bt->right=NULL;

bt->data=no;

}

else

{

if(no<bt->data)

bt->left=insert(bt->left,no);

else

if(no>bt->data)

bt->right=insert(bt->right,no);

else

if(no==bt->data)

{

puts("Duplicates nodes: Program exited");

exit(0);

}

}

return(bt);

}

void inorder(struct tree *bt)

{

if(bt!=NULL)

{

inorder(bt->left);

printf("%d ",bt->data);

inorder(bt->right);

}

}

OUTPUT

Enter the nodes of tree in preorder: and 0 to quit

7 5 9 0

Enter the number to insert:- 2

The inorder of tree after insertion of an element

2 5 7 9

Explanation This program invokes a function insert() which inserts the node into the structure pointer object *bt. Firstly, the nodes which are to be inserted are entered and then program calls insert() for insertion of new element. The new inserted element firstly checks with the root of the tree. If the number is lesser than the root node it is recursively checked with the nodes, which are present on the left sub-tree, otherwise right sub-tree. Appropriate position of parent node is found and the element is inserted. After insertion, elements are arranged in inorder using the inorder() and the same numbers are displayed on the screen.

8.11.3 Traversing the Binary Search Tree

The binary search tree can be traversed similar to the binary tree by the inorder, preorder and postorder traversing methods.

Example 8.1

Program to traverse the binary search tree by using the inorder, preorder and postorder methods.

Solution

# include <stdio.h>

# include <conio.h>

struct rec

{

int data;

struct rec *left;

struct rec *right;

};

struct rec *t1;

struct rec *insert(struct rec * t1, int data);

void inorder(struct rec *t1);

void preorder(struct rec *t1);

void postorder(struct rec *t1);

main()

{

int digit;

clrscr();

printf("\nEnter the t1 in pre order and 0 to quit\n");

scanf("%d",&digit);

while(digit!=0)

{

t1=insert(t1,digit);

scanf("%d",&digit);

}

printf("\nThe preorder of the t1 is\n");

preorder(t1);

printf("\nThe inorder of the t1 is\n");

inorder(t1);

printf("\nThe post order of the t1 is\n");

postorder(t1);

}

struct rec *insert(struct rec * t1, int digit)

{

if(t1==NULL)

{

t1=(struct rec *) malloc (sizeof(struct rec));

t1->left= t1->right=NULL;

t1->data=digit;

}

else

if(digit< t1->data)

t1->left=insert(t1->left,digit);

else

if(digit > t1->data)

t1->right=insert(t1->right, digit);

else

if(digit==t1->data)

{

printf("Duplicate node: program exited");

exit(0);

}

return(t1);

}

void inorder(struct rec *t1)

{

if(t1!=NULL)

{

inorder(t1->left);

printf("%d ",t1->data);

inorder(t1->right);

}

}

void preorder(struct rec *t1)

{

if(t1!=NULL)

{

printf("%d ",t1->data);

preorder(t1->left);

preorder(t1->right);

}

}

void postorder(struct rec *t1)

{

if(t1!=NULL)

{

postorder(t1->left);

postorder(t1->right);

printf("%d ",t1->data);

}

}

OUTPUT

Enter the t1 in pre order and 0 to quit

3 2 4 0

The preorder of the t1 is

3 2 4

The inorder of the t1 is

2 3 4

The post order of the t1 is

2 4 3

Explanation The program first gets the binary search tree into the structure object t1. And the insert() is used to insert the element into the tree. The three functions inorder(), preorder() and postorder() are used to traverse the tree in appropriate manner.

8.12 THREADED BINARY TREE

While studying the linked representation of a binary tree, it is observed that the number of nodes that have null values are more than the non-null pointers. The number of left and right leaf nodes has number of null pointer fields in such a representation. These null pointer fields are used to keep some other information for operations of binary tree. The null pointer fields are to be used for storing the address fields of higher nodes in tree, which is called thread. Threaded binary tree is the one in which we find these types of pointers from null pointer fields to higher nodes in a binary tree. Consider the following tree:

Figure 8.34 A binary tree with null pointers

In Fig. 8.34, in the binary tree there are 7 null pointers. These are shown with the dotted lines. There are total 12 node pointers out of which 5 are actual node pointers, i.e. non-null pointer (solid lines). For any binary tree having n nodes there will be (n+1) null pointers and 2n total pointers. All the null pointers can be replaced with appropriate pointer value known as thread. The binary tree can be threaded according to appropriate traversal method. The null pointer can be replaced as follows:

Threaded binary tree can be traversed by any one of the three traversals, i.e. preorder, postorder and inorder. Further, in inorder threading there may be one-way inorder threading or two-way inorder threading. In one way inorder threading the right child of the node would point to the next node in the sequence of the inorder traversal. Such a threading tree is called right in threaded binary tree. Also, the left child of the node would point to the previous node in the sequence of inorder traversal. This type of tree is called as left in threaded binary tree. In case both the children of the nodes point to other nodes then such a tree is called as fully threaded binary tree.

Fig. 8.35 describes the working of right in threaded binary tree in which one can see that the right child of the node points to the node in the sequence of the inorder traversal method.

Figure 8.35 Right in threaded binary tree

The inorder traversal shown in the Fig. 8.35 will be as M-K-N-J-O-L. Two dangling pointers are shown to point a header node as shown below:

  • rchild of M is made to point to K
  • rchild of N is made to point to J
  • rchild of O is made to point to L.

Similarly, the working of the left in binary threaded tree is illustrated in Fig. 8.36. In this case the left child of node points to the previous node in the sequence of inorder traversal.

As shown in Fig. 8.36, thread of N points to K. Here, K is the predecessor of N in inorder traversal. Hence, the pointer points to K. In this type of tree the pointers pointing to other nodes are as follows:

  • lchild of N is made to point to K
  • lchild of O is made to point to J.

Figure 8.36 Left in threaded binary tree

Fig. 8.37 illustrates the operation of fully threaded binary tree. Right and left children are used for pointing to the nodes in inorder traversal method.

  • rchild of M is made to point to K
  • lchild of N is made to point to K
  • rchild of N is made to point to J
  • lchild of O is made to point to J
  • rchild of O is made to point to L.

Figure 8.37 Fully threaded binary tree

Fully threaded binary tree with header is described in Fig. 8.38.

rchild of M is made to point to K

lchild of M is made to point to Header

lchild of N is made to point to K

rchild of N is made to point to J

lchild of O is made to point to J

rchild of O is made to point to L

rchild of L is made to point to Header.

Figure 8.38 Fully threaded tree with header

The working of the fully threaded binary tree is illustrated in Fig. 8.38. In this case the left child of node points to the previous node in the sequence of inorder traversal and right child of the node points to the successor node in the inorder traversal of the node. In the previous two methods left and right pointers of the first and last node in the inorder list are NULL. But in this method the left pointer of the first node points to the header node and the right pointer of the last node points to the header node. The header node’s right pointer points to itself, and the left pointer points to the root node of the tree. The use of the header is to store the starting address of the tree. In the fully threaded binary thread each and every pointer points to the other nodes. In this tree we do not find any NULL pointers.

In the Fig. 8.38 the first node in the inorder is M and its left pointer points to the left pointer of the header node. Similarly, the last node in the inorder is L and its right pointer points to the left pointer of the header.

In memory representation of threaded binary tree, it is very important to consider the difference between thread and normal pointer. The threaded binary tree node is represented in Fig. 8.39.

Figure 8.39 Representation of the node

Each node of any binary tree stores the three fields. The left field stores the left thread value and the right field stores the right thread value. The middle field contains the actual value of the node, i.e. data.

8.13 HEIGHT-BALANCED TREE

The efficiency of searching process in binary tree depends upon the method in which the data is organised. A binary tree is said to be completely balanced binary tree if all its leaves present at nodes of level h or h−1 and all its nodes at level less than h−1 contain two children.

Figure 8.40 Full binary tree

Figure 8.41 A degenerate binary tree

A tree is height balanced tree when each node in the left sub-tree varies from right sub-tree by not more than one.

A nearly height balanced tree is called an AVL. This form of tree is studied and defined by Russian mathematician G.M. Adel’son-Velskii and E.M. Landis in 1962.

We can conclude number of nodes might be present in a balanced tree having height h. At level one there is only one node, i.e. root. In every successive level the number of nodes increases i.e. 2 nodes at level 2, 4 nodes at level 3, and so on. There will be 21−1 nodes at level 1. Thus, we can calculate total number of nodes from level 1 through level h−1 will be 1+2+22+23+…..+ 2h−2 =2h−1 −1. The number of nodes at level h may be from 1 to 2h−1 nodes. The total number of nodes (n) of tree range from 2h−1 to 2h−1 or (2h−1−1+1).

Figure 8.42 Completely balanced tree

An AVL tree should satisfy the following rules:

  1. A node is known as left heavy if the longest path in its left child (left sub-tree) is longer than the longest path in right sub-tree.
  2. A node is known as right heavy if the longest path in its right sub-tree is longer than left sub-tree.
  3. A node is known as balanced if the longest path in left and right sub-trees are identical.
8.14 B-TREE (BALANCED MULTI-WAY TREE)

Binary search tree is, in general called multi-way search tree. The integer m is called the order of the tree. Each node should have maximum m children. If k < m, where m is number of children, then node has accurately k−1 keys which divides all the keys into k number of sets. In case some sets are empty, the children are also empty.

The B-tree is also known as the balanced sort tree. The B-tree is used in external sorting. The B-tree is not a binary tree. While implementing B-tree following conditions are followed:

  1. The height of the tree must be minimum.
  2. There should be no empty sub-trees after the leaves of the tree.
  3. The leaves of the tree should be at the same level.
  4. All nodes excepting the leaves should have at least few children.

8.14.1 B-Tree Insertion

In B-tree insertion at first search is made where the new element is to be placed. If the node is suitable to the given element then insertion is straightforward. The element is inserted by using an appropriate pointer in such an order that number of pointers will be one more than the number of records. In case, the node overflows due to upper bound of node, splitting is mandatory. The node is divided into three parts. The middle part is passed upward. It will be inserted into the parent. Partition may spread the tree. This is because the parent into which element is to be inserted spilts into its child nodes. If the root is needed to be split, a new root is created with two children. The tree grows by one level.

Example: Consider the following B-tree of degree 4. It can be balanced in four ways. Here, each node holds elements. It also has four branches. Suppose, it has the following values:

The value 1 is put in a new node. This node can also hold next two values.

When value 2 (4th value ) is put, the node is split at 5 into leaf nodes. Here, 5 is parent. The element 8 is added in leaf node. The search for its accurate position is done in the node having value 6. The element 8 also is present in the same node.

The element 13 is to be inserted. However, the right leaf node, in which 1 to 3 values have appropriate plane, is occupied. Hence, the node splits at median 8 and this moves it up to the parent.

By following the above procedure the remaining nodes can be included. The final figure would be as follows:

8.14.2 B-Tree Deletion

In B-Tree deletion the element which is to be deleted is searched. In case the element is terminal node, the deletion process is straightforward. The element with a suitable pointer is deleted.

If the element fixed for deletion is not a terminal node, it is replaced by its successor element. Actually, a copy of successor is taken. The successor is an element with higher value. The successor of any node which is not at lowest level, be a terminal node. Thus, deletion is nothing but removing of a particular element or record from a terminal node. While deleting the record the new node size is more than minimum, i.e. the deletion is complete. If the node size is less than minimum, an underflow happens.

Rearrangement is done if either of adjacent siblings has more than the minimum elements (records). For rearrangement, the contents of the node (only those nodes having less than minimum records) along with sorting out records from parent node are gathered. The central record is written back to the parent and left and right halves are written back to two siblings.

Concatenation is applied if the node with less than minimum number of records has no adjacent sibling. The node is combined with its neighbouring sibling and element is moved from its parent.

  1. Deleting K is straightforward because it is a leaf node.
  2. Deleting E is not simple. Hence, its successor is moved up. E is moved down and deleted.
  3. To delete P, the node has less than minimum numbers of keys. The sibling is carried. R moves up and Q moves down.
  4. Deleting H, again node has less than minimum keys than required. The parent is left with only one key. Here, sibling cannot be applied. Hence, A, C, D and R form a new node.
8.15 B-TREE OF ORDER 5

We can build a B-tree of order 5.

  1. CDF are inserted in the same node.
  2. Insert B. The node is full. It is splitted. Here, A is median in BCADF. A is parent. The splitting is at root node. We should make one node.
  3. Again, insert P, Q, R, S.
  4. E can be added in DPQF and here Q is median.
  5. X and Y are entered after Q.
  6. After addition of T.
  7. J, K are inserted.
  8. L can be added FEXY and X will be median.
  9. Z can be placed in DPJK and it will be promoted to TAQX. But this is also full and hence, the root will split and new root will be created.
8.16 B+ TREE

A B+ tree can be obtained with slight modification of indexing in B tree. A B+ tree stores key values repeatedly. Fig. 8.43 shows B+ tree indexing.

Figure 8.43 B+ tree

By observing Fig. 8.43, we will come to know that the key values 10, 22 and 13 are stored repeatedly in the last level (terminal nodes). In these leaf nodes a link is maintained so that the traversing can be done from the leaf node at the extreme left to the leaf node at the extreme right. B tree and B+ tree are same except the above differences.

Every leaf node of B+ tree has two parts:

  1. Index part It is the interior node stored repeatedly.
  2. Sequence set It is a set of leaf nodes.

The interior nodes or keys can be accessed directly or sequentially. B+ tree is useful data structure in indexed sequential file organization.

Exercises
  1. Answer the following questions:
    1. Explain trees and binary trees.
    2. Give the properties of binary tree.
    3. Explain the various types of binary trees.
    4. Define the following terminologies of tree:
      1. Height
      2. Degree of a node
      3. Siblings
      4. Terminal node.
    5. How are binary trees represented?
    6. Give the working of binary trees.
    7. What is meant by traversing? List the methods of node traversing. Explain briefly.
    8. What are the differences between tree and graph?
    9. What is binary search tree? How is an element searched?
    10. Explain the procedure of insertion and deletion of data with binary search tree.
  2. Select the appropriate option for each of the following questions:
    1. Traversing means
      1. visiting all the nodes of the list
      2. shifting all the nodes at forward
      3. randomly accessing the elements
      4. none of the above.
    2. Every tree structure must contain
      1. root node
      2. either left right branch with root node
      3. both left and right branches with root
      4. all of the above.
    3. When every no-leaf node in binary tree has filled left and right sub-trees, the tree is called
      1. strictly binary tree
      2. complete binary tree
      3. binary search tree
      4. none of the above.
    4. The last node of this binary tree contains two branches. Such a tree is called
      1. strictly binary tree
      2. complete binary tree
      3. extended binary tree
      4. none of the above.
    5. The following sequence of the traversing is called

      Go to the root

      Traverse the left sub-tree

      Traverse the right sub-trees

      1. inorder
      2. preorder
      3. postorder
      4. pre-postorder.
    6. The following sequence of the traversing is called

      Traverse the left sub tree in inorder

      Visit root node.

      Traverse the right sub tree in inorder.

      1. inorder
      2. postorder
      3. preorder
      4. pre-postorder.
    7. The following sequence of the traversing is called

      Traversing the left sub-tree in postorder style.

      Traverse the right sub tree in postorder.

      Visit the root node (N).

      1. inorder
      2. postorder
      3. preorder
      4. pre-postorder.
    8. The tree given below is called as
      1. complete tree
      2. left-skewed binary tree
      3. right-skewed binary tree
      4. none of above.

      Consider the above figure for the following questions:

    9. The tree contains____level(s).
      1. one
      2. zero
      3. two
      4. none of the above.
    10. Degree of the B node is
      1. one
      2. two
      3. three
      4. none of the above.
    11. Height of the tree is
      1. two
      2. three
      3. four
      4. none of the above.
    12. Siblings of B are
      1. F and G
      2. D and E
      3. A and C
      4. none of the above.
    13. If root node ‘A’ is deleted then the left sub tree contains the elements
      1. C, F, and G
      2. A, B, and C
      3. B, D, and E
      4. none of the above.
  3. Attempt the following programs:
    1. Write a program to create tree structure, perform insert and delete operations.
    2. Write a program to traverse the binary search tree with different traversal methods such as inorder, preorder and postorder.
    3. Construct binary tree for the following data:

      Inorder: F E A C D G H B I

      Postorder: E F C D H I B G A

    4. Construct the binary tree for the following:

      1.

      Inorder: 3 5 6 8 12 15 18 19

      Preorder: 12 5 3 6 8 18 15 19

      Postorder: 3 8 6 5 15 19 18 12

      2.

      Preorder: A E F D J H I G B C

      Inorder: F E A H J I D B G C

      3.

      Inorder: 1 3 4 5 6 7 9 12

      Postorder: 3 5 4 1 7 12 9 6

    5. Determine the preorder, inorder and postorder of the following trees:
    6. Write a C program to insert nodes into a binary tree and traverse them in preorder.
    7. Write a program for finding the height of the tree.
    8. Write a program to display all the nodes of the binary search tree and then insert data and display it along with the previous data of the tree.
    9. Write a C program to search an element from the binary search tree.
    10. Write a program for implementing binary tree traversal.
  4. What is the output of each of the following programs?
    1. #include<stdio.h>

      #include<conio.h>

      struct tree

      {

      long num;

      struct tree *ltree;

      struct tree *rtree;

      };

      struct tree *btree=NULL;

      struct tree *insert(struct tree*tree,long digit);

      void func_trv(struct tree*tree);

      main()

      {

      long digit;

      clrscr();

      puts("Enter integers: and 0 to quit");

      scanf("%ld",&digit);

      while(digit!=0)

      {

      tree= insert(tree,digit);

      scanf("%d",&digit);

      }

      puts("func_trv traversing tree:\n");

      func_trv(tree);

      struct tree*insert(struct tree*tree,long digit)

      {

      if(tree==NULL)

      {

      tree=(struct tree*) malloc(sizeof(struct tree));

      tree->ltree=tree->rtree=NULL;

      tree->num=digit;

      }

      else

      {

      if(digit<tree->num)

      tree->ltree=insert(tree->ltree,digit);

      else

      if(digit>tree->num)

      tree->rtree=insert(tree->rtree,digit);

      else

      if(digit==tree->num)

      {

      puts("Duplicates nodes: Program exited");

      exit(0);

      }

      }

      return(tree);

      }

      void func_trv(struct tree*tree)

      {

      if(tree!=NULL)

      {

      func_trv(tree->ltree);

      printf("%4ld",tree->num);

      func_trv(tree->rtree);

      }

      }

    2. #include<stdio.h>

      #include<conio.h>

      struct tree

      {

      long no;

      struct tree *ls;

      struct tree *rs;

      };

      struct tree *btree=NULL;

      struct tree *creat(struct tree*btree,long ele);

      void fun1(struct tree*btree);

      main()

      {

      long ele;

      clrscr();

      puts("Enter integers: and 0 to quit");

      scanf("%ld",&ele);

      while(ele!=0)

      {

      btree= creat(btree,ele);

      scanf("%d",&ele);

      }

      puts("traversing by funl tree:\n");

      funl(btree);

      }

      struct tree*creat(struct tree*btree,long ele)

      {

      if(btree==NULL)

      {

      btree=(struct tree*) malloc(sizeof(struct tree));

      btree->ls=btree->rs=NULL;

      btree->no=ele;

      }

      else

      {

      if(ele<btree->no)

      btree->ls=creat(btree->ls,ele);

      else

      if(ele>btree->no)

      btree->rs=creat(btree->rs,ele);

      else

      if(ele==btree->no)

      {

      puts("Duplicates nodes: Program exited");

      exit(0);

      }

      }

      return(btree);

      }

      void fun1(struct tree*btree)

      {

      if(btree!=NULL)

      {

      printf("%4ld",btree->no);

      funl(btree->ls);

      funl(btree->rs);

      }

      }

    3. #include<stdio.h>

      #include<conio.h>

      struct tree

      {

      long data;

      struct tree *left;

      struct tree *right;

      };

      struct tree *bt=NULL;

      struct tree *insert(struct tree*bt,long no);

      void fun_t(struct tree*bt);

      main()

      {

      long no;

      clrscr();

      puts("Enter integers: and 0 to quit");

      scanf("%ld",&no);

      while(no!=0)

      {

      bt= insert(bt,no);

      scanf("%d",&no);

      }

      puts("traversing btree by fun_t:\n");

      fun_t(bt);

      }

      struct tree*insert(struct tree*bt,long no)

      {

      if(bt==NULL)

      {

      bt=(struct tree*) malloc(sizeof(struct tree));

      bt->left=bt->right=NULL;

      bt->data=no;

      }

      else

      {

      if(no<bt->data)

      bt->left=insert(bt->left,no);

      else

      if(no>bt->data)

      bt->right=insert(bt->right,no);

      else

      if(no==bt->data)

      {

      puts("Duplicates nodes: Program exited");

      exit(0);

      }

      }

      return(bt);

      }

      void fun_t(struct tree*bt)

      {

      if(bt!=NULL)

      {

      fun_t(bt->left);

      fun_t(bt->right);

      printf("%4ld",bt->data);

      }

      }

    4. #include<stdio.h>

      #include<conio.h>

      struct tree

      {

      long data;

      struct tree *left;

      struct tree *right;

      };

      struct tree *bt=NULL;

      struct tree *insert(struct tree*bt,long no);

      void fun1(struct tree*bt);

      void fun2(struct tree*bt);

      void fun3(struct tree*bt);

      main()

      {

      long no;

      clrscr();

      puts("Enter integers: and 0 to quit");

      scanf("%ld",&no);

      while(no!=0)

      {

      bt= insert(bt,no);

      scanf("%d",&no);

      }

      puts("fun1 traversing bt:\n");

      funl(bt);

      puts("\nfun2 traversing bt:\n");

      fun2(bt);

      puts("\nfun3 traversing bt:\n");

      fun3(bt);

      }

      struct tree*insert(struct tree*bt,long no)

      {

      if(bt==NULL)

      {

      bt=(struct tree*) malloc(sizeof(struct tree));

      bt->left=bt->right=NULL;

      bt->data=no;

      }

      else

      {

      if(no<bt->data)

      bt->left=insert(bt->left,no);

      else

      if(no>bt->data)

      bt->right=insert(bt->right,no);

      else

      if(no==bt->data)

      {

      puts("Duplicates nodes: Program exited");

      exit(0);

      }

      }

      return(bt);

      }

      void fun2(struct tree*bt)

      {

      if(bt!=NULL)

      {

      fun2(bt->left);

      fun2(bt->right);

      printf("%4ld",bt->data);

      }

      }

      void fun1(struct tree*bt)

      {

      if(bt!=NULL)

      {

      printf("%4ld",bt->data);

      fun1(bt->left);

      fun1(bt->right);

      }

      }

      void fun3(struct tree*bt)

      {

      if(bt!=NULL)

      {

      fun3(bt->left);

      printf("%4ld",bt->data);

      fun3(bt->right);

      }

      }

    5. #include<stdio.h>

      #include<conio.h>

      struct tree

      {

      long num;

      struct tree *left;

      struct tree *right;

      };

      int sn;

      struct tree *bt=NULL;

      struct tree *place(struct tree*bt,long digit);

      void fun_s(struct tree *bt, long sn);

      main()

      {

      long digit;

      clrscr();

      puts("Enter the nodes of tree in preorder:

      and 0 to quit");

      scanf("%ld",&digit);

      while(digit!=0)

      {

      bt= place(bt,digit);

      scanf("%d",&digit);

      }

      printf("\nEnter the number:-");

      scanf("%d",&sn);

      fun_s(bt,sn);

      }

      struct tree*place(struct tree*bt,long digit)

      {

      if(bt==NULL)

      {

      bt=(struct tree*) malloc(sizeof(struct tree));

      bt->left=bt->right=NULL;

      bt->num=digit;

      }

      else

      {

      if(digit<bt->num)

      bt->left=place(bt->left,digit);

      else

      if(digit>bt->num)

      bt->right=place(bt->right,digit);

      else

      if(digit==bt->num)

      {

      puts("Duplicates nodes: Program exited");

      exit(0);

      }

      }

      return(bt);

      }

      void fun_s(struct tree*bt, long sno)

      {

      if(bt==NULL)

      puts("Number does not found");

      else

      if(sno==bt->num)

      printf("Number %d is found",sno);

      else

      if(sno<bt->num)

      fun_s(bt->left,sno);

      else

      fun_s(bt->right, sno);

      }