Binary Search Tree

This is a discussion on Binary Search Tree within the C Programming forums, part of the General Programming Boards category; Can anyone see why the delete function is returning a segmentation fault in this code?? the values "d", "b", "f", ...

  1. #1
    Registered User
    Join Date
    Sep 2005
    Posts
    8

    Binary Search Tree

    Can anyone see why the delete function is returning a segmentation fault in this code??
    the values "d", "b", "f", "a", "c", "e", "g" are being insterted and printed correctly from a seperate source file. as soon as i try to delete a node i cant print or do anything.
    thanks
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include "bst.h"
    #include "mylib.h"
    
    struct bstnode {
       char *key;
       bst left;
       bst right;
    };
    
    bst bst_new(){
       return NULL;
    }
    
    bst bst_insert(bst b, char *key){
       if (b == NULL) {
          b =  emalloc(sizeof *b);
          b -> key = key;
          b -> left = NULL;
          b -> right = NULL;
       } else if (strcmp(key, b -> key) < 1) {
          b -> left = bst_insert(b -> left, key);
       } else {
          b -> right = bst_insert(b -> right, key);
       }
       return b;
    }
    
    char *bst_search(bst b, char *key){
       if (b == NULL) {
          return NULL;
       } else if (b -> key == key) {
          return b -> key;
       } else if (strcmp(key, b -> key) > 0) {
          return bst_search(b -> left, key);
       } else {
          return bst_search(b -> right, key);
       }
    }
    
    void bst_inorder(bst b, void f(char *s)){
       if (b == NULL) {
          return;
       } else {
          bst_inorder(b -> left, f);
          f(b -> key);
          bst_inorder(b -> right, f);
       }
    }
    
    void bst_preorder(bst b, void f(char *s)){
       if (b == NULL) {
          return;
       } else {
          f(b -> key);
          bst_preorder(b -> left, f);
          bst_preorder(b -> right, f);
       }
    }
    
    bst bst_delete(bst b, char *key){
       int x = strcmp(key, b->key);
       printf("%d\n", x);
    
       if (x<0) {
          return bst_delete(b->left, key);
       } else if (x > 0) {
          return bst_delete(b->right, key);
       } else {
          if (b->left == NULL && b->right == NULL) {
             b->key = NULL;
             b->left = NULL;
             b->right = NULL;
             return b;
          } else if (b->left == NULL) {
             b->key = b->right->key;
             b->right = b->right->right;
             b->left = b->right->left;
             return b;
          } else if (b->right == NULL) {
             b->key = b->left->key;
             b->right = b->left->right;
             b->left = b->left->left;
             return b;
          } else {
             bst b2 = b->right;
             while (b2->left != NULL) {
                b2=b2->left;
             }
             b->key = b2->key;
             return bst_delete(b2, b2->key);
          }
       }
    }

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,799
    Where is main? What is bst? What is emalloc? You haven't shown all of your code!
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 10:07 AM
  2. BST (Binary search tree)
    By praethorian in forum C++ Programming
    Replies: 3
    Last Post: 11-13-2005, 08:11 AM
  3. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 04:15 PM
  4. binary search and search using binary tree
    By Micko in forum C++ Programming
    Replies: 9
    Last Post: 03-18-2004, 09:18 AM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

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