//struktury
#include<iostream>
using namespace std;
struct BstNode {
int data;
BstNode* left;
BstNode* right;
BstNode* stary;
};
BstNode* GetNewNode(int data) {
BstNode* newNode = new BstNode();
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
BstNode* Insert(BstNode* root, int data) {
if (root == NULL) { // empty tree
root = GetNewNode(data);
}
// if data to be inserted is lesser, insert in left subtree.
else if (data <= root->data) {
root->left = Insert(root->left, data);
}
// else, insert in right subtree.
else {
root->right = Insert(root->right, data);
}
return root;
}
BstNode* Insertbst(BstNode* root, int data) {
if (root == NULL) { // empty tree
root = GetNewNode(data);
}
// if data to be inserted is lesser, insert in left subtree.
else if (data <= root->data) {
root->left = Insertbst(root->left, data);
root->left->stary = root;
}
// else, insert in right subtree.
else {
root->right = Insert(root->right, data);
root->right->stary = root;
}
return root;
}
bool Search(BstNode* root, int data) {
if (root == NULL) {
return false;
}
else if (root->data == data) {
return true;
}
else if (data <= root->data) {
return Search(root->left, data);
}
else {
return Search(root->right, data);
}
}
void Inorder(BstNode* root) {
if (root == NULL) return;
Inorder(root->left); //Visit left subtree
cout<<root->data<<" "; //Print data
Inorder(root->right); // Visit right subtree
}
BstNode* FindMin(BstNode* root)
{
while (root->left != NULL) root = root->left;
return root;
}
int max(BstNode* root)
{
BstNode* temp = root;
while (temp->right != NULL)
temp = temp->right;
return(temp->data);
}
int min(BstNode* root)
{
BstNode* temp = root;
while (temp->left != NULL)
temp = temp->left;
return(temp->data);
}
BstNode* usunliscie(BstNode* root) {
if (root == NULL)
return NULL;
if (root->left == NULL && root->right == NULL)
{
delete root;
return NULL;
}
root->left = usunliscie(root->left);
root->right = usunliscie(root->right);
return root;
}
BstNode* Delete(BstNode* root, int data) {
if (root == NULL) return root;
else if (data < root->data) root->left = Delete(root->left, data);
else if (data > root->data) root->right = Delete(root->right, data);
// znaleziono
else {
// Case 1: nie ma dzieci
if (root->left == NULL && root->right == NULL) {
delete root;
root = NULL;
}
//Case 2: jedno dziecko
else if (root->left == NULL) {
BstNode* temp = root;
root = root->right;
delete temp;
}
else if (root->right == NULL) {
BstNode* temp = root;
root = root->left;
delete temp;
}
// case 3: 2 dzieci - sprowadzam do postaci zeby bylo jedno dziecko
else {
BstNode* temp = FindMin(root->right);
root->data = temp->data;
root->right = Delete(root->right, temp->data);
}
}
return root;
}
BstNode* minn(BstNode* root)
{
while (root->left)
root = root->left;
return root;
}
BstNode* maxx(BstNode* root)
{
while (root->right)
root = root->right;
return root;
}
void nastepnik(BstNode* root, BstNode*& pop, int x)
{
if (root == NULL)
{
pop = NULL;
return;
}
if (root->data == x) {
if (root->right)
pop = minn(root->right);
}
else if (x < root->data)
{
pop = root;
nastepnik(root->left, pop, x);
}
else {
nastepnik(root->right,pop, x);
}
}
void poprzednik(BstNode* root, BstNode*& pop, int x)
{
if (root == NULL)
{
pop = NULL;
return;
}
if (root->data == x) {
if (root->left)
pop = maxx(root->left);
}
else if (x < root->data)
poprzednik(root->left, pop, x);
else {
pop = root;
poprzednik(root->right, pop, x);
}
}
// Rotacja w lewo
//---------------
void rot_L(BstNode*& root, BstNode* A)
{
BstNode* B = A->right, *p = A->stary;
if (B)
{
A->right = B->left;
if (A->right) A->right->stary = A;
B->left = A;
B->stary = p;
A->stary = B;
if (p)
{
if (p->left == A) p->left = B; else p->right = B;
}
else root = B;
}
}
// Rotacja w prawo
//----------------
void rot_R(BstNode*& root, BstNode* A)
{
BstNode* B = A->left, *p = A->stary;
if (B)
{
A->left = B->right;
if (A->left) A->left->stary = A;
B->right = A;
B->stary = p;
A->stary = B;
if (p)
{
if (p->left == A) p->left = B; else p->right = B;
}
else root = B;
}
}
int main() {
BstNode* root = NULL;
BstNode* pop = NULL;
root = Insertbst(root, 15);
root = Insertbst(root, 10);
root = Insertbst(root, 20);
root = Insertbst(root, 25);
root = Insertbst(root, 8);
root = Insertbst(root, 12);
Inorder(root);
root=Delete(root, 10);
cout << endl;
Inorder(root);
nastepnik(root, pop, 12);
cout << endl << pop->data;
rot_R(root, root->right);
system("pause");
return 0;
}
//klasy
#include<iostream>
using namespace std;
class BST {
struct BstNode {
int data;
BstNode* left;
BstNode* right;
BstNode* stary;
};
BstNode* root;
BstNode* GetNewNode(int data) {
BstNode* newNode = new BstNode();
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
BstNode* Insertbst(BstNode* root, int data) {
if (root == NULL) { // empty tree
root = GetNewNode(data);
}
// if data to be inserted is lesser, insert in left subtree.
else if (data <= root->data) {
root->left = Insertbst(root->left, data);
root->left->stary = root;
}
// else, insert in right subtree.
else {
root->right = Insertbst(root->right, data);
root->right->stary = root;
}
return root;
}
bool Search(BstNode* root, int data) {
if (root == NULL) {
return false;
}
else if (root->data == data) {
return true;
}
else if (data <= root->data) {
return Search(root->left, data);
}
else {
return Search(root->right, data);
}
}
void Inorder(BstNode* root) {
if (root == NULL) return;
Inorder(root->left); //Visit left subtree
cout << root->data << " "; //Print data
Inorder(root->right); // Visit right subtree
}
BstNode* FindMin(BstNode* root)
{
while (root->left != NULL) root = root->left;
return root;
}
int max(BstNode* root)
{
BstNode* temp = root;
while (temp->right != NULL)
temp = temp->right;
return(temp->data);
}
int min(BstNode* root)
{
BstNode* temp = root;
while (temp->left != NULL)
temp = temp->left;
return(temp->data);
}
BstNode* usunliscie(BstNode* root) {
if (root == NULL)
return NULL;
if (root->left == NULL && root->right == NULL)
{
delete root;
return NULL;
}
root->left = usunliscie(root->left);
root->right = usunliscie(root->right);
return root;
}
BstNode* Delete(BstNode* root, int data) {
if (root == NULL) return root;
else if (data < root->data) root->left = Delete(root->left, data);
else if (data > root->data) root->right = Delete(root->right, data);
// znaleziono
else {
// Case 1: nie ma dzieci
if (root->left == NULL && root->right == NULL) {
delete root;
root = NULL;
}
//Case 2: jedno dziecko
else if (root->left == NULL) {
BstNode* temp = root;
root = root->right;
delete temp;
}
else if (root->right == NULL) {
BstNode* temp = root;
root = root->left;
delete temp;
}
// case 3: 2 dzieci - sprowadzam do postaci zeby bylo jedno dziecko
else {
BstNode* temp = FindMin(root->right);
root->data = temp->data;
root->right = Delete(root->right, temp->data);
}
}
return root;
}
BstNode* minn(BstNode* root)
{
while (root->left)
root = root->left;
return root;
}
BstNode* maxx(BstNode* root)
{
while (root->right)
root = root->right;
return root;
}
void nastepnik(BstNode* root, BstNode*& pop, int x)
{
if (root == NULL)
{
pop = NULL;
return;
}
if (root->data == x) {
if (root->right)
pop = minn(root->right);
}
else if (x < root->data)
{
pop = root;
nastepnik(root->left, pop, x);
}
else {
nastepnik(root->right, pop, x);
}
}
void poprzednik(BstNode* root, BstNode*& pop, int x)
{
if (root == NULL)
{
pop = NULL;
return;
}
if (root->data == x) {
if (root->left)
pop = maxx(root->left);
}
else if (x < root->data)
poprzednik(root->left, pop, x);
else {
pop = root;
poprzednik(root->right, pop, x);
}
}
// Rotacja w lewo
//---------------
void rot_L(BstNode*& root, BstNode* A)
{
BstNode* B = A->right, * p = A->stary;
if (B)
{
A->right = B->left;
if (A->right) A->right->stary = A;
B->left = A;
B->stary = p;
A->stary = B;
if (p)
{
if (p->left == A) p->left = B; else p->right = B;
}
else root = B;
}
}
// Rotacja w prawo
//----------------
void rot_R(BstNode*& root, BstNode* A)
{
BstNode* B = A->left, * p = A->stary;
if (B)
{
A->left = B->right;
if (A->left) A->left->stary = A;
B->right = A;
B->stary = p;
A->stary = B;
if (p)
{
if (p->left == A) p->left = B; else p->right = B;
}
else root = B;
}
}
BstNode* makeEmpty(BstNode* t) {
if (t == NULL)
return NULL;
{
makeEmpty(t->left);
makeEmpty(t->right);
delete t;
}
return NULL;
}
public:
BST() {
root = NULL;
}
~BST() {
root = makeEmpty(root);
}
void insert(int x) {
root = Insertbst(root ,x);
}
void zobacz() {
Inorder(root);
}
};
int main() {
BST t;
t.insert(20);
t.insert(25);
t.insert(15);
t.insert(10);
t.insert(30);
t.zobacz();
system("pause");
return 0;
}