Witam.
Potrzebuję pilnie waszej pomocy. Musze przerobić poniższy program tak, by sam losował elementy drzewa, i mierzył czas operacji. Potrzebuje to koniecznie na jutro. Błagam, pomóżcie.
#include <iostream>
using namespace std;
// definicja typu danych reprezentującego węzeł drzewa BST
//--------------------------------------------------------
struct BSTNode
{
BSTNode * p, * left, * right;
int key;
// tutaj można umieszczać inne pola danych
};
// Definicja klasy obsługującej drzewo BST
//----------------------------------------
class BST
{
public:
BSTNode * root; // korzeń drzewa
int count; // liczba węzłów
BST();
~BST();
bool insert(BSTNode * n);
BSTNode * search(int key);
int maxKey(BSTNode * x);
int minKey(BSTNode * x);
BSTNode * maxNode(BSTNode * x);
BSTNode * minNode(BSTNode * x);
BSTNode * pred(BSTNode * x);
BSTNode * succ(BSTNode * x);
BSTNode * remove(BSTNode * x);
void preorder(BSTNode * x);
void inorder(BSTNode * x);
void postorder(BSTNode * x);
void walk(BSTNode * x);
void coutBSTcount();
};
// Konstruktor klasy BST
//----------------------
BST::BST()
{
root = NULL;
count = 0;
}
// Destruktor klasy BST
//---------------------
BST::~BST()
{
while(root) delete(remove(root));
}
// Wstawia element do struktury BST
//---------------------------------
bool BST::insert(BSTNode * n)
{
BSTNode * y, * x = root;
y = n->left = n->right = NULL;
while(x)
{
if(n->key == x->key)
{
delete n;
return false;
}
y = x;
x = (n->key < x->key) ? x->left : x->right;
}
n->p = y;
if(!y) root = n;
else if(n->key < y->key) y->left = n;
else y->right = n;
count++;
return true;
}
// Wyszukuje element wg wartości klucza
//-------------------------------------
BSTNode * BST::search(int key)
{
BSTNode * x = root;
while((x) && (x->key != key))
x = (key < x->key) ? x->left : x->right;
return x;
}
// Zwraca masymalną wartość klucza
//--------------------------------
int BST::minKey(BSTNode * x)
{
while(x->left) x = x->left;
return x->key;
}
// Zwraca minimalną wartość klucza
//--------------------------------
int BST::maxKey(BSTNode * x)
{
while(x->right) x = x->right;
return x->key;
}
// Zwraca węzeł z maksymalnym kluczem
//-----------------------------------
BSTNode * BST::minNode(BSTNode * x)
{
while(x->left) x = x->left;
return x;
}
// Zwraca węzeł z minimalnym kluczem
//----------------------------------
BSTNode * BST::maxNode(BSTNode * x)
{
while(x->right) x = x->right;
return x;
}
// Zwraca węzeł poprzednika
//-------------------------
BSTNode * BST::pred(BSTNode * x)
{
if(x->left) return maxNode(x->left);
BSTNode * y;
do
{
y = x;
x = x->p;
} while(x && (x->right != y));
return x;
}
// Zwraca węzeł następnika
//------------------------
BSTNode * BST::succ(BSTNode * x)
{
if(x->right) return minNode(x->right);
BSTNode * y;
do
{
y = x;
x = x->p;
} while(x && (x->left != y));
return x;
}
// Usuwa element x ze struktury BST. Zwraca usunięty węzeł
//--------------------------------------------------------
BSTNode * BST::remove(BSTNode * x)
{
BSTNode * y = x->p, * z;
if((x->left) && (x->right))
{
z = (rand() % 2) ? remove(pred(x)) : remove(succ(x));
z->left = x->left; if(z->left) z->left->p = z;
z->right = x->right; if(z->right) z->right->p = z;
count++;
}
else z = (x->left) ? x->left : x->right;
if(z) z->p = y;
if(!y) root = z;
else if(y->left == x) y->left = z; else y->right = z;
count--;
return x;
}
// Przechodzi przez BST metodą preorder
//-------------------------------------
void BST::preorder(BSTNode * x)
{
if(x)
{
cout << x->key << endl; // tutaj przetwarzamy bieżący węzeł
preorder(x->left);
preorder(x->right);
}
}
// Przechodzi przez BST metodą inorder
//------------------------------------
void BST::inorder(BSTNode * x)
{
if(x)
{
inorder(x->left);
cout << x->key << endl; // tutaj przetwarzamy bieżący węzeł
inorder(x->right);
}
}
// Przechodzi przez BST metodą postorder
//--------------------------------------
void BST::postorder(BSTNode * x)
{
if(x)
{
postorder(x->left);
postorder(x->right);
cout << x->key << endl; // tutaj przetwarzamy bieżący węzeł
}
}
// Przechodzi przez drzewo wypisując zawartość węzłów
//---------------------------------------------------
void BST::walk(BSTNode * 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);
}
// Wypisuje do cout liczbę węzłów drzewa BST
//------------------------------------------
void BST::coutBSTcount()
{
cout << "\nLiczba wezlow drzewa BST : " << count << endl << endl;
}
// **********************************
// *** Funkcje obsługi opcji menu ***
// **********************************
// Dodaje nowe węzły do drzewa BST
//--------------------------------
void add(BST * T)
{
cout << "Dodawanie nowych wezlow do drzewa BST\n"
"-------------------------------------\n\n";
T->coutBSTcount();
cout << "Podaj liczbe wezlow do utworzenia, a nastepnie wprowadz odpowiednia\n"
"liczbe kluczy nowych wezlow.\n\n";
int i,n;
BSTNode * x;
cin >> n;
for(i = 0; i < n; i++)
{
x = new BSTNode;
cin >> x->key;
T->insert(x);
}
cout << endl;
T->walk(T->root);
T->coutBSTcount();
}
// Usuwa węzeł o zadanym kluczu
//-----------------------------
void del(BST * T)
{
cout << "Usuwanie wezla drzewa BST o zadanym kluczu\n"
"------------------------------------------\n\n";
T->coutBSTcount();
BSTNode * x;
int key;
cout << "Podaj klucz usuwanego wezla : "; cin >> key;
x = T->search(key);
if(x)
{
delete T->remove(x);
cout << endl;
if(T->root) T->walk(T->root);
T->coutBSTcount();
}
else cout << "\nBrak wezla o takim kluczu\n";
}
// Sprawdza, czy drzewo zawiera węzeł o zadanym kluczu
//----------------------------------------------------
void check(BST * T)
{
cout << "Sprawdzenie obecnosci wezla o danym kluczu w drzewie BST\n"
"--------------------------------------------------------\n\n"
"Podaj klucz wezla : ";
int key;
cin >> key;
cout << endl;
if(T->search(key)) cout << "Wezel znaleziony.\n";
else cout << "W drzewie BST brak wezla o podanym kluczu\n";
}
// Znajduje minimalny i maksymalny klucz
//--------------------------------------
void minmax(BST * T)
{
cout << "Znajdowanie minimalnego i maksymalnego klucza w drzewie BST\n"
"-----------------------------------------------------------\n\n"
"Klucz minimalny : " << T->minKey(T->root) << endl <<
"Klucz maksymalny : " << T->maxKey(T->root) << endl;
}
// Znajduje poprzednik węzła o zadanym kluczu
//-------------------------------------------
void pred(BST * T)
{
cout << "Znajdowanie poprzednika w drzewie BST\n"
"-------------------------------------\n\n"
"Podaj klucz wezla : ";
int key;
BSTNode * x;
cin >> key;
cout << endl;
x = T->search(key);
if(x)
{
x = T->pred(x);
if(x) cout << "Poprzednikiem [" << key << "] jest " << x->key << endl;
else cout << "Wezel [" << key << "] nie posiada poprzednika\n";
}
else cout << "Wezel o podanym kluczu nie istnieje w drzewie BST\n";
}
// Znajduje następnik węzła o zadanym kluczu
//------------------------------------------
void succ(BST * T)
{
cout << "Znajdowanie nastepnika w drzewie BST\n"
"------------------------------------\n\n"
"Podaj klucz wezla : ";
int key;
BSTNode * x;
cin >> key;
cout << endl;
x = T->search(key);
if(x)
{
x = T->succ(x);
if(x) cout << "Nastepnikiem [" << key << "] jest " << x->key << endl;
else cout << "Wezel [" << key << "] nie posiada nastepnika\n";
}
else cout << "Wezel o podanym kluczu nie istnieje w drzewie BST\n";
}
// Przechodzi przez drzewo algorytmem preorder
//--------------------------------------------
void preorder(BST * T)
{
cout << "Przechodzenie drzewa BST algorytmem preorder\n"
"--------------------------------------------\n\n";
T->preorder(T->root);
}
// Przechodzi przez drzewo algorytmem inorder
//--------------------------------------------
void inorder(BST * T)
{
cout << "Przechodzenie drzewa BST algorytmem inorder\n"
"-------------------------------------------\n\n";
T->inorder(T->root);
}
// Przechodzi przez drzewo algorytmem postorder
//--------------------------------------------
void postorder(BST * T)
{
cout << "Przechodzenie drzewa BST algorytmem postorder\n"
"---------------------------------------------\n\n";
T->postorder(T->root);
}
main()
{
BST * T = new BST();
int choice;
do
{
system("cls"); // w Linuxie wstaw clear
cout << "Test funkcji obslugi drzew poszukiwan binarnych\n"
"===============================================\n\n"
"Wybor Funkcja\n"
"-------------\n"
" [0] Koniec\n"
" [1] Dodaj wezly\n"
" [2] Usun wezel\n"
" [3] Sprawdz obecnosc wezla\n"
" [4] Wezel min i max\n"
" [5] Poprzednik\n"
" [6] Nastepnik\n"
" [7] Preorder\n"
" [8] Inorder\n"
" [9] Postorder\n"
"--------------\n"
"Twoj wybor : ";
cin >> choice;
system("cls");
switch(choice)
{
case 1 : add(T); break;
case 2 : del(T); break;
case 3 : check(T); break;
case 4 : minmax(T); break;
case 5 : pred(T); break;
case 6 : succ(T); break;
case 7 : preorder(T); break;
case 8 : inorder(T); break;
case 9 : postorder(T); break;
}
if((choice >= 1) && (choice <= 9))
{
cout << endl;
system("pause");
}
} while(choice);
delete T;
}