In the case of the linked representation of a binary tree we find that half of the entries in the pointers fields LEFT and RIGHT will contain null entries. This space may be efficiently used by replacing the null entries with special pointers called Threads which point to the nodes higher in trees. Such trees are called Threaded trees.
Threads in a binary tree must be distinguished from normal pointers. There are many ways to thread a binary tree.
1. The right NULL pointer of each node can be replaced by a thread to the successor of that node under in-order traversal called a
right thread and the tree is called a right-threaded tree.
2. The left NULL pointer of each node can be replaced by a thread to the predecessor of that node under in order traversal called a
left thread and the tree will call a left threaded tree.
3. Both left and right NULL pointers can be used to point to the predecessor and successor of that node respectively under in-order traversal. Such a tree is called a fully threaded tree.
Insertion In Threaded Binary Tree
First of all, we have to find the location of the new node for insertion. The new node will be inserted as a leaf node so its left and right pointers both will be threads.
Case 1:When the tree is empty:-When the tree is empty the left pointer of the head node is a thread pointing to itself. We will insert the new node as the left child of the header node so now the left pointer of the head will be a link pointing to the newnode. We know that the left pointer of the first node in in-order traversal and the right pointer of the last node in in-order traversals are threads pointing to the header node. Here we have only one node which is the first and the last node so its left-right pointers will be threads pointing to the header node.
Case 2:When a new node is inserted as the left child of its parent:- The threads of the new node will point to its in-order predecessor and successor. The node which was the in-order predecessor of the parent is now the in-order predecessor of this node. The in-order successor of this node is its parent.
Case 3:When a new node is inserted as the right child of its parent:- The node which was the in-order successor of the parent is now the in-order successor of this node. The in-order predecessor of this node is its parent. so the left and right threads of the new node will be: tmp->leftptr=parent;tmp->rightptr=parent->child
The parent of the new node had a thread in its right pointer pointing to its successor but after insertion, its right pointer will be a link pointing to the new node. parent->right=link;parent->rchild=tmp;
Let's see the following Figure. where the insertion procedure is clearly described.
Deletion In Threaded Binary Tree
Case 1:Node to be deleted is the leaf node:- If the node to be deleted is the root node then the tree will become empty after its deletion so the left pointer of the head will be a thread pointing to itself.
If the node to be deleted is a left leaf node then the left pointer of the parent will become a thread pointing to its in-order predecessor. Initially, its in-order predecessor was its left child but now its in-order predecessor will be that node which was the predecessor of its left child.
If the node to be deleted is a right leaf node then the right pointer of the parent will become a thread pointing to its in-order successor. Initially, its in-order successor was its right child but now its in-order successor will be that node which was the successor of its right child.
Case 2: The node to be deleted has one child:- Delete the node as in the binary search tree. Find the in-order successor and in-order predecessor of the node to be deleted.
If the node has a right subtree then put the predecessor of the node in the left pointer of its successor.
If the node has left subtree then put the successor of the node in the right pointer of its predecessor.
Case 3: The node to be deleted has two children:-First we delete the in-order successor of the node and then replace the deleted node with the in-order successor. For deleting in-order successor we will call either case 1 or case 2.
Let's see the following Fig 2. where the deletion procedure is clearly described.
Fig 2. deletion 10 is replaced by inorder successor 12 in threaded binary tree.
Insertion And Deletion In Threaded Binary Tree
#include <stdio.h>
#include <stdlib.h>
enum boolean
{
false = 0,
true = 1
} ;
struct thtree
{
enum boolean isleft ;
struct thtree *left ;
int data ;
struct thtree *right ;
enum boolean isright ;
} ;
void insert ( struct thtree **, int ) ;
void delete ( struct thtree **, int ) ;
void search ( struct thtree **, int, struct thtree **,
struct thtree **, int * ) ;
void inorder ( struct thtree * ) ;
void deltree ( struct thtree ** ) ;
/* inserts a node in a threaded binary tree */
void insert ( struct thtree **s, int num )
{
struct thtree *p, *z, *head = *s ;
/* allocating a new node */
z = malloc ( sizeof ( struct thtree ) ) ;
z -> isleft = true ; /* indicates a thread */
z -> data = num ; /* assign new data */
z -> isright = true ; /* indicates a thread */
/* if tree is empty */
if ( *s == NULL )
{
head = malloc ( sizeof ( struct thtree ) ) ;
/* the entire tree is treated as a left sub-tree of the head node */
head -> isleft = false ;
head -> left = z ; /* z becomes leftchild of the head node */
head -> data = -9999 ; /* no data */
head -> right = head ; /* right link will always be pointing
to itself */
head -> isright = false ;
*s = head ;
z -> left = head ; /* left thread to head */
z -> right = head ; /* right thread to head */
}
else/* if tree is non-empty */
{
p = head -> left ;
/* traverse till the thread is found attached to the head */
while ( p != head )
{
if ( p -> data > num )
{
if ( p -> isleft != true ) /* checking for a thread */
p = p -> left ;
else
{
z -> left = p -> left ;
p -> left = z ;
p -> isleft = false ; /* indicates a link */
z -> isright = true ;
z -> right = p ;
return ;
}
}
else
{
if ( p -> data < num )
{
if ( p -> isright != true )
p = p -> right ;
else
{
z -> right = p -> right ;
p -> right = z ;
p -> isright = false ; /* indicates a link */
z -> isleft = true ;
z -> left = p ;
return ;
}
}
}
}
}
}
/* deletes a node from the binary search tree */
void delete ( struct thtree **root, int num )
{
int found ;
struct thtree *parent, *x, *xsucc ;
/* if tree is empty */
if ( *root == NULL )
{
printf ( "\nTree is empty" ) ;
return ;
}
parent = x = NULL ;
/* call to search function to find the node to be deleted */
search ( root, num, &parent, &x, &found ) ;
/* if the node to deleted is not found */
if ( found == false )
{
printf ( "\nData to be deleted, not found" ) ;
return ;
}
/* if the node to be deleted has two children */
if ( x -> isleft == false && x -> isright == false )
{
parent = x ;
xsucc = x -> right ;
while ( xsucc -> isleft == false )
{
parent = xsucc ;
xsucc = xsucc -> left ;
}
x -> data = xsucc -> data ;
x = xsucc ;
}
/* if the node to be deleted has no child */
if ( x -> isleft == true && x -> isright == true )
{
/* if node to be deleted is a root node */
if ( parent == NULL )
{
( *root ) -> left = *root ;
( *root ) -> isleft = true ;
free ( x ) ;
return ;
}
if ( parent -> right == x )
{
parent -> isright = true ;
parent -> right = x -> right ;
}
else
{
parent -> isleft = true ;
parent -> left = x -> left ;
}
free ( x ) ;
return ;
}
/* if the node to be deleted has only rightchild */
if ( x -> isleft == true && x -> isright == false )
{
/* node to be deleted is a root node */
if ( parent == NULL )
{
( *root ) -> left = x -> right ;
free ( x ) ;
return ;
}
if ( parent -> left == x )
{
parent -> left = x -> right ;
x -> right -> left = x -> left ;
}
else
{
parent -> right = x -> right ;
x -> right -> left = parent ;
}
free ( x ) ;
return ;
}
/* if the node to be deleted has only left child */
if ( x -> isleft == false && x -> isright == true )
{
/* the node to be deleted is a root node */
if ( parent == NULL )
{
parent = x ;
xsucc = x -> left ;
while ( xsucc -> right == false )
xsucc = xsucc -> right ;
xsucc -> right = *root ;
( *root ) -> left = x -> left ;
free ( x ) ;
return ;
}
if ( parent -> left == x )
{
parent -> left = x -> left ;
x -> left -> right = parent ;
}
else
{
parent -> right = x -> left ;
x -> left -> right = x -> right ;
}
free ( x ) ;
return ;
}
}
/* returns the address of the node to be deleted, address of its parent and
whether the node is found or not */
void search ( struct thtree **root, int num, struct thtree **par,
struct thtree **x, int *found )
{
struct thtree *q ;
q = ( *root ) -> left ;
*found = false ;
*par = NULL ;
while ( q != *root )
{
/* if the node to be deleted is found */
if ( q -> data == num )
{
*found = true ;
*x = q ;
return ;
}
*par = q ;
if ( q -> data > num )
{
if ( q -> isleft == true )
{
*found = false ;
x = NULL ;
return ;
}
q = q -> left ;
}
else
{
if ( q -> isright == true )
{
*found = false ;
*x = NULL ;
return ;
}
q = q -> right ;
}
}
}
/* traverses the threaded binary tree in inorder */
void inorder ( struct thtree *root )
{
struct thtree *p ;
p = root -> left ;
while ( p != root )
{
while ( p -> isleft == false )
p = p -> left ;
printf ( "%d\t", p -> data ) ;
while ( p -> isright == true )
{
p = p -> right ;
if ( p == root )
break ;
printf ( "%d\t", p -> data ) ;
}
p = p -> right ;
}
}
void deltree ( struct thtree **root )
{
while ( ( *root ) -> left != *root )
delete ( root, ( *root ) -> left -> data ) ;
}
int main()
{
struct thtree *root=NULL;
int ch,value;
while(1)
{
printf("\n1.insert");
printf("\n2.inorder");
printf("\n3.delete");
printf("\n4.exit");
printf("\nenter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:printf("\nenter the value:");
scanf("%d",&value);
insert(&root,value);
break;
case 2:inorder(root);
break;
case 3:printf("\n enter value for deletion:");
scanf("%d",&value);
delete(&root,value);
break;
case 4:return 0;
}
}
return 0;
}
Happy Exploring!
Posts
No comments:
Post a Comment