【深基16.例7】普通二叉树（简化版）

链接

该说不愧是简化版嘛,还以为要用平衡树的,结果普通的二叉查找就可以了

至于前驱和后继,和二分法挺像的,就不解释了,代码易懂

#include<iostream>
using namespace std;

struct tree {
	int val;
	tree* left, * right;
	tree(int x):val(x),left(nullptr),right(nullptr){}
};

class BST {
private:
	tree* root;
	int count = 0;
	int rank = 0;
	int rank_ans = 0;
	tree* Insert(tree* node, int val) {
		if (!node) return new tree(val);
		if (val < node->val) node->left = Insert(node->left, val);
		else if (val > node->val) node->right = Insert(node->right, val);
		return node;
	}

	tree* search(tree* node, int val) {
		if (!node || node->val == val) return node;
		else if (node->val < val) return search(node->right, val);
		else if (node->val > val) return search(node->left, val);
	}

	int former(tree* node, int val) {
		int temp = INT_MIN + 1;//注意加一,否则WA警告
		while (node) {
			if (node->val < val) {
				temp = node->val;
				node = node->right;
			}
			else node = node->left;
		}
		return temp;
	}

	int latter(tree* node, int val) {
		int temp = INT_MAX;
		while (node) {
			if (node->val > val) {
				temp = node->val;
				node = node->left;
			}
			else node = node->right;
		}
		return temp;
	}

	void query_rank(tree* node,int x) {
		if (!node) return;
		query_rank(node->left,x);
		if (x <= node->val) return;
		count++;
		
		query_rank(node->right,x);
	}

	void query_val(tree* node, int x) {
		if (!node) return;
			query_val(node->left, x);
			rank++;
			if (rank == x) { 
				rank_ans = node->val; 
				return;
			}
			query_val(node->right, x);
	}

	void Delete(tree* node) {
		if (!node) return;
		Delete(node->left);
		Delete(node->right);
		delete node;
	}
public:
	BST():root(nullptr){}

	void Insert(int val) {
		root = Insert(root, val);
	}

	int Rank(int val) {
		count = 0;
		query_rank(root,val);
		return count + 1;
	}

	int val(int x) {
		rank = 0;
		rank_ans = 0;
		query_val(root, x);
		return rank_ans;
	}

	int former(int val) {
		return former(root, val);
	}

	int latter(int val) {
		return latter(root, val);
	}

	~BST() {
		Delete(root);
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	cin >> t;
	BST bst;
	while (t--) {
		int op, x;
		cin >> op >> x;
		switch (op) {
		case 1: cout << bst.Rank(x) << '\n';
			break;
		case 2:cout << bst.val(x) << '\n';
			break;
		case 3:cout << bst.former(x) << '\n';
			break;
		case 4:cout << bst.latter(x) << '\n';
			break;
		case 5:bst.Insert(x);
			break;
		}
	}
}

时间复杂度:O(t*n)

空间复杂度:O(n)