removing item from binary search tree

**Micko** · 03-29-2004

I'm writing simple program that's simulate Binary Search Tree. I wrote functions Insert
and Show, but don't know how to implement function Delete (deletion by copying from prelude's tutorial). If you could wrote this function using this structure and using free function according to this declaration.I need to find appropriate node by comparing data first then to frr that node by keeping tree structure. If you could help me I would appreciate

Code:

#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
	int data;
	struct Node* left;
	struct Node* right;
}node;
void Insert(node**,int);
void Show(node*);
void Delete(int);
int main()
{
	node *root=NULL;
	Insert(&root,2);
	Insert(&root,5);
	Insert(&root,1);
	Insert(&root,0);
	Insert(&root,10);
	Show(root);
}
void Insert(node** root,int data)
{
	if(!*root)
	{
		*root=malloc(sizeof(node));
		(*root)->data=data;
		(*root)->left=NULL;
		(*root)->right=NULL;
		return;
	}
	else 
	{
	if((*root)->data>data)
		Insert(&(*root)->left,data);
	else
		Insert(&(*root)->right,data);
	}
}

void Show(node* root)
{
	if(root)
	{
		Show(root->left);
		printf("%d ",root->data);
		Show(root->right);
	}
}
void Delete (int data)
{
	//TODO
}

Thanks

**Hammer** · 03-29-2004

Draw the problem out on paper first, then try to apply the logic to your code. You'll find it easier that way.

**ggs** · 03-29-2004

try reconstructing the tree as you traverse, but leave out the node to be deleted.

**Prelude** · 03-29-2004

>but don't know how to implement function Delete (deletion by copying from prelude's tutorial)
The tutorial describes it exactly. Find the proper node, then determine which of the three deletion cases match. If there is no left child, replace with the right child. If there is no right child, replace with the left. If there are two children, find the successor or predecessor and copy the data in that node to the node that was found and delete the predecessor (or successor) using one of the simple cases.

A full recursive function is harder to wrap your brain around than a function that uses recursion to find the node and then iteration to fix the structure:

Code:

void Delete ( node **root, int data )
{
  if ( (*root) == NULL ) 
    return; 
  if ( data < (*root)->data ) 
    Delete ( &(*root)->left, data ); 
  else if ( data > (*root)->data ) 
    Delete ( &(*root)->right, data ); 
  else { 
    node *old_node;
    /* Easy case 1: No right child, replace with left */
    if ( (*root)->right == NULL ) { 
      old_node = *root; 
      *root = (*root)->left; 
      free ( old_node ); 
    } 
    /* Easy case 2: No left child, replace with right */
    else if ( (*root)->left == NULL ) { 
      old_node = *root; 
      *root = (*root)->right; 
      free ( old_node ); 
    } 
    /* Hard case 3: Two children, replace with predecessor */
    else { 
      node *heir = (*root)->left; 
      node *prev = *root; 
      while ( heir->right != NULL ) { 
        prev = heir; 
        heir = heir->right; 
      } 
      (*root)->data = heir->data; 
      if ( prev != *root ) 
        prev->right = heir->left; 
      else 
        prev->left = heir->left; 
      free ( heir ); 
    } 
  }
}

Thread: removing item from binary search tree

Thread Tools

Search Thread

Display

removing item from binary search tree

Similar Threads

Immediate programming help! Please!

binary interface to binary search tree giving me SUCH A HEADACHE!!

searching and insertion in a binary search tree

Binary Tree, couple questions

BST/Red and Black Tree