Need help with BST Program

This is a discussion on Need help with BST Program within the C Programming forums, part of the General Programming Boards category; Thanks Salem, its working. I'm making some modifications in the program to make it work my way. If I have ...

  1. #16
    Registered User
    Join Date
    May 2012
    Location
    India
    Posts
    32
    Thanks Salem, its working. I'm making some modifications in the program to make it work my way. If I have any issues, I'll get back.

    Thanks again.

  2. #17
    Registered User
    Join Date
    May 2012
    Location
    India
    Posts
    32
    Hello, I've completed my program but there seems to be some minor issue which I've been trying hard to figure out. Here's the code:

    Code:
    #include<stdio.h>
    #include<conio.h>
    #include<stdlib.h>
    typedef struct node
    {
            int data;
            struct node *left;
            struct node *right;
    }NODE;
    typedef struct
    {
            int count;
            NODE *root;
    }TREE;
    TREE *createTree(void)
    {
         TREE *tree;
         tree = (TREE *)malloc(sizeof(TREE));
         if(tree)
         {
                 tree->count = 0;
                 tree->root = NULL;
         }
         return tree;
         
    }
    NODE *addNode(TREE *tree, NODE *node, int dataIn)
    {
         if(node == NULL)
         {
                 NODE *newNode;
                 newNode = (NODE *)malloc(sizeof(NODE));
                 if(newNode)
                 {
                            newNode->data = dataIn;
                            newNode->left = NULL;
                            newNode->right = NULL;
                            node = newNode;
                            (tree->count)++;
                 }
         }
         else
         {
             if(dataIn < node->data)
             {
                       node->left = addNode(tree, node->left, dataIn);
                       return node;
             }
             else
             {
                 node->right = addNode(tree, node->right, dataIn);
                 return node;
             }
         }
         return node;
    }
    void inOrder(NODE *node)
    {
         if(node != NULL)
         {
                 inOrder(node->left);
                 printf("%d\t", node->data);
                 inOrder(node->right);
         }
    }
    void preOrder(NODE *node)
    {
         if(node != NULL)
         {
                 printf("%d\t", node->data);
                 preOrder(node->left);
                 preOrder(node->right);
         }
    }
    void postOrder(NODE *node)
    {
         if(node != NULL)
         {
                 postOrder(node->left);
                 postOrder(node->right);
                 printf("%d\t", node->data);
                 
         }
    }
    int findNode(NODE *node, int findData)
    {
        if(node == NULL)
                return 0;
        if(findData == node->data)
                    return 1;
        else if(findData < node->data)
             findNode(node->left, findData);
        else
            findNode(node->right, findData);
    }
    NODE *findNewRoot(TREE *tree, NODE *node, int delData, int *success)
    {
         NODE *dltPtr;
         NODE *exchPtr;
         NODE *newRoot;
         int temp;
         if(!node)
         {
                  *success = 0;
                  return NULL;
         }
         if(delData < node->data)
                    node->left = findNewRoot(tree, node->left, delData, success);
         else if(delData > node->data)
                         node->right = findNewRoot(tree, node->right, delData, success);
         else
         {
             dltPtr = node;
             if(!node->left)
             {
                            newRoot = node->right;
                            free(dltPtr);
                            *success = 1;
                            return newRoot;
             }
             else if(!node->right)
             {
                  newRoot = node->left;
                  free(dltPtr);
                  *success = 1;
                  return newRoot;
             }
             else
             {
                 exchPtr = node->left;
                 while(exchPtr)
                               exchPtr = exchPtr->right;
                 temp = node->data;
                 node->data = exchPtr->data;
                 exchPtr->data = temp;
                 node->left = findNewRoot(tree, node->left, exchPtr->data, success);
             }
         }
         return node;
    }
                               
    int main(void)
    {
        TREE *tree;
        tree = createTree();
        int value;
        while(1)
        {
                printf("\n1. Insert");
                printf("\n2. Delete");
                printf("\n3. Find");
                printf("\n4. InOrder");
                printf("\n5. PreOrder");
                printf("\n6. PostOrder");
                printf("\nChoice: ");
                scanf("%d", &value);
                if(value == 1)
                {
                         int data;
                         printf("\nEnter data to be inserted: ");
                         scanf("%d", &data);
                         tree->root = addNode(tree, tree->root, data);
                }
                else if(value == 2)
                {
                     int delData;
                     printf("\nEnter node to be deleted: ");
                     scanf("%d", &delData);
                     if(findNode(tree->root, delData) == 1)
                     {
                                  int success;
                                  NODE *newRoot;
                                  newRoot = findNewRoot(tree, tree->root, delData, &success);
                                  if(success == 1)
                                  {
                                             tree->root = newRoot;
                                             (tree->count)--;
                                             if(tree->count == 0)
                                                            tree->root = NULL;
                                             printf("\n\nNode deleted successfully. . .");
                                  }
                                  else
                                  {
                                      printf("\n\nNode not deleted. . .");
                                  }
                     }
                     else
                     {
                         printf("\n\nNode %d not found. . .", delData);
                     }
                }
                else if(value == 3)
                {
                     int findData;
                     printf("\nEnter value to be found: ");
                     scanf("%d", &findData);
                     if(findNode(tree->root, findData) == 1)
                     {
                                   printf("\n\nNode %d found\n\n", findData);
                     }
                     else
                     {
                                   printf("\n\nNode %d not found\n\n", findData);
                     }
                }
              else if(value == 4)
              {
                   printf("\n\n");
                   printf("---------------InOrder Traversal--------------\n\n");
                   inOrder(tree->root);
                   printf("\n\n");
                   printf("-----------------------------------------------\n");
              }
              else if(value == 5)
              {
                   printf("\n\n");
                   printf("---------------PreOrder Traversal--------------\n\n");
                   preOrder(tree->root);
                   printf("\n\n");
                   printf("-----------------------------------------------\n");
              }
              else if(value == 6)
              {
                   printf("\n\n");
                   printf("---------------PostOrder Traversal--------------\n\n");
                   postOrder(tree->root);
                   printf("\n\n");
                   printf("-----------------------------------------------\n");
              }
              else
                  exit(1);
        }
        getch();
        return 0;
    }
    After using option 1 to insert three nodes - "20", "10" and "30" when I try to find "10" using option 3, it says "Node 10 not found" even though the node is present. Even the print options show that the node is present.

    I did a little debug and figured out that findNode() function does return a 1, but the if condition doesn't catch it. What could be the issue?

  3. #18
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,439
    Your recursive calls of findnode don't return anything.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #19
    Registered User
    Join Date
    May 2012
    Location
    India
    Posts
    32
    Quote Originally Posted by Salem View Post
    Your recursive calls of findnode don't return anything.
    Thanks Salem, for your reply. I couldn't find out how to do it the recursive way, hence I tried the iteration method and now it seems to work fine. Here's the updated code of findNode().

    Code:
    int findNode(NODE *node, int findData)
    {
        while(node != NULL)
        {
                   if(findData == node->data)
                               return 1;
                   else if(findData < node->data)
                                    node = node->left;
                   else if(findData > node->data)
                                    node = node->right;
        }
        return 0;
                                    
    }

  5. #20
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,439
    We did all this 2 weeks ago with insertNode, and you were either not returning a result, or just ignoring the result.

    Oh well,
    Code:
    int findNode(NODE *node, int findData)
    {
        if(node == NULL)
                return 0;
        if(findData == node->data)
                    return 1;
        else if(findData < node->data)
             return findNode(node->left, findData);
        else
            return findNode(node->right, findData);
    }
    Were you by any chance getting any warnings from your compiler.
    Say for example "not all return paths return a result"?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  6. #21
    Registered User
    Join Date
    May 2012
    Location
    India
    Posts
    32
    Salem: Thanks for the suggestion on the recursive code. Honestly am a bit weak with recursion, hence I chose the iterative method.

    The code that I posted earlier, did not give me any warnings like the one you mentioned.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help converting array program to link list program
    By hsmith1976 in forum C++ Programming
    Replies: 0
    Last Post: 02-14-2010, 08:50 PM
  2. Replies: 1
    Last Post: 03-03-2009, 03:47 PM
  3. Replies: 5
    Last Post: 08-16-2007, 11:43 PM
  4. Replies: 18
    Last Post: 11-13-2006, 12:11 PM
  5. How To Make The Program Installed In Program Files Folder?
    By javacvb in forum Windows Programming
    Replies: 4
    Last Post: 11-05-2003, 04:33 PM

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