Like Tree1Likes
  • 1 Post By anduril462

Creating a Binary Search Tree

This is a discussion on Creating a Binary Search Tree within the C Programming forums, part of the General Programming Boards category; Hi, I want to create and display a binary search tree of integer keys. But, I have problem with my ...

  1. #1
    Registered User
    Join Date
    Apr 2011
    Posts
    48

    Creating a Binary Search Tree

    Hi,
    I want to create and display a binary search tree of integer keys.
    But, I have problem with my inorder function.I simply want to display the resulting ordered list after each insertion by calling function tree_inorder.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    #define TYPED_ALLOC(type) (type *)malloc(sizeof (type))
    
    typedef struct tree_node_s {
      int                     key;
      struct tree_node_s     *leftp, *rightp;
    }tree_node_t;
    
    tree_node_t *tree_insert(tree_node_t *rootp, int new_key);
    void tree_inorder(tree_node_t *rootp);
    
    int
    main(void)
    {
      tree_node_t *bs_treep;   /* binary search tree                 */
      int          data_key;   /* input - keys for tree              */
      int          status;     /* status of input operation          */
    
      bs_treep = NULL;    /* Initially, tree is empty */
      
      for (status = scanf("%d", &data_key);
           status == 1;
           status = scanf("%d", &data_key)) {
        bs_treep = tree_insert(bs_treep, data_key);
        printf("Tree after insertion of %d:\n", data_key);
        tree_inorder(bs_treep);
      }
    
      if (status == 0) {
        printf("Invalid data >>%c\n", getchar());
      }
      else {
        printf("Final binary search tree:\n");
        tree_inorder(bs_treep);
      }
      
      return(0);
    }
    
    tree_node_t *
    tree_insert(tree_node_t *rootp,   /* input/output - root node of 
    				     binary search tree    */
    	    int         new_key)  /* input - key to insert */
    {
      if (rootp == NULL) {            /* Simple Case 1 - Empty tree */
        rootp = TYPED_ALLOC(tree_node_t);
        rootp->key = new_key;
        rootp->leftp = NULL;
        rootp->rightp = NULL;
      }
      else if (new_key == rootp->key) { /* Simple Case 2 */
        /* duplicate key - no insertion                  */
      }
      else if (new_key < rootp->key) { /* Insert in       */
        rootp->leftp = tree_insert(rootp->leftp, new_key); /* left subtree */
      }
      else {
        rootp->rightp = tree_insert(rootp->rightp, new_key);
      }
    
      return(0);
    }
    void tree_inorder(tree_node_t *rootp)
    {
      if (rootp == NULL)
      return;
      tree_inorder(rootp->leftp);
      printf("%d", rootp->key);
      tree_inorder(rootp->rightp);
    }

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,498
    It's not your inorder that's broken, it's your insert:
    Code:
      return(0);
    should be:
    Code:
      return rootp;
    Also, you don't need TYPED_ALLOC. You're actually better off not casting malloc (read this FAQ article).
    paranoidgnu likes this.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. creating a binary search tree
    By krishpatel in forum C Programming
    Replies: 6
    Last Post: 12-23-2010, 10:53 PM
  2. creating a binary search tree
    By krishpatel in forum C Programming
    Replies: 1
    Last Post: 12-23-2010, 12:18 PM
  3. Replies: 0
    Last Post: 11-04-2006, 10:07 AM
  4. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 01:12 PM
  5. Search Engine - Binary Search Tree
    By Gecko2099 in forum C Programming
    Replies: 9
    Last Post: 04-17-2005, 02:56 PM

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