欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉搜索树的原理及其实现

程序员文章站 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;
}

测试结果:

二叉搜索树的原理及其实现
参考资料:《挑战程序设计竞赛》(俗称白书)