removing item from binary search tree

This is a discussion on removing item from binary search tree within the C Programming forums, part of the General Programming Boards category; I'm writing simple program that's simulate Binary Search Tree. I wrote functions Insert and Show, but don't know how to ...

  1. #1
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712

    removing item from binary search tree

    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

  2. #2
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    Draw the problem out on paper first, then try to apply the logic to your code. You'll find it easier that way.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  3. #3
    ggs
    ggs is offline
    C > C++ duders ggs's Avatar
    Join Date
    Aug 2001
    Posts
    435
    try reconstructing the tree as you traverse, but leave out the node to be deleted.
    .sect signature

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >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 ); 
        } 
      }
    }
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Immediate programming help! Please!
    By xMEGANx in forum C++ Programming
    Replies: 6
    Last Post: 02-20-2008, 12:52 PM
  2. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  3. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 05:15 PM
  4. Binary Tree, couple questions
    By scoobasean in forum C Programming
    Replies: 3
    Last Post: 03-12-2005, 09:09 PM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 11:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21