000
13.11.2005, 11:33 Uhr
~Petr
Gast
|
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!!
| C++: |
#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 VypisSeznam(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);
//VypisSeznam(strom);
break;
case '1' : cout << "Insert - insert a new node\n";
strom = Insert(strom, getData());
//VypisSeznam(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;
}
|
Dieser Post wurde am 13.11.2005 um 12:33 Uhr von Uwe editiert. |
