二叉搜索树的原理及其实现
程序员文章站
2022-03-30 22:58:16
...
二叉搜索树的原理及其实现
代码
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct poi {
int val;
poi *l, *r;
poi() {}
poi(int val, poi *l, poi *r) :val(val), l(l), r(r) {}
};
poi *insert(poi*node, int val) {
if (node == NULL) {
poi*p = new poi;
p->val = val;
p->l = p->r = NULL;
return p;
}
else {
if (node->val > val) node->l = insert(node->l, val);
else node->r = insert(node->r, val);
return node;
}
}
bool find(poi*node, int val) {
if (node == NULL) return NULL;
if (node->val == val) return node;
if (node->val > val) return find(node->l, val);
else return find(node->r, val);
}
poi *remove(poi*node, int val) {
if (node == NULL) return NULL;
else if (node->val > val) node->l = remove(node->l, val);
else if (node->val < val) node->r = remove(node->r, val);
else {
if (node->l == NULL) {
poi*p = node->r;
delete node;
return p;
}
else if (node->l->r == NULL) {
poi *p = node->l;
p->r = node->r;
delete node;
return p;
}
else {
poi*p = node->l;
while (p->r->r) p = p->r;
poi *q = p->r;
node->val = q->val;
p->r = q->l;
delete q;
}
}
return node;
}
void print(poi*node) {
if (node == NULL) return;
if (node) cout << node->val << " ";
if (node->l) print(node->l);
if (node->r) print(node->r);
}
int main() {
vector<int> a{ 1, 6, 3, 7, 4, 8, 2, 0, 9, 5 };
cout << "Building tree...\n\n";
poi*root = NULL;
for (int i : a) root = insert(root, i);
cout << "The tree has been built successfully!\n";
cout << "The tree is : ";
print(root); cout << "\n";
cout << "\n\nNow let's search for something...\n";
for (int i : a) {
if (find(root, i)) cout << i << " is found!\n";
else cout << i << " is not found!\n";
}
cout << "\nNow let's remove something...\n";
for (int i = 0; i < a.size() + 5; i++) {
if (find(root, i)) cout << i << " is found!\n";
else cout << i << " is not found!\n";
cout << "Try to remove " << i << "...\n";
root = remove(root, i);
cout << i << " has been removed successfully!\nTry to find " << i << "...\n";
if (find(root, i)) cout << i << " is found!\n";
else cout << i << " is not found!\n";
cout << "The tree is : ";
print(root); cout << "\n\n";
}
return 0;
}
测试结果:
参考资料:《挑战程序设计竞赛》(俗称白书)