解析BST C/C++语方、数据结构讲解、辅导留学生C BST 设计

#include
using namespace std;
class BST
{
struct node
{
int data;
node* left;
node* right;
int height;
};
node* root;
// void makeEmpty(node* t)
// {
// if(t == NULL)
// return;
// makeEmpty(t->left);
// makeEmpty(t->right);
// delete t;
// }
node* insert(int x, node* t)
{
if(t == NULL)
{
t = new node;
t->data = x;
t->height = 0;
t->left = NULL;
t->right = NULL;
}
else if(x data)
{
t->left = insert(x, t->left);
if(height(t->left) - height(t->right) == 2)
{
if(x left->data)
t = singleRightRotate(t);
else
t = doubleRightRotate(t);
}
}
else if(x > t->data)
{
t->right = insert(x, t->right);
if(height(t->right) - height(t->left) == 2)
{
if(x > t->right->data)
t = singleLeftRotate(t);
else
t = doubleLeftRotate(t);
}
}
t->height = max(height(t->left), height(t->right))+1;
return t;
}
node* singleRightRotate(node* t)
{
node* u = t->left;
t->left = u->right;
u->right = t;
t->height = max(height(t->left), height(t->right))+1;
u->height = max(height(u->left), t->height)+1;
return u;
}
node* singleLeftRotate(node* t)
{
node* u = t->right;
t->right = u->left;
u->left = t;
t->height = max(height(t->left), height(t->right))+1;
u->height = max(height(t->right), t->height)+1 ;
return u;
}
node* doubleLeftRotate(node* t)
{
t->right = singleRightRotate(t->right);
return singleLeftRotate(t);
}
node* doubleRightRotate(node* t)
{
t->left = singleLeftRotate(t->left);
return singleRightRotate(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;
// Element not found
if(t == NULL)
return NULL;
// Searching for element
else if(x data)
t->left = remove(x, t->left);
else if(x > t->data)
t->right = remove(x, t->right);
// Element found
// With 2 children
else if(t->left t->right)
{
temp = findMin(t->right);
t->data = temp->data;
t->right = remove(t->data, t->right);
}
// With one or zero child
else
{
temp = t;
if(t->left == NULL)
t = t->right;
else if(t->right == NULL)
t = t->left;
delete temp;
}
if(t == NULL)
return t;
t->height = max(height(t->left), height(t->right))+1;
// If node is unbalanced
// If left node is deleted, right case
if(height(t->left) - height(t->right) == 2)
{
// right right case
if(height(t->left->left) - height(t->left->right) == 1)
return singleLeftRotate(t);
// right left case
else
return doubleLeftRotate(t);
}
// If right node is deleted, left case
else if(height(t->right) - height(t->left) == 2)
{
// left left case
if(height(t->right->right) - height(t->right->left) == 1)
return singleRightRotate(t);
// left right case
else
return doubleRightRotate(t);
}
return t;
}
int height(node* t)
{
return (t == NULL ? -1 : t->height);
}
int getBalance(node* t)
{
if(t == NULL)
return 0;
else
return height(t->left) - height(t->right);
}
void inorder(node* t)
{
if(t == NULL){
return;
}
inorder(t->left);
cout data right);
}
void postorder(node* t)
{
if(t == NULL){
return;
}
postorder(t->left);
// cout data right);
cout data data left);
// cout data right);

}
public:
BST()
{
root = NULL;
}
void insert(int x)
{
root = insert(x, root);
}
void remove(int x)
{
root = remove(x, root);
}
void display()
{
inorder(root);
cout << endl;
}
void display2()
{
postorder(root);
cout << endl;
}
void display3()
{
preorder(root);
cout << endl;
}
};
int main()
{
BST t;
t.insert(14);
t.insert(10);
t.insert(2);
t.insert(33);
t.insert(23);
t.insert(5);
t.insert(100);
t.insert(81);
t.insert(44);
t.insert(12);
// t.display();
// t.display2();
// t.display3();
t.remove(5);
t.remove(33);
// t.remove(65);
// t.remove(89);
// t.remove(43);
// t.remove(88);
// t.remove(20);
// t.remove(38);
t.display();
}