Binary Search Tree Help!

[timb89]

Im trying to insert items into a BST from a txt file.

For arguments sake the data file is just the integers 1 2 3 4 5 6 7 8 9.

When i try to do a inorder traversal, all that is outputting is the first and last number.

I think the problem is with the creating the BST though i'm not sure what it is?

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

struct BST
{
    int data;
    BST *left;
    BST *right;
};

void menu(); //Displays menu options.

void buildBST(BST *& tree);

void printInorder(BST * p);

BST * tree = new BST;

int main()
{
    cout << " Binary Search Tree Balancing and Drawing" << endl;

    menu();
   
    system("PAUSE");
    return EXIT_SUCCESS;
}

void menu()
{
    int choice;

    cout << "\tMenu" << endl;
    cout << " 1.  Build new binary search tree" << endl;
    cout << " 2.  Display inorder traversal" << endl;
    cout << " 3.  Save tree (as preorder traversal)" << endl;
    cout << " 4.  Balance tree" << endl;
    cout << " 5.  Draw tree" << endl;
    cout << " 6.  Quit" << endl;
    
    cout << " Choice ? ";
    cin >> choice;
    
    switch (choice)
    {
         case 1:
              buildBST(tree);                    
              break;
         case 2:
              printInorder(tree);
              break;
         case 3:
              break;
         case 4:
              break;
         case 5:
              
              break;
         case 6:
              
              break;
    }
}

void buildBST(BST *& tree)
{     
    int array [100];
    int index = 0;
    int output;
    int number;   //To store a[i] in.
    tree = NULL;  //To ensure the tree is built fresh.
    
    ifstream infile;
    string fileName;
    
    cout << "Please enter name of data file" << endl;
         cin >> fileName;
    
    infile.open(fileName.c_str());
    
    if (!infile)
    {
         cout << "Cannot find " << fileName << endl;
         cout << endl;
         menu();
    }  
    
    if (infile.is_open()) 
    {
         while (!infile.eof()) 
         {
              infile >> output;
              array[index];
              index++;
              
              BST * t = new BST;
              t -> data = output;
              t -> left = NULL;
              t -> right = NULL;
              
              if (tree == NULL) 
              {
                   tree = t;
                   cout << "NULL = " << t -> data << endl;
              }
              
              else if (output < tree -> data) 
              {
                   tree -> left = t;                   
                   cout << "LEFT = " << t -> data << endl;                   
              }
              
              else // (output > tree -> data)
              {
                   tree -> right = t;                  
                   cout << "RIGHT = " << t -> data << endl;   
              }     
         }
    } 
    
    cout << endl;
    menu();
}

void printInorder(BST * tree)
{
    if (tree != NULL) 
    {
        printInorder (tree -> left);  // print left subtree
        cout << tree -> data << endl; // print this node
        printInorder (tree -> right); // print right subtree
    }
}

[Narue]

You're essentially using a recursive algorithm without the recursion. Might I suggest this tutorial?

[timb89]

why do i need recursion if it is adding the element one at a time from the txt file?

[Narue]

Perhaps if you split up the file reading code and the tree insertion code, you'll see the problem. I really do suggest you read the tutorial I linked to, because you clearly don't understand the logic of inserting into a binary search tree. There's a loop involved there too. Presently the only loop you're using is reading items from the file.

[vidit_X]

Hint : You are adding elements to tree's root only.

And what's the purpose of line 97.

array[index];

[Valaraukar]

Look here

else if (output < tree -> data) 
{
    tree -> left = t;                   
    cout << "LEFT = " << t -> data << endl;                   
}

You are assigning to tree (you root node)......but that's all you ever do. You never move on to the next node.

Perhaps if you imagine that each node could have only one 'child'. You assign tree his/her child but don't ever assign the child a child. Instead, because each node (in this example) can only have one child, you have to replace tree's first child with the next one that you acquire (using the data from your file). The previous child is now lost.
This happens recursively until you reach the end of your file by which time you are left with your first piece of data (stored in tree) and the data stored by the last child assigned to tree (the last piece of file data).

[timb89]

ok i think i see the problem now, whats the best way to convert this code? i just tried adding a recursive function into the while loop but it just crashed...

the array was becuase i was originally storing the text file in there to make sure it worked.