Threaded Binary Trees

Threaded Binary Trees

In threaded binary tree the leaf nodes are having the NULL values in the left and right link fields. It is just a wastage of memory. So to avoid the NULL value the threads are used. The threads are nothing but the links to predecessor and successor nodes.

There are three types of threading possible - Inorder, preorder and postorder threading.

C structure

typedef struct thread

{

int data;

int lth,rth;

struct thread *left;

struct thread *right;

}Th;

The basic idea in inorder threading is that the left thread should point to the predecessor and the right thread points to the successor. Here we are assuming the head node as the starting node and the root node of the tree is attached to left of head node which is as shown in Fig. 4.10.1.

Let us see the 'C' program for the creation of threaded binary tree.

/*****************************************************************

Program for Implementation of Inorder Threaded Binary Search Tree and perform insertion, deletion and display of tree.

*****************************************************************/

#include<stdio.h>

#include<conio.h>

#include <alloc.h>

typedef struct bst

{

int data;

int lth, rth;

struct bst *left, *right;

}node;

node *dummy;

/*

------------------------------------------------------------------------------------------

The main function

------------------------------------------------------------------------------------------

*/

void main()

{

int choice,key;

char ans='N';

node *root, *temp, *parent;                                                  

node *create(node *),*search(node*, int,node**);

void inorder(node *),del(node*,int);

clrscr();

do

{

clrscr();

printf("\n\t Program For Threaded Binary Tree");

printf("\n1.Create \n2.Display \n3.Search \n4.Delete");

scanf("%d", &choice);

switch(choice)

{

case 1:root = NULL;

do

{

root=create(root);

printf("\n Do u Want To enter More

Elements?(y/n)");

ans=getch();

} while(ans =='y');

break;

case 2:if(root == NULL)

printf("Tree Is Not Created");

else

{

printf("\n The Tree is: ");

inorder(root);

}

break;

case 3:printf("\n Enter The Element Which You Want To Search");

scanf("%d",&key);

temp=search(root,key,&parent);

if(temp== NULL)

printf("\nElement is Not Present");

else

printf("Its Parent Node is %d",parent->data);

break;

case 4:printf("\n Enter The Element U wish to Delete");

scanf("%d", &key);

del(root,key);

break;

}

printf("\n\nWant To See Main Menu?(y/n)");

ans=getche()*

} while(ans=='y');

}

/*

------------------------------------------------------------------------------------------

The create function

------------------------------------------------------------------------------------------

*/

node *create(node *root)

{

void insert(node *,node *);

node *New;

New = (node*)malloc(sizeof(node));

New->left=NULL;

New->right=NULL;

New->lth=0;

New->rth=0;

printf("\n Enter The Element ");

scanf("%d", &New->data);

if(root == NULL)

{ // Tree is not Created

root=New;

dummy = (node*)malloc(sizeof(node));

dummy->data=-999;

dummy->left=root;

root->left-dummy;

root->right-dummy;

}

else

insert(root,New);

return root;

}

/*

------------------------------------------------------------------------------------------

This function is for creating a binary search tree

------------------------------------------------------------------------------------------

*/

void insert(node *root,node *New)

{

if(New->data<root->data)

{

if(root->lth==0)

{

New->left=root->left;

New->right=root;

root->left=New;

root->Ith=1;

}

else

insert(root->left,New);

}

if(New->data>root->data)

{

if(root->rth==0)

{

New->right=root->right;

New->left=root;

root->rth=1;

root->right=New;

}

else

insert(root->right,New);

}

}

/*

------------------------------------------------------------------------------------------

The search function

------------------------------------------------------------------------------------------

*/

node *search(node *root,int key,node **parent)

{

node *temp;

temp=root;

while((temp!=dummy))

{

if(temp->data==key)

{

printf("\n The %d Element is Present",temp->data);

return temp;

}

*parent=temp;

if(temp->data>key)

temp-temp->left;

else

temp-temp->right;

}

return NULL;

}

/*

------------------------------------------------------------------------------------------

This function is for deleting a node from binary search tree There exists three possible cases for deletion of a node

------------------------------------------------------------------------------------------

*/

void del(node *root,int key)

{

node *temp, *parent,*temp_succ;

node *search(node *,int,node **);

int flag=0;

temp=search(root,key,&parent);

if(root==temp)

{

printf("\n Its Root Node Which Can Not Be Deleted!!");

return;

}

//deleting a node with two children

if(temp->lth==1&&temp->rth ==1)

{

parent=temp;

temp_succ=temp->right;//Finding Inorder successor

while(temp_succ->lth==1)

{

flag=1;

parent=temp_succ;

temp_succ=temp_succ->left;

}

if(flag==0)

{

temp->data=temp_succ->data;

parent->right-temp_succ->right;

parent->rth=0;

}

else//inorder successor is on left subbranch.

// and it has to be traversed

{

temp->data=temp_succ->data;

parent->rth=0;

parent->lth=0;

parent->left=temp_succ->left;

}

printf(" Now Deleted it!");

return;

}

//deleting a node having only one child

//The node to be deleted has left child

if(temp->lth==1 &&temp->rth==0)

{

if(parent->left==temp)

{

(temp->left)->right-parent;

parent->left-temp->left;

}

else

{

 (temp->left)->right-temp->right;

parent->right-temp->left;

temp=NULL;

delete temp;

printf(" Now Deleted it!");

return;

}

//The node to be deleted has right child

if(temp->lth==0 &&temp->rth!=0)

{

if(parent->left==temp)

{

parent->left=temp->right;

(temp->right)->left-temp->left;

(temp->right)->right=parent;

}

else

{

parent->right-temp->right;

(temp->right)->left=parent;

}

temp=NULL;

free(temp);

printf(" Now Deleted it!");

return;

}

//deleting a node which is having no child

if(temp->lth==0 &&temp->rth==0)

{

if(parent->left==temp)

{

parent->left-temp->left;

parent->lth=0;

}

else

{

parent->right-temp->right;

parent->rth=0;

}

printf(" Now Deleted it!");

return;

}

}

*/

------------------------------------------------------------------------------------------

The inorder function

------------------------------------------------------------------------------------------

void inorder(node *temp)

{

while(temp!=dummy)

{

while(temp->lth==1)

temp-temp->left;

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

while(temp->rth==0)

{

temp-temp->right;

if(temp==dummy)

return;

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

}

temp-temp->right;

}

}

Output

Program For Threaded Binary Tree

1. Create

2. Display

3. Search

4. Delete 1

Enter The Element 10

Do u Want To enter More Elements?(y/n)

 Enter The Element 8

Do u Want To enter More Elements? (y/n)

 Enter The Element 7

Do u Want To enter More Elements? (y/n)

 Enter The Element 15

Do u Want To enter More Elements?(y/n)

 Enter The Element 11

Do u Want To enter More Elements?(y/n)

 Enter The Element 17

Do u Want To enter More Elements? (y/n)

 Want To See Main Menu?(y/n)

Program For Threaded Binary Tree

1. Create

2. Display

3. Search

4. Delete2

The Tree is: 7 8 9 10 11 15 17

Want To See Main Menu?(y/n)

Program For Threaded Binary Tree

1.Create

2.Display

3.Search

4.Delete3

Enter The Element Which You Want To Search 11

The 11 Element is PresentIts Parent Node is 15

Want To See Main Menu?(y/n)

 Program For Threaded Binary Tree

1. Create

2. Display

3. Search

4. Delete 4

Enter The Element U wish to Delete 15

The 15 Element is Present Now Deleted it!

Want To See Main Menu?(y/n)

Program For Threaded Binary Tree

1. Create

2. Display

3. Search

4. Delete2

The Tree is: 7 8 9 10 11 17

Want To See Main Menu?(y/n)

Logic explanation for threaded binary tree -

In thread binary tree, the NULL pointers are avoided. Instead of left NULL pointer the link points to inorder predecessor of that node. Similarly instead of right NULL pointer the link points to inorder successor of that node.

There are two additional fields in each node named as 1th and rth these fields indicate whether left or right thread is present. Thread present means the NULL link is replaced by a link to inorder predecessor or inorder successor. To represent that there exists thread the 1th or rth fields are set to 0. Let us take one example to explain how a threaded binary tree gets created. Suppose we want to create a threaded binary tree for the nodes having values,

10, 8, 6, 12, 9, 11, 14

Initially we will create a dummy node which will act as a header of the tree.

Now let us take first value i.e. 10. The node with value 10 will be the root node we will attach this root node as left child of dummy node.

The NULL links of root's left and right child will be pointed to dummy.

Now next comes 8. The 8 will be compared with 10, as the value is less than 10, we will attach 8 as left child of 10 and we will set root's 1th field to 1, indicating that the node 10 is having left child. See then how the links are arranged.

New → left = root → left

New → right = root;

root → left = New;

root → lth = = 1;

Note that the left link of node 8 points to its inorder predecessor and right link of node 8 points to its inorder successor.

Next comes 6. The value 6 will be first compared with root i.e. with 10. As 6 is less than 10, we will move on left subbranch. The 6 will then be compared with 8, so we have to move on left subbranch of 8. But Ith of node 8 is 0, indicating that there is no left child to 8, so we will attach 6 as left child to 8.

Then comes 12. We will compare 12 with 10. As 12 is greater than 10, we will attach the node 12 as right child of 10.

Note that the left field of node 12 points to its inorder predecessor and right field of node 12 points to its inorder successor. Thus by attaching 9, 11, 14 as appropriate children, the threaded binary tree will look like this

Such a threaded tree is called inorder threaded binary tree.

Ex. 4.10.1: Create threaded binary tree for 10, 20, 30, 40, 50.

Sol. :

Advantages of threaded binary trees

1. Due to NULL links in binary tree certain amount of memory gets wastage. This wastage of memory is utilized by using threads.

2. The predecessor and successor of any node can be accessed effectively.

Disadvantage of threaded binary trees

1. Insertion and deletion of nodes become complex in threaded binary tree, since thread and link manipulation is required on every insertion.

Ex. 4.10.2 With reference to Fig. 4.10.9 answer the following

i) Is it a binary tree?

ii) Is it a complete tree?

iii) Give the preoder traversal?

iv) Give the inorder traversal?

v) Give the postorder traversal?

vi) Give list notation (using pairs of round brackets)

vii) Where will be the left child of node 4 pointing to if it is converted to threaded

viii) Is it a max heap?

Sol. :

i) Yes it is a binary tree as it consists the nodes with at the most two child nodes.

ii) No it is not a complete binary tree. The complete binary tree contains 2^{h + 1}- 1 number of nodes, The height of above tree is, h = 2. It contains 6 nodes instead of 7.

iii) Preorder Traversal 9 8 6 574

iv) Inorder Traversal 6 8 5 974

v) Postorder Traversal 6 58479

vi) List Notation (Parent, left - subtree, right-subtree)

(9, (8,6,5), (7,4))

vii) If the tree is converted to threaded binary tree then the left child of 4 will point to its predecessor i.e. 7.

viii) Yes it is a max heap because of two reasons,

i). It is almost complete binary tree

ii) The parent node is having greater value than its child nodes.

Review Questions

1. What is threaded binary tree? Explain right and left in threaded binary tree.

2. What is the advantage of threaded binary tree over binary tree? Explain threaded binary tree construction with suitable example.