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;
}