Program drzewa wyszukiwań binarnych

Question

#include <iostream>
#include <cstdlib>
#include <time.h>
#include <string>
 
using namespace std;
 
#include<iostream>
 
using namespace std;
 
class BST
{
    struct node
    {
        int data;
        node* left;
        node* right;
    };
 
    node* root;
 
    node* makeEmpty(node* t)
    {
        if(t == NULL)
            return NULL;
        {
            makeEmpty(t->left);
            makeEmpty(t->right);
            delete t;
        }
        return NULL;
    }
 
     node* insert(int x, node* t)
    {
        if(t == NULL)
        {
            t = new node;
            t->data = x;
            t->left = t->right = NULL;
        }
        else if(x < t->data)
            t->left = insert(x, t->left);
        else if(x > t->data)
            t->right = insert(x, t->right);
        return t;
    }
 
     node* findMin(node* t)
    {
        if(t == NULL)
            return NULL;
        else if(t->left == NULL)
            return t;
        else
            return findMin(t->left);
    }
 
     node* findMax(node* t)
    {
        if(t == NULL)
            return NULL;
        else if(t->right == NULL)
            return t;
        else
            return findMax(t->right);
    }

    node* remove(int x, node* t)
    {
        node* temp;
        if(t == NULL)
            return NULL;
        else if(x < t->data)
            t->left = remove(x, t->left);
        else if(x > t->data)
            t->right = remove(x, t->right);
        else if(t->left && t->right)
        {
            temp = findMin(t->right);
            t->data = temp->data;
            t->right = remove(t->data, t->right);
        }
        else
        {
            temp = t;
            if(t->left == NULL)
                t = t->right;
            else if(t->right == NULL)
                t = t->left;
            delete temp;
        }
 
        return t;
    }
 
    void inorder(node* t)
    {
        if(t == NULL)
            return;
        inorder(t->left);
        cout << t->data << " ";
        inorder(t->right);
    }
 
    node* find(node* t, int x)
    {
        if(t == NULL)
            return NULL;
        else if(x < t->data)
            return find(t->left, x);
        else if(x > t->data)
            return find(t->right, x);
        else
            return t;
    }
 
public:
    BST()
    {
        root = NULL;
    }
 
    ~BST()
    {
        root = makeEmpty(root);
    }
 
    void insert(int x)
    {
        root = insert(x, root);
    }
 
    void remove(int x)
    {
        root = remove(x, root);
    }
 
    void display()
    {
        inorder(root);
        cout << endl;
    }
 
    void search(int x)
    {
        root = find(root, x);
        cout << root->data << endl;
    }
};
 
int main()
{
BST k;
int tab[100000];
srand(time(0));
for(int i=0;i<1000000;i++) 
{
    tab[i]=rand()%10000000+1;
    cout<< tab[i]<<"\n\n";
 }
 k.insert(1000000);
getchar();
return 0;
 
}

Ktoś poprawilby ten kod i dokończył wykonanie zadania? Wiecej szczegółow na priv.

Comments

Co to ma znaczyć ktoś poprawiłby kod i dokończył zadanie? :D Jak masz z czymś problem to go nakreśl powiedz co dokładnie nie działa, a nie oczekuj, że ktoś będzie robił Twoje zadania ;)

Answer 1

Nie jestem pewna czy metoda insert działa poprawnie.

Porównaj czasy operacji wstawiania, usuwania, znajdowania minimalnego elementu, wyszukiwania losowego elementu dla: nieposortowanej tablicy, posortowanej tablicy i drzewa poszukiwań binarnych.  Nie wiem jak to sprawdzić kompletnie :/