Бінарне дерево пошуку
З однією структурою
#include <iostream>
using namespace std;
struct Tree {
int a;
Tree* left = nullptr;
Tree* right = nullptr;
};
void ShowTree(Tree* tmp) {
if (tmp != nullptr)
{
ShowTree(tmp->left);
cout << tmp->a << endl;
ShowTree(tmp->right);
}
}
int main()
{
Tree t1;
t1.a = 25;
Tree t2;
t2.a = 15;
Tree t3;
t3.a = 50;
Tree t4;
t4.a = 3;
Tree t5;
t5.a = 20;
Tree t6;
t6.a = 60;
t1.left = &t2;
t1.right = &t3;
t2.left = &t4;
t2.right = &t5;
t3.right = &t6;
ShowTree(&t1);
system("pause");
return 0;
}
3 15 20 25 50 60
З класом і структурою
#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);
}
};
int main()
{
BST t;
t.insert(5);
t.insert(2);
t.insert(3);
t.insert(1);
t.insert(7);
t.display();
t.remove(5);
t.display();
t.remove(5);
t.display();
t.remove(7);
t.display();
system("pause");
return 0;
}
1 2 3 5 7
1 2 3 7
1 2 3 7
1 2 3