-
BST (Binary search tree)
Hi guys, I did this program, its BST, its a homework, but I got some error, could anyone look at it? thx a lot
What’s wrong:
- I compiled program, then I did press 0 (inicialization), then 1 (insert data)
- I put some data there (that’s fine)
- I tried preorder, inorder and postorder traversal and it’s writing, Bin. tree is empty! + data
- (for example: Data: 23, 45, 56, 78, 90)
Preorder traversal:
23
Bin. tree is empty!
45
Bin. tree is empty!
56
Bin. tree is empty!
78
Bin. tree is empty!
90
Bin. tree is empty!
Bin. tree is empty!
I tried delete node even whole tree, but there are some errors!!
-
-
Code:
#include "iostream"
#include "stdio.h"
#include "conio.h"
#include "malloc.h"
#include "process.h"
#include "stdlib.h"
#include "string.h"
using namespace std;
typedef int tStr;
struct uzel{
int item;
struct uzel *right;
struct uzel *left;
};
typedef struct uzel *BST;
typedef struct uzel uzel;
bool Empty(BST t){
if(t!=NULL){
return false;
}
else return true;
}
BST Initialize(BST t){
t=NULL;
return t;
}
BST DeleteTree(BST t){
if(t!=NULL) {
DeleteTree(t->left);
DeleteTree(t->right);
free(t);
}
else {
cout<<"Bin. tree is empty !"<<endl;
}
return NULL;
}
BST Search(BST t, int x){
if(t==NULL){
cout<<"Bin. tree is empty!"<<endl;
return NULL;
}
if(x < t->item){
return Search(t->left,x);
}
else{
if(x > t->item){
return Search(t->right,x);
}
else return t;
}
}
BST Insert(BST t, int x){
if(t==NULL) {
t=(struct uzel*) malloc(sizeof(struct uzel));
t->item = x;
t->left = t->right = NULL;
return t;
}
if(t->item >= x) {
t->left = Insert(t->left, x);
return t;
}
else{
t->right = Insert(t->right,x);
return t;
}
}
BST findmin(BST t){
if(t == NULL){
return NULL;
}
else{
if(t->left == NULL){
return t;
}
else{
return findmin(t->left);
}
}
}
BST findmax(BST t){
if(t==NULL){
return NULL;
}
else{
if(t->right == NULL){
return t;
}
else{
return findmax(t->right);
}
}
}
BST Delete(BST t, int x){
BST tmpCell;
if(t == NULL){
cout<<"Cannot delete, bin. tree is empty !"<<endl;
return NULL;
}
else{
if(x < t->item){
t->left = Delete(t->left,x);
}
else{
if(x > t->item){
t->right = Delete(t->right,x);
}
else{
if(t->right && t->left){
tmpCell = findmin(t->right);
t->item= tmpCell->item;
t->right = Delete(t->right, tmpCell->item);
}
else{
tmpCell = t;
if(t->left == NULL){
t = t->right;
}
else if(t->right == NULL){
t = t->left;
}
}
}
}
free(tmpCell);
cout<<"Value was deleted."<<endl;
}
return t;
}
void Preorder(BST t){
if (t!=NULL){
cout<<t->item<<endl;
Preorder(t->left);
Preorder(t->right);
}
else{
cout<<"Bin. tree is empty !"<<endl;
}
}
void Inorder(BST t){
if (t!=NULL){
Inorder(t->left);
cout<< t->item <<endl;
Inorder(t->right);
}
else{
cout<<"Bin. tree is empty !"<<endl;
}
}
void Postorder(BST t){
if (t!=NULL){
Postorder(t->left);
Postorder(t->right);
cout<<t->item<<endl;
}
else{
cout<<"Bin tree is empty !"<<endl;
}
}
tStr getData(void){
cout << "Get data: ";
tStr data;
cin >> data;
return data;
}
/*
void Vy........eznam(BST t){
tStr data;
cout << "Obsah seznamu:";
if (Empty(t)==true){
cout<<" NULL"<<endl;
}
else{
data = t->item;
cout << data << ", ";
}
}
*/
void Menu(void)//vypis menu
{
cout << "\nGet number 0-7: \n\n";
cout << "0: Inicialize\n";
cout << "1: Insert\n";
cout << "2: Search\n";
cout << "3: Preorder\n";
cout << "4: Inorder\n";
cout << "5: Postorder\n";
cout << "6: Delete\n";
cout << "7: Delete tree\n";
cout << "M: Menu\n";
cout << "E: End\n";
}
int main(){
Menu();
char znak;
BST strom;
//tStr data;
do {
cout << "\n\nGet char!";
cin >> znak;
switch (toupper(znak)) {
case '0' : cout << "Inicialize - Initialization\n";
strom = Initialize(strom);
//Vy........eznam(strom);
break;
case '1' : cout << "Insert - insert a new node\n";
strom = Insert(strom, getData());
//Vy........eznam(strom);
break;
case '2' : cout << "Search - search node\n";
Search(strom, getData());
cout<<strom<<endl;
break;
case '3' : cout << "Preorder - preorder traversal\n";
Preorder(strom);
break;
case '4' : cout << "Inorder - inorder traversal\n";
Inorder(strom);
break;
case '5' : cout << "Postorder - postorder traversal\n";
Postorder(strom);
break;
case '6' : cout << "Delete - delete node\n";
Delete(strom, getData());
break;
case '7' : cout << "Delete Tree - delete tree\n";
DeleteTree(strom);
break;
case 'M' : Menu();
break;
case 'E' :
break;
default : cout << "You get a wrong char!!!\n";
}
} while (toupper(znak) != 'E');
return 0;
}
-
>but I got some error
That's no an error, it's exactly what you told the program to do? If you're not at a leaf, you recurse. If you are at a leaf, print a message saying that the tree is empty. Here's what your tree looks like for Data: 23, 45, 56, 78, 90:
Code:
23
\
45
\
56
\
78
\
90
Ignoring the fact that this is an awful tree, there are 6 leaves, one to the left of 23, 45, 56, and 78, and two to the left and right of 90. Now consider how your preorder traversal works and look at your output again. Does it coincide with the structure of the tree?
Code:
23
Bin. tree is empty!
45
Bin. tree is empty!
56
Bin. tree is empty!
78
Bin. tree is empty!
90
Bin. tree is empty!
Bin. tree is empty!
How about if we replace the message with ~, and format the result like a tree?
Code:
23
/ \
~ 45
/ \
~ 56
/ \
~ 78
/ \
~ 90
/ \
~ ~
There's nothing wrong with the code, only your expectations of what it should be doing. It seems like you want to print a message saying that the tree is empty only if the entire tree is empty, so you would do this:
Code:
void preorder_r ( BST t )
{
if ( t != NULL ) {
cout<< t->data <<'\n';
preorder ( t->left );
preorder ( t->right );
}
}
void preorder ( BST t )
{
if ( t != NULL )
preorder_r ( t );
else
cout<<"Tree is empty\n";
}
And now for a few comments on your code.
>#include "iostream"
It's customary to wrap standard headers in angle brackets and non-standard headers in double quotes. So you should be using <iostream>, not "iostream".
>typedef int tStr;
This is about the worst typedef I've ever seen. You're making a synonym for an integer that suggests a string, which is amazingly confusing.
>typedef struct uzel *BST;
Never hide a level of indirection with a typedef. It's confusing to readers.
>typedef struct uzel uzel;
You're probably coming from C. C++ does this behind the scenes for you, so there's no need to do it manually.
Code:
BST Initialize(BST t){
t=NULL;
return t;
}
There's no point assigning to t, just return NULL.
