#include <iostream>
using namespace std;
struct wezel
{
wezel * p, * left, * right;
int key;
};
class BST
{
public:
wezel *root; // korzeń drzewa
int count; //l. wezlow
BST();
~BST();
int max(wezel * x);
int mini(wezel * x);
void preorder(wezel * x);
void inorder(wezel * x);
void postorder(wezel * x);
wezel*find(wezel * n, int wartosc);
void remove(wezel*& root, int k);
void add(int n,wezel *start);
wezel * maxWezel(wezel * x);
wezel * minWezel(wezel * x);
wezel * BST::pred(wezel * x);
void build(int tab[], const unsigned int size);
};
BST::BST()
{
root = NULL;
count = 0;
}
wezel*BST::find(wezel * n, int wartosc)
{
if (n->key == wartosc)
{
return n;
}
else if (wartosc < n->key && n->left != NULL)
{
return find(n->left, wartosc);
}
else if (wartosc > n->key && n->right != NULL)
{
return find(n->right, wartosc);
}
return NULL;
}
int BST::mini(wezel * x)
{
while(x->left) x = x->left;
return x->key;
}
int BST::max(wezel * x)
{
while(x->right) x = x->right;
return x->key;
}
wezel * BST::minWezel(wezel * x)
{
while(x->left) x = x->left;
return x;
}
wezel * BST::maxWezel(wezel * x)
{
while(x->right) x = x->right;
return x;
}
wezel * BST::pred(wezel * x)
{
if(x->left) return maxWezel(x->left);
wezel * y;
do
{
y = x;
x = x->p;
} while(x && (x->right != y));
return x;
}
void BST::remove(wezel*& root, int k)
{
wezel* usuwacz = find(root,k);
if (usuwacz)
{
if ((usuwacz->left) && (usuwacz->right))
{
wezel* pre = pred(usuwacz);
usuwacz->key=pre->key;
if (pre->p->left == pre)
pre->p->left=pre->left;
else
pre->p->right=pre->left;
delete pre;
}
else
{
wezel* poddrzewo = usuwacz->left ? usuwacz->left : usuwacz->right;
if (usuwacz->p)
{
if (usuwacz->p->left == usuwacz)
usuwacz->p->left = poddrzewo;
else
usuwacz->p->right = poddrzewo;
if (poddrzewo)
poddrzewo->p = usuwacz->p;
}
else
{
poddrzewo->p=NULL;
root=poddrzewo;
}
delete usuwacz;
}
}
}
void BST::preorder(wezel* x)
{
if(x)
{
cout << x->key << endl;
preorder(x->left);
preorder(x->right);
}
}
void BST::inorder(wezel * x)
{
if(x)
{
inorder(x->left);
cout << x->key << endl;
inorder(x->right);
}
}
void BST::postorder(wezel * x)
{
if(x)
{
postorder(x->left);
postorder(x->right);
cout << x->key << endl; // tutaj przetwarzamy bieżący węzeł
}
}
void BST::add(int n, wezel *start)
{
wezel * p=root;
if(root==NULL)
{
wezel *nowy = new wezel;
root->key = n;
root->left = NULL;
root->right = NULL;
root->p = NULL;
}
else if(n < start->key)
{
if(start->left != NULL)
{
add(n,start->left);
}
else
{
wezel *nowy = new wezel;
nowy->key = n;
nowy->left = NULL;
nowy->right = NULL;
nowy->p = start;
start->left=nowy;
}
}
else
{
if(start->right!=NULL)
{
add(n,start->right);
}
else
{
wezel *nowy = new wezel;
nowy->key = n;
nowy->left = NULL;
nowy->right = NULL;
nowy->p = start;
start->right=nowy;
}
}
}
void BST::build(int tab[], const unsigned int size)
{
wezel*p;
for(int i=0; i<size; i++)
{
add(tab[i], p);
}
}
int main()
{
BST * T = new BST();
system("pause");
}
#include<iostream>
#include<ctime>
using namespace std;
class sortowanie
{
private:
int rozm;
int*tab;
public:
sortowanie()
{
srand(time(NULL));
int*tab=new int[rozm];
for(int i=0; i<rozm; i++)
{
tab[i]=rand()%100;
}
}
~sortowanie()
{
delete[] tab;
}
void zamien(int &a, int &b)
{
int tmp;
tmp=a;
a=b;
b=tmp;
}
void wyswietl( int rozm)
{
for(int i=0; i<rozm; i++)
{
cout<<tab[i]<<" ";
}
}
void sort_wybieranie(int a)
{
int i, j, tmp;
for(i=0; i<a; i++)
{
tmp=i;
for(j=i+1; j<a; j++) if(tab[j]<tab[tmp]) tmp=j;
zamien(tab[tmp], tab[i]);
}
}
void sort_szybk(int lewy, int prawy)
{
int i,j,piwot;
i = (lewy + prawy) / 2;
piwot = tab[i]; tab[i] = tab[prawy];
for(j = i = lewy; i < prawy; i++)
if(tab[i] < piwot)
{
zamien(tab[i], tab[j]);
j++;
}
tab[prawy] = tab[j]; tab[j] = piwot;
if(lewy < j - 1) sort_szybk(lewy, j - 1);
if(j + 1 < prawy) sort_szybk(j + 1, prawy);
}
void sort_scal(int i_p, int i_k, int d[])
{
int i_s,i1,i2,i; int*p=new int[i_k+1];
i_s = (i_p + i_k + 1) / 2;
if(i_s - i_p > 1) sort_scal(i_p, i_s - 1);
if(i_k - i_s > 0) sort_scal(i_s, i_k);
i1 = i_p; i2 = i_s;
for(i = i_p; i <= i_k; i++)
p[i] = ((i1 == i_s) || ((i2 <= i_k) && (d[i1] > d[i2]))) ? d[i2++] : d[i1++];
for(i = i_p; i <= i_k; i++) d[i] = p[i];
}
};
int main()
{
system("pause");
}