c++实现简单搜索二叉树＜K,V＞形

搜索二叉树

搜索二叉树本质:左节点比我小 右节点比我大

节点类

BSTreeNode:给自身节点封装一个类 用这个类来添加节点的操作
我们写的是一个key.value型的搜索二叉树

template<class K,class V>
struct BSTreeNode
{
	typedef BSTreeNode<K,V> Node;
	Node* _left;//左孩子
	Node* _right;//右孩子
	K _key;//建
	V _value;//值
};
1
2
3
4
5
6
7
8
9

BSTreeNode(节点类的构造)

BSTreeNode(const K& key, const V& value)
		: _left(nullptr)
		, _right(nullptr)
		, _key(key)
		, _value(value)
	{}
1
2
3
4
5
6

BSTree(功能实现类)

因为我们实现的是key，value型的所以模版是K,V
类中变量

template<class K,class V>
class BSTree
{
	typedef BSTreeNode<K,V> Node;
private:
	Node* _root;
};
1
2
3
4
5
6
7

Insert(插入)

首先:要判断是否为空树 如果是空树直接new一个新节点当根节点
还有就是建立一个cur让其等于根节点
用一个parent记录cur的父节点
用他们中的key值比较谁大谁小
小的往左走，大的往右走
走到合适位置，new一个新节点插入到树中

bool Insert(const K& key,const V& value)
{
	if (_root == nullptr)//树为空的情况
	{
		_root = new Node(key,value);
		return true;
	}
	Node* parent = nullptr;//因为cur是局部变量函数走完会销毁，所以增加一个指针 链接cur
	Node* cur = _root;
	while (cur)
	{
		if (cur->_key < key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_key > key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}
	cur = new Node(key,value);
	if (parent->_key < key)//大就链右边 小链左边
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

Erase(删除)

看代码中的注释

bool Erase(const K& key)
{
	Node* parent = nullptr;//记录父节点
	Node* cur = _root;//从根开始找
	while (cur)
	{
		//大了往右 小了往左
		if (cur->_key < key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_key > key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else//找到节点
		{
			if (cur->_left == nullptr)//左树为空
			{
				if (cur == _root)//头节点没有左子树
				{
					_root = cur->_right;
				}
				else//不为根节点
				{
					if (cur == parent->_right)//自身为父节点的右节点
					{
						//让自己的右节点成为父节点的右节点
						parent->_right = cur->_right;
					}
					else//左节点
					{
						//让我的右节点成为父节点的左节点
						parent->_left = cur->_right;
					}
				}
				delete cur;//删掉自己这个节点
				return true;
			}
			else if (cur->_right == nullptr)//右树为空
			{
				if (cur == _root)//头节点没有右子树
				{
					_root = cur->_left;
				}
				else
				{
					//让自己的左节点代替自己
					if (cur == parent->_right)
					{
						parent->_right = cur->_left;
					}
					else
					{
						parent->_left = cur->_left;
					}
				}
				delete cur;//删除节点
				return true;
			}
			else
			{
				//左右都不为空
				//找到右数中最小的代替自己
				Node* rightMin = cur->_right;
				//不能为空 如果为空的话 
				//要删的是头节点 会让空的_left指向他 会崩溃
				Node* father = cur;//定义这个为rightMin的父节点
				while (rightMin->_left)//找右树中的最小
				{
					father = rightMin;
					rightMin = rightMin->_left;
				}
				cur->_key = rightMin->_key;//交换值
				//如果 相等 那么才让他的父节点左指向他自身节点的右
				if (rightMin == father->_left)
				{
					father->_left = rightMin->_right;
				}
				else//不想等就是说明的头节点 那么就要让头节点的右指向他的右
				{
					father->_right = rightMin->_right;
				}
				delete rightMin;
				return true;
			}
		}
	}
	return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

Find(查找这个节点)

大了往右 小了往左 找到返回节点 没找到返回空

Node* Find(const K& key)
{
	Node* cur = _root;
	while (cur)
	{
		
		if (cur->_key < key)
		{
			cur = cur->_right;
		}
		else if (cur->_key > key)
		{
			cur = cur->_left;
		}
		else
		{
			return cur;
		}
	}
	return nullptr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21