SDiZO, lab3 Drzewo BST

gistfile1.c

#include<iostream>
#include <time.h>
using namespace std;
struct tree{
    int key;
    tree *left, *right;
};
tree *root;
 
class Binary_tree{
    public:
        Binary_tree();
        void insert1(int);
        tree *insert2(tree *, tree *);
        void delete_tree(int);
        void inorder(tree *);
        void walk(tree *);
        void posttrav(tree *);
        static int ii;
};

Binary_tree bt;

int Binary_tree::ii = 1;

Binary_tree::Binary_tree()
{
root = NULL;
}

tree * Binary_tree::insert2(tree *temp, tree *newnode)
{
    if(temp == NULL) {
        temp = newnode;
    } 
    else if(temp->key == newnode->key) {
        return temp;
    }
    else if(temp->key < newnode->key) {
        insert2(temp->right, newnode);
        if(temp->right == NULL) {            
             ii++;
            temp->right = newnode;
        }
    } else {
        insert2(temp->left, newnode);
        if(temp->left == NULL) {
            ii++;
            temp->left = newnode;
        }
    }    
    return temp;
}

void Binary_tree::delete_tree(int key)
{
    tree *temp = root,*parent = root, *marker;
    if(temp == NULL)
        cout<<"The tree is empty"<<endl;
    else {
        while(temp != NULL && temp->key != key) {
            parent = temp;
            if(temp->key < key) {
                temp = temp->right;
            } else {
                temp = temp->left;
            }
        }
    }
    
    marker = temp;
    
    if(temp == NULL)
        cout<<"Brak wezla";
    
    else if(temp == root) {
        if(temp->right == NULL && temp->left == NULL) {
            root = NULL;
        } else if(temp->left==NULL) {
            root = temp->right;
        } else if(temp->right == NULL) {
            root = temp->left;
        } else {
            tree *temp1;
            temp1 = temp->right;
            while(temp1->left != NULL) {
                temp = temp1;
                temp1 = temp1->left;
            } if(temp1 != temp->right) {
                temp->left = temp1->right;
                temp1->right = root->right;
            }
            temp1->left = root->left;
            root = temp1;
        }
    } else {
        if(temp->right == NULL && temp->left == NULL){
            if(parent->right == temp)
                parent->right = NULL;
            else
                parent->left = NULL;
        }
        else if(temp->left == NULL){
            if(parent->right == temp)
                parent->right = temp->right;
            else
                parent->left = temp->right;
        }
        else if(temp->right == NULL){
            if(parent->right == temp)
                parent->right = temp->left;
            else
                parent->left = temp->left;
        } else {
            tree *temp1;
            parent = temp;
            temp1 = temp->right;
            while(temp1->left != NULL){
                parent = temp1;
                temp1 = temp1->left;
            }
            if(temp1 != temp->right){
                temp->left = temp1->right;
                temp1->right = parent->right;
            }
            temp1->left = parent->left;
            parent = temp1;
        }
    }
    delete marker;
}

void Binary_tree::insert1(int n)
{
    tree *temp = root, *newnode;
    newnode = new tree;
    newnode->left = NULL;
    newnode->right = NULL;
    newnode->key = n;
    root = insert2(temp, newnode);
}

void Binary_tree::walk(tree * x)
{
  cout << x->key << " : Left-> ";
  if(x->left) 
      cout << x->left->key;
  else        
      cout << "NIL";
  cout << ", Right-> ";
  if(x->right) 
      cout << x->right->key;
  else         
      cout << "NIL";
  cout << endl;
  if(x->left)  
      walk(x->left);
  if(x->right) 
      walk(x->right);
}

void Binary_tree::inorder(tree *t)
{
    if(root == NULL) {
        cout << "Drzewo puste!\n";
    } else {
        if(t != NULL) {
            inorder(t->left);
            cout << t->key << " ";
            inorder(t->right);
        }
    }
}

void insert3(int n)
{
    
    for(int i = 0; i < n; i = Binary_tree::ii) {
        int z = rand() % 200;
        bt.insert1(z);
    }
}

int main()
{
    srand(time(NULL));
    int choice, n, key, z;
    while(z){
        cout << "\n1. Dodaj jeden wezel \n2. Dodaj losowe \n3. Inorder "
                "\n4. Usun \n5. Walk \n6. Wyjscie\n";        
        cin >> choice;
        switch(choice){
            case 1:
                cout << "Dodaj element: ";
                cin >> n;
                bt.insert1(n);
                break;
            case 2:
                cout<<"Ile elementow: ";
                cin >> n;
                insert3(n);
                break;
            case 3:
                cout << endl;
                bt.inorder(root);
                break;
            case 4:
                cout<<endl;
                cout <<"Jaki element chcesz usunac?: ";
                cin >> n;
                bt.delete_tree(n);
                break;
            case 5:
                cout << endl;
                bt.walk(root);
                break;
            case 6:
                z = 0;
        }
    }
}