Thread: Having a bit of trouble with a binary search program

  1. #1
    Registered User
    Join Date
    Apr 2006
    Posts
    10

    Having a bit of trouble with a binary search program

    My binary tree needs to do the following:

    1. Store any amount of positive integers.

    2. Delete any given entry in the binary search tree

    3. Print out the entries in the tree in ascending and descending order.

    4. Allow the tree to be searched such that if a number is input the two nearest numbers to it are found in the tree and output to the screen, if the input number exists in the tree only that is output.

    Now i have done task 1, 2, and part of 3. I can't fugure out how to make it print out the numbers in reverse order or how to do task 4. Any help on the subject is much appreciated. Here is my code.

    Code:
    #include <iostream.h>
    #include <cstring.h>
    #include <conio.h>
    #include <ctype.h>
    #include <fstream.h>
    
    
    // declare a tree node structure
    struct treenode {
          string data;
          treenode* left;
          treenode* right;
          };
    
    // create a new tree with an empty root node
    // pass back the root address
      treenode* initialise() {
      treenode *root = new treenode;
      root->data=" ";
      root->right=NULL;
      root->left=NULL;
      return root;
    }
    
    // used for the 'delete' routine
    ofstream file1;
    ifstream file2;
    
    // insert a new item, starting at the root
    void insert(treenode* root,string newitem) {
      treenode  *temp, *current;
      bool found;
      clrscr();
      current=root;
      found=false;
      while (!found) {
         if (newitem < current->data)// belongs to left of current
         {
           if (!(current->left))
              found=true;              //if left pointer is NULL add new item here
           else {
              current=current->left;
               }
          }
         else                      // otherwise belongs on right hand side
            if(!(current->right))
               found=true;         // if right pointer NULL add here
            else {
               current=current->right;  // look at right hand branch
               }
      }
      // now add a new node
      temp= new treenode;  // create node
      temp->data = newitem; // put data into it
      temp->right=NULL;
      temp->left=NULL;
      if (newitem < current->data)  // now add it on correct side of current
         current->left=temp;
      else
         current->right=temp;
    }
    
    
    // this is a recursive function
    // traverse in order
    void inorder(treenode* tree) {
       treenode  *leftsubtree, *rightsubtree;
       leftsubtree=tree->left;
       rightsubtree=tree->right;
       if (leftsubtree)    // i.e if not NULL (empty subtree)
          inorder(leftsubtree);  // recursive call
       cout<<tree->data<<endl;
       if (rightsubtree)   // i.e. if not NULL (empty subtree)
          inorder(rightsubtree); // recursive call
    }
    
    
    // also a recursive function
    void search(treenode* current, string item){
           if (!current)
              cout<<"not in the tree"<<endl;
            else {
            if (item==current->data)
                cout<<item<<"  is in the tree "<<endl;
            else
               {
                if (item<current->data)
                    search(current->left, item);
                else
                    search(current->right, item);
                    }
                 }
      }
    
    // delete a node containing a given item
    // traverse tree pre-order and write data to file, except for item to delete
    void preorder(treenode* tree, string item){
        treenode  *leftsubtree, *rightsubtree;
       leftsubtree=tree->left;
       rightsubtree=tree->right;
       if (tree->data!=item)
          file1<<tree->data<<" ";
       if (leftsubtree)    // i.e if not NULL (empty subtree)
          preorder(leftsubtree, item);  // recursive call
       if (rightsubtree)   // i.e. if not NULL (empty subtree)
          preorder(rightsubtree, item); // recursive call
       }
    
    // read file and insert data to build a new tree
    void writenewtree(treenode* root){
       string data;
       while (file2>>data)
         insert(root, data);
    }
    
     void main() {
      treenode* root;
      treenode* newroot;
      string prompt = "Traverse in order 1.  Search 2.  Delete node 3. Quit 0.";
      char choice;
      root= initialise();
      string item;
      // build the tree -------------------------------------
      cout<<"Data -Z to end: ";
      getline(cin, item);
      while (item!="Z") {
         if (root->data==" ")       // if the root is empty
            {
             root->data =item; // put the new item in the root
              }
         else                          
            insert(root,item);  // otherwise call insert function passing 'root'
            cout<<"Data Z to end: ";
            getline(cin, item);
         }
       // ----------------------------------------------------
       clrscr();
       cout<<endl<<prompt;
       cin>>choice;
       clrscr();
       while (toupper(choice)!='0'){
       switch (choice){
           case '1': cout<<"Traversing tree in order..."<<endl;
                     inorder(root);
                     break;
    
           case '2': cout<<"Search for an item? Z if none: ";
                     getline(cin, item);
                     while (item!="Z"){
                         clrscr();
                         search(root,item);
                         inorder(root);
                         cout<<"Search for an item? Z if none: ";
                         getline(cin, item);
                         }
                      break;
           case '3':  cout<<"Delete an item? Z if none: ";
                      getline(cin, item);
                      while (item!="Z"){
                          clrscr();
                          file1.open("tempfile");
                          preorder(root, item);
                          file1.close();
                          file2.open("tempfile");
                          newroot = initialise();
                          writenewtree(newroot);
                          file2.close();
                          cout<<"Existing tree..."<<endl;
                          inorder(root);
                          cout<<endl<<"New tree..."<<endl;
                          inorder(newroot);
                          root=newroot;
                          cout<<endl<<"Delete an item? Z if none: ";
                          getline(cin, item);
                          }
                          break;
                       }
       cout<<endl<<prompt;
       cin>>choice;
       clrscr();
       }
       PostQuitMessage(0);
       }

  2. #2
    Registered User
    Join Date
    Apr 2006
    Posts
    10
    Anyone?

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > void main()
    main returns an int.

    > root= initialise();
    A better empty tree would be
    root = NULL;

    This is made simpler if your insert function returns the new root (which is usually the old root, except when you create the first node).
    root = insert( root, data );


    When you first create your tree, you have this
    > if (root->data==" ")
    But later on, you don't.

    And in several other places, you don't have a "special" test either.

    > while (toupper(choice)!='0')
    toupper() and tolower() do not apply to the digits '0' to '9'

    > case '1':
    To save ballooning main() into some massive function, make each case a separate function
    Code:
    case '1': doSomething(); break;
    case '2': doAnotherThing(); break;
    > writenewtree(newroot);
    The most inaccurately named function I've seen in a long while.
    Sure you're writing a tree into memory, but the usual convention for 'read' and 'write' refers to the file end of the deal, not the memory end.

    > I can't fugure out how to make it print out the numbers in reverse order
    Well you already wrote inorder and preorder, how about postorder?
    Or maybe swap over the 'go left, then go right' decisions?

    > how to do task 4
    How about searchNearest(root,target,nearestLess, nearestGreater)
    It searches a tree, and updates the nearest pointers with the nodes which are closest to the target value.
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Recursive binary search program help.
    By mooney in forum C Programming
    Replies: 3
    Last Post: 04-04-2008, 01:12 AM
  2. help with c program: binary to ascii program
    By bigmac(rexdale) in forum C Programming
    Replies: 26
    Last Post: 02-03-2008, 02:26 PM
  3. Binary Search Tree Trouble
    By reelbigtim in forum C Programming
    Replies: 1
    Last Post: 11-18-2007, 03:23 AM
  4. Replies: 4
    Last Post: 08-24-2007, 05:28 PM
  5. Using variables in system()
    By Afro in forum C Programming
    Replies: 8
    Last Post: 07-03-2007, 12:27 PM