[C++]二叉搜索树

2022-09-30 14:19:56

二叉搜索树

预备知识

二叉链存图
- Bolg

感谢：
代码参考：CSDN博主「chudongfang2015」的原创文章

链接

原理讲述

作用

用于对数据有序的排列

其中最典型的就是对数组进行有序排列

此片中也以此为模板

性质

对于树中的每一个节点

其左子树的数据均比次节点的数小

其右子树的数据均比次节点的数大

这样的树进行中序遍历得到的数组便是有序的

建树也是以此为基础

代码分析

节点 BSTreeNode

template<class K,class V>
struct BSTreeNode{
	K key_;
	V value_;
	BSTreeNode *lchild_,*rchild_;
	
	BSTreeNode(const K& key,const V& value){
		lchild_ = NULL;
		rchild_ = NULL;
		key_ = key;
		value_ = value;
	}
};

这里用到了模板

以应对不同数据的要求

这里还添加了 value_ 这个变量

是用来存储对应数字的实际含义的

（在这个Bolg中没有用到这里看key的值就行了）

这里还有用到构造函数

在创建的时候就把 key 和 value 的值加入进去

二叉树类 BSTree

template<class K,class V>
class BSTree{
	typedef BSTreeNode<K,V> Node;
	
public:
	BSTree(){
		root_ = NULL;
	}
	...
	
	Node* self(){
		return root_;
	}
private:
	Node* root_;
	...
};

这边我就把几个之后会用到的东西讲一讲

首先是这个 typedef

这么一长串敲起来着实费力

所以就用 Node（节点）来代替

然后就是其构造函数

让根节点指针为空即可

因为建树是由后面的插入完成的

最后就是 root_

代表这棵树的根节点

建树 Insert

	bool Insert_(Node*& root,const K& key,const V& value){
		if(root == NULL){
			root = new Node(key,value);
			return true;
		}
		
		if(root->key_ > key)
			return Insert_(root->lchild_,key,value);
		else
			return Insert_(root->rchild_,key,value);
	}

由于 BSTree 的性质

所以要让比当前节点小的值去左边

比当前节点大的值去右边

当到了新的节点（即空节点的时候）

就可以在这里留下了

寻找 Find

	Node* Find_(Node* root,const K& key){
	if(root == NULL)
		return NULL;
	if(root->key_ > key)
		return Find_(root->lchild_,key);
	else if(root->key_ < key)
		return Find_(root->rchild_,key);
	else
		return root;
	}

还是因为其性质

所以小左大右找

如果找到空节点就返回失败

删除 Remove

	bool Remove_(Node*& root,const K& key){
		if(root == NULL){
			return false;
		}
		
		if(root->lchild_ == NULL && root->rchild_ == NULL){
			if(root->key_ == key){
				delete root;
				root = NULL;
				return true;
			}
			else
				return false;
		}
		
		if(root->key_ > key)
			Remove_(root->lchild_,key);
		else if(root->key_ < key)
			Remove_(root->rchild_,key);
		else{
			Node* del = NULL;
			
			if(root->lchild_ == NULL){
				del = root;
				root = root->rchild_;
				delete del;
				del = NULL;
				return true;
			}
			else if(root->rchild_ == NULL){
				del = root;
				root = root->lchild_;
				delete del;
				del = NULL;
				return true;
			}
			else{
				Node* RightFirst = root->rchild_;
				while(RightFirst->lchild_){
					RightFirst = RightFirst->lchild_;
				}
				
				swap(root->key_,RightFirst->key_);
				swap(root->value_,RightFirst->value_);
				
				Remove_(root->rchild_,key);
				return true;
			}
		}
	}

删除主要分成四种情况

找到空节点找到叶子结点还需要往左/右找找到一般节点

找到空节点
- root == NULL

这直接返回 false 即可

找到叶子结点
- root->lchild_ == NULL && root->rchild_ == NULL

说明这个节点可以直接删除

不用考虑子树的问题

接下来来看一下如何删除

因为之前创建的时候是用 new 关键字开辟的空间

所以现在用 delete 关键字把这个空间给删除掉

注意这里的删除删的不是 root 这个指针

而是这个指针指向的东西

所以 delete 之后 root 就变成了野指针

需要重新赋值为 NULL

这样才能保证下一个节点插入的正确性

还需要往左/右找
- root->key_ > key
- root->key_ < key

这就直接往左/右传递即可

找到一般节点(即有子节点的节点)
- else

这里还需要分为三种情况：

只有右子树，只有左子树，左右子树都有

只有右子树
- root->lchild_ == NULL

这样就直接把右子树接到该节点即可

注意一下这里需要用到一个中间变量 del

用来存要删除的空间

先把 root 存在 del 中

然后用 rchild 接替 root

最后再用 del 把 root 这个节点删除

只有左子树
- root->rchild_ == NULL

原理和 只有右子树 相同

左右子树都有
- else

第一步是找到这个节点的前驱

i节点的前驱指的是比i节点大的节点中最小的节点

	Node* RightFirst = root->rchild_;
	while(RightFirst->lchild_){
		RightFirst = RightFirst->lchild_;
	}

由二叉索搜树的性质可知

其前驱即是其最小左子孙节点

即一直搜索它的左节点

就可以找到它的前驱

这里用 RightFirst 存下了它的前驱

用一个 while 循环即可轻松实现

第二步是交换前驱和该节点

	swap(root->key_,RightFirst->key_);
	swap(root->value_,RightFirst->value_);

直接 swap 他们的 key 和 value 就可

第三步删除它的前驱

由于此节点已经和他的前驱互换了

那么说明这个节点已经跳出了有两个子树的范围

可能是有一个或者零个子树

那就再次调用 Remove_ 函数就可以了

输出 Output

	void Output_(Node* root){
		if(root == NULL)
			return;
		
		Output_(root->lchild_);
		cout << root->key_ << " ";
		Output_(root->rchild_);
	}

这就是正常的中序遍历

和预备知识里的Bolg中的一样

完整代码放在下面

Code

#include<bits/stdc++.h>
using namespace std;

template<class K,class V>
struct BSTreeNode{
	K key_;
	V value_;
	BSTreeNode *lchild_,*rchild_;
	
	BSTreeNode(const K& key,const V& value){
		lchild_ = NULL;
		rchild_ = NULL;
		key_ = key;
		value_ = value;
	}
};

template<class K,class V>
class BSTree{
	typedef BSTreeNode<K,V> Node;
	
public:
	BSTree(){
		root_ = NULL;
	}
	
	Node* Find(const K& key){
		return Find_(root_,key);
	}

	bool Insert(const K& key,const V& value){
		return Insert_(root_,key,value);
	}
	
	bool Remove(const K& key){
		return Remove_(root_,key);
	}
	
	void Output(){
		Output_(root_);
		cout << endl;
	}
	
	Node* self(){
		return root_;
	}
private:
	Node* root_;
	
	Node* Find_(Node* root,const K& key){
	if(root == NULL)
		return NULL;
	if(root->key_ > key)
		return Find_(root->lchild_,key);
	else if(root->key_ < key)
		return Find_(root->rchild_,key);
	else
		return root;
	}
	
	bool Insert_(Node*& root,const K& key,const V& value){
		if(root == NULL){
			root = new Node(key,value);
			return true;
		}
		
		if(root->key_ > key)
			return Insert_(root->lchild_,key,value);
		else
			return Insert_(root->rchild_,key,value);
	}

	bool Remove_(Node*& root,const K& key){
		if(root == NULL){
			return false;
		}
		
		if(root->lchild_ == NULL && root->rchild_ == NULL){
			if(root->key_ == key){
				delete root;
				root = NULL;
				return true;
			}
			else
				return false;
		}
		
		if(root->key_ > key)
			Remove_(root->lchild_,key);
		else if(root->key_ < key)
			Remove_(root->rchild_,key);
		else{
			Node* del = NULL;
			
			if(root->lchild_ == NULL){
				del = root;
				root = root->rchild_;
				delete del;
				del = NULL;
				return true;
			}
			else if(root->rchild_ == NULL){
				del = root;
				root = root->lchild_;
				delete del;
				del = NULL;
				return true;
			}
			else{
				Node* RightFirst = root->rchild_;
				while(RightFirst->lchild_){
					RightFirst = RightFirst->lchild_;
				}
				
				swap(root->key_,RightFirst->key_);
				swap(root->value_,RightFirst->value_);
				
				Remove_(root->rchild_,key);
				return true;
			}
		}
	}
	
	void Output_(Node* root){
		if(root == NULL)
			return;
		
		Output_(root->lchild_);
		cout << root->key_ << " ";
		Output_(root->rchild_);
	}
};

int main(){
    BSTree<int, int> s;

    s.Insert(5, 1);
    s.Insert(4, 1);
    s.Insert(3, 1);
    s.Insert(6, 1);
    s.Insert(1, 1);
    s.Insert(2, 1);
    s.Insert(0, 1);
    s.Insert(9, 1);
    s.Insert(8, 1);
    s.Insert(7, 1);

    s.Output();

    cout << s.Find(6)->key_ << endl;

    s.Remove(4);
    s.Remove(6);
    s.Remove(3);
    s.Remove(1);
    s.Remove(2);

    s.Output();
	return 0;
}

码农公寓