Join 136,154 C++ Programmers for FREE! Get instant access to thousands of C++ experts, tutorials, code snippets, and more! There are 2,126 people online right now. Registration is fast and FREE... Join Now!
It is a binary search tree project I am working on for a while. The only problem that got me stuck is the root (1st item inserted) will not be display and crashed the search function.
any help would be greatly apprectiated, tomorrow friday is the deadline.
header file:
CODE
typedef int itemType;
class tree { private: struct TNode { itemType item; TNode *lchild; TNode *rchild; };
int size;
TNode *root; TNode *p; TNode *q;
public:
tree(); // constructor
bool isEmpty() const; //goal:test whether tree is empty //pre:none //post:return true if tree is empty else return false
bool isFull() const; //goal:test whether tree is full //pre:none //post:return true if tree is full else return false
Cutting it a bit close with the deadline are we? Luckily DIC is here to help you out! The problem you are having is how you insert your nodes. I am not sure why, but you checked if the tree is empty and attempted to add your node to root. You passed root to the function as "p" so enter it as p!
CODE
void tree::insert(TNode *&p, itemType newItem) { if(isEmpty() || p == NULL) { // Here we create a node and assign it to p, the pointer we passed into the function. p = new TNode; p->item = newItem; p->lchild = NULL; p->rchild = NULL; size++; } else if (newItem < p->item) { insert(p->lchild, newItem); } else { insert(p->rchild, newItem); }
}
The second thing I noticed was that you put your structure of TNode inside your definition of Tree and then when you created *root you attempted to access it using tree::TNode. Problem with this is that it was set as private. Either make it public or move it outside the class of tree and define your root pointer as...
CODE
struct TNode *root;
Personally I would move it outside of your tree class since a node is a structure which can stand on its own and be used in various things other than a tree (like a linkedlist, queue, stack etc). I consider it on its own as an acceptable implementation that will allow other programmers to use your TNode structure to enhance your program later.
After you make these subtle changes, you will notice root is being entered and your search will come online and detect the root in your search.
Hopefully that gets you to the point of near completion for Friday.
that was so kind of you, Martyr2 a hundred thank you to Martyr2 of released me out of bond.
If you have time, would you mind to check the java section and take a look at world clock project that I am having trouble with adding radiobutton. The purpose of the radiobutton is to provide optional time zone for user to play around with.
Wow, there's a whole lot of recursion going on there.
In main, the line struct tree::TNode *root; strikes me as odd. You made the struct private, how can you even do this? In any case, you shouldn't have nodes getting passed around in public. I'm using your tree to store my data, I shouldn't need to know anything about the structure of the storage to use it.
While you're recursing, you can probably simplify your code by never checking isEmpty again. You're starting at a node, you don't really need to check beyond the is null.
Now the problem I am facing is that the search function will crashed the program after an interger is inserted. If the search does not match the interger that was stored, the program will crashed.
thanks for pointing out the private root issue. I moved it to public now.
here's my code again
header:
CODE
typedef int itemType;
class tree { private: struct TNode { itemType item; TNode *lchild; TNode *rchild; }; int size; TNode *p; TNode *q;
public:
tree(); //constructor
bool isEmpty() const; //goal:test whether tree is empty //pre:none //post:return true if tree is empty else return false
bool isFull() const; //goal:test whether tree is full //pre:none //post:return true if tree is full else return false
int getSize(); //goal:get the size of tree if is not empty //pre:tree exists //post:return tree size
void preorder(TNode *&p); //goal:display tree in preoder //pre:tree exists //post:if tree is not empty
void inorder(TNode *&p); //goal:display tree in inorder //pre:tree exists //post:if tree is not empty
void postorder(TNode *&p); //goal:display tree in postorder //pre:tree exists //post:if tree is not empty
struct TNode *root; };
implementation
CODE
/*************************************************** data struc 8 binary search tree visual c++ Wei Chan Lee 11/23/07 ****************************************************/
#include "tree.h" #include <iostream> using namespace std;
/*************************************************** data struc 8 binary search tree visual c++ Wei Chan Lee 11/23/07 ****************************************************/
#include "tree.h" #include <conio.h> #include <iostream> using namespace std;
int main() { itemType anItem; int option; struct tree::TNode *root; root = NULL;
tree runtree;
// user menu
do{ cout << "\n Binary Search Tree"; cout << "\n 1.Insert Item"; cout << "\n 2.Search Item"; cout << "\n 3.Tree Size"; cout << "\n 4.Display Tree In Preorder"; cout << "\n 5.Display Tree In Inorder"; cout << "\n 6.Display Tree In Postorder"; cout << "\n 7.Exit" << endl;
cin >> option;
switch(option) { case 1: // Insert Item cout << "\nEnter an integer: "; cin >> anItem; runtree.insert(root,anItem); break; //end case 1
case 2: // Search Item cout << "\nEnter an integer: "; cin >> anItem; if(runtree.search(root, anItem) == anItem) { cout << runtree.search(root, anItem) << " founded in tree!!" << endl; } else { cout << anItem << " is not in tree " << endl; } break; //end case 2
case 3: // Check Size cout << "\nThe tree size is " << runtree.getSize() << "." << endl; break; //end case 3
case 4: // Display Preorder cout << endl; runtree.preorder(root); cout << endl; break; //end case 4
case 5: // Display Inorder cout << endl; runtree.inorder(root); cout << endl; break; //end case 5
case 6: // Display Postorder cout << endl; runtree.postorder(root); cout << endl; break; //end case 6 } }while(option != 7); // Exit Program
getch();
return 0; }
Thank you for your effort and concern of helping me.
6 Dec, 2007 - 09:30 AM
| 