数据结构 - 二叉查找树 Binary Search Tree

一、性质
二、结点定义
三、部分操作
- 插入:唯一键值和重复键值
- 删除：普通删除和懒惰删除
- 四种遍历：先、中、后序、层级
四、进一步思考

一、二叉查找树性质

若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
任意节点的左、右子树也分别为二叉查找树；
树中没有键值相等的节点。

二、结点定义

struct TreeNode{
	int value;
	TreeNode *left, *right;
	TreeNode(int val): value(val), left(NULL), right(NULL){}
};

三、部分操作

3.1插入

3.1.1 唯一键值结点的插入

递归插入即可。

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

TreeNode* SearchTree::RecursiveInsert(int val, TreeNode* head){
	if(!head){return new TreeNode(val);}
	if(val > head->value){
		head->right = RecursiveInsert(val, head->right);
	}
	else if(val < head->value){
		head->left = RecursiveInsert(val, head->left);
	}
	return head;
}

3.1.2 支持重复键值结点的插入

如果键值是包含在简单的数据结构中，只需要额外一个记录频次的变量。

如果键值时包含在庞大的数据结构中，可以将相同键值存储到辅助数据结构中，比如链表、另一个查找树。

3.2 删除

3.2.1 唯一键值结点删除

递归找到删除结点
将它的值由其右子树最小值或者左子树最大值替换
然后递归删除右子树最小值结点/左子树最大值结点

void SearchTree::Delete(int val){ 
	RecursiveDelete(val, root);
}

TreeNode* SearchTree::RecursiveDelete(int val, TreeNode* head){
	if(!head) return NULL;
	if(head->value < val){
		head->right = RecursiveDelete(val, head->right);
	}
	else if(head->value > val){
		head->left = RecursiveDelete(val, head->left);
	}
	else{
		if(head->left && head->right){
			head->value = RecursiveMin(head->right)->value;
			head->right = RecursiveDelete(head->value, head->right);
		}
		else{
			TreeNode* tmp = head;
			if(!head->left) head = head->right;
			else if(!head->right) head = head->left;
			delete tmp; tmp = NULL;
		}
	}
	return head;
}

3.2.2 懒惰删除->重复键值结点删除

如果删除的结点比较少，可以用懒惰删除法。当一个结点要被删除，它仍可以被保留在tree中，只是被标记成删除的状态。而且，即便树有一半的结点被标记为删除状态，时间上的浪费也只是常数。

这个方法很适用于当树允许重复的结点出现时的情况。允许重复结点的树有记录频次的变量，删除一个结点，相当把这个变量减一，也就相当于mark了。

3.3 四种遍历

3.3.1 先序遍历 Preorder

顺序：父结点->左子树->右子树。

void SearchTree::PrintPreorder(){
	Preorder(root);
}

void SearchTree::Preorder(TreeNode* head){
	if(!head) return;
	cout << head->value << " ";
	Preorder(head->left);
	Preorder(head->right);
}

3.3.2 中序遍历 Inorder

顺序：左子树->父结点->右子树。

void SearchTree::PrintInorder(){
	Inorder(root);
}

void SearchTree::Inorder(TreeNode* head){
	if(!head) return;
	Inorder(head->left);
	cout << head->value << " ";
	Inorder(head->right);
}

3.3.3 后序遍历 Postorder

顺序：左子树->右子树->父结点。

void SearchTree::PrintPostorder(){
	Postorder(root);
}

void SearchTree::Postorder(TreeNode* head){
	if(!head) return;
	Postorder(head->left);
	Postorder(head->right);
	cout << head->value << " ";
}

3.3.4 层级遍历 Level Order

按照结点深度遍历，即先打印深度为0也就是结点，然后打印深度为1的结点，依次递推。

不同于前面三个遍历每次打印单个结点，层级遍历每一次需要打印一层结点，而结点之间从结构上，没有连接，主要通过父结点的左右指针访问。

因此，我们需要用到一个容器类变量，保存上一层的父结点。这里我选择用queue<>，遍历操作从队列前端执行，更新push操作从队列后端执行，如下所示。

void SearchTree::PrintLevelorder(){
	if(!root) return;
	queue<TreeNode*> nodeQueue;
	nodeQueue.push(root);
	Levelorder(nodeQueue);
}

void SearchTree::Levelorder(queue<TreeNode*> &nodeQueue){
	if(nodeQueue.empty()) return;
	int size = nodeQueue.size(); 
	TreeNode* cur = NULL;
	while(size--){
		cur = nodeQueue.front();
		cout << cur->value << " ";
		nodeQueue.pop();
		if(cur->left) nodeQueue.push(cur->left);
		if(cur->right) nodeQueue.push(cur->right);
	}
	return Levelorder(nodeQueue);
}

3.4 完整C++实现

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct TreeNode{
	int value;
	TreeNode *left, *right;
	TreeNode(int val): value(val), left(NULL), right(NULL){}
};

class SearchTree {
public:
	SearchTree():root(NULL){}
	SearchTree(vector<int> &arr);
	void PrintPreorder();
	void PrintInorder();
	void PrintPostorder();
	void PrintLevelorder();
	void Insert(int val);
	void Delete(int val);
	TreeNode* Find(int val);
	TreeNode* Min();
	void Clear();
private:
	void Preorder(TreeNode* head);
	void Inorder(TreeNode* head);
	void Postorder(TreeNode* head);
	void Levelorder(queue<TreeNode*> &nodeQueue);
	TreeNode* RecursiveInsert(int val, TreeNode* head);
	TreeNode* RecursiveDelete(int val, TreeNode* head);
	TreeNode* RecursiveFind(int val, TreeNode* head);
	TreeNode* RecursiveMin(TreeNode* head);
	TreeNode* RecursiveClear(TreeNode* &head);
	TreeNode* root;
};

SearchTree::SearchTree(vector<int> &arr){
	for(auto i: arr)
		Insert(i);
}

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

TreeNode* SearchTree::RecursiveInsert(int val, TreeNode* head){
	if(!head){return new TreeNode(val);}
	if(val > head->value){
		head->right = RecursiveInsert(val, head->right);
	}
	else if(val < head->value){
		head->left = RecursiveInsert(val, head->left);
	}
	return head;
}


void SearchTree::Delete(int val){ 
	RecursiveDelete(val, root);
}

TreeNode* SearchTree::RecursiveDelete(int val, TreeNode* head){
	if(!head) return NULL;
	if(head->value < val){
		head->right = RecursiveDelete(val, head->right);
	}
	else if(head->value > val){
		head->left = RecursiveDelete(val, head->left);
	}
	else{
		if(head->left && head->right){
			head->value = RecursiveMin(head->right)->value;
			head->right = RecursiveDelete(head->value, head->right);
		}
		else{
			TreeNode* tmp = head;
			if(!head->left) head = head->right;
			else if(!head->right) head = head->left;
			delete tmp; tmp = NULL;
		}
	}
	return head;
}

TreeNode* SearchTree::Find(int val){
	return RecursiveFind(val, root);
}

TreeNode* SearchTree::RecursiveFind(int val, TreeNode* head){
	if(!head) return NULL;
	if(head->value > val)
		return RecursiveFind(val, head->left);
	else if(head->value < val)
		return RecursiveFind(val, head->right);
	else return head;
}

TreeNode* SearchTree::Min(){
	return RecursiveMin(root);
}

TreeNode* SearchTree::RecursiveMin(TreeNode* head){
	if(!head) return NULL;
	if(!head->left) return head;
	return RecursiveMin(head->left);
}

void SearchTree::Clear(){
	RecursiveClear(root);
}

TreeNode* SearchTree::RecursiveClear(TreeNode* &head){
	if(head){
		head->left = RecursiveClear(head->left);
		head->right = RecursiveClear(head->right);
		delete head; head = NULL;
	}
	return NULL;
}

void SearchTree::PrintPreorder(){
	Preorder(root);
}

void SearchTree::Preorder(TreeNode* head){
	if(!head) return;
	cout << head->value << " ";
	Preorder(head->left);
	Preorder(head->right);
}

void SearchTree::PrintInorder(){
	Inorder(root);
}

void SearchTree::Inorder(TreeNode* head){
	if(!head) return;
	Inorder(head->left);
	cout << head->value << " ";
	Inorder(head->right);
}

void SearchTree::PrintPostorder(){
	Postorder(root);
}

void SearchTree::Postorder(TreeNode* head){
	if(!head) return;
	Postorder(head->left);
	Postorder(head->right);
	cout << head->value << " ";
}

void SearchTree::PrintLevelorder(){
	if(!root) return;
	queue<TreeNode*> nodeQueue;
	nodeQueue.push(root);
	Levelorder(nodeQueue);
}

void SearchTree::Levelorder(queue<TreeNode*> &nodeQueue){
	if(nodeQueue.empty()) return;
	int size = nodeQueue.size();
	TreeNode* cur = NULL;
	while(size--){
		cur = nodeQueue.front();
		cout << cur->value << " ";
		nodeQueue.pop();
		if(cur->left) nodeQueue.push(cur->left);
		if(cur->right) nodeQueue.push(cur->right);
	}
	return Levelorder(nodeQueue);
}


int main(){
	vector<int> arr = {8, 4, 15, 2, 6, 9, 17};
	
	SearchTree test(arr); //Insertion Test
	
	cout << "Before deletion: " << endl; 
	cout << "Preorder: "; test.PrintPreorder(); cout << endl; 
	cout << "Inorder: "; test.PrintInorder(); cout << endl;
	cout << "Postorder: "; test.PrintPostorder(); cout << endl;
	cout << "Levelorder: "; test.PrintLevelorder(); cout << endl;


	test.Delete(8);//Deletion Test
	cout << "After deletion: ";
	test.PrintPreorder(); cout << endl; 

	TreeNode* fRet = test.Find(8);//Find Test
	if(fRet) cout << "Find: " << fRet->value << endl;
	else cout << "Can't find."<< endl;

	test.Clear(); //Clear Test
	test.PrintPreorder(); cout << endl;

四、进一步思考

按照以上insert和delete方法，我们发现一定次数后，树容易一个方向倾斜。

如果delete的结点由左子树最大值替换，则往右倾斜；
如果delete的结点由右子树最小值替换，则往左倾斜。

针对这个问题，我们很容易想到一个方法：delete的结点由random(左子树最大值，右子树最小值)替换。

还有一个方法就是平衡二叉树。

数据结构 - 二叉查找树 Binary Search Tree

一、二叉查找树性质

二、结点定义

三、部分操作

3.1插入

3.1.1 唯一键值结点的插入

3.1.2 支持重复键值结点的插入

3.2 删除

3.2.1 唯一键值结点删除

3.2.2 懒惰删除->重复键值结点删除

3.3 四种遍历

3.3.1 先序遍历 Preorder

3.3.2 中序遍历 Inorder

3.3.3 后序遍历 Postorder

3.3.4 层级遍历 Level Order

3.4 完整C++实现

四、进一步思考

继续阅读

树的基本概念(定义、基本术语、性质)

GSL--GNU Scientific Library

D5|哈希表，善用数据结构

如何成为一名.net 工程师?

BMP文件结构及图像每行字节计算方法

D. Ehab the Xorcist(构造+思维)

查找算法之二分查找查找算法之二分查找

JAVA高效编程指南

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

【数据结构】医院选址

[转]ISUP信令的IAM消息详细内容

笔试面试题目：滑动窗口(二)

交通/城市相关的公开的数据集上学时整理的Xie et al., 2020收集的

数据结构与算法（27）——排序（二）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

Linux设备模型（中）之上层容器