二叉搜索树介绍和模拟实现_二叉树对单词排序

一.二叉搜索树概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
(1). 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
(2). 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
(3). 它的左右子树也分别为二叉搜索树

二叉搜索树之所以被称作搜索树是因为该结构适合用来查找，如在上图中我们想要查找10，根节点为11，所以我们直接去11的左半部分找，7 < 10，所以我们去7的右半部分找，9 < 10，所以我们去9的右半部分找，最终找到了10

注意查找的时间复杂度为O(N)，不是O(logN)，在如下这种极端情况下，时间复杂度为O(N)，只有当树的形状接近完全二叉树或满二叉树，才能达到O(logN)

二.二叉搜索树的模拟实现

二叉搜索树的接口总览

// 树的节点的结构体
template<class K>
struct BSTreeNode
{
	BSTreeNode(const K& key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}
	BSTreeNode* _left;
	BSTreeNode* _right;
	K _key;
};
template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node; 
public:
	// 构造函数
	BSTree();
	// 析构函数
	~BSTree();
	// 拷贝构造
	BSTree(const BSTree<T>& t);
	// 赋值运算符重载
	BSTree& operator=(BSTree<T> t);
	// 插入节点
	bool Insert(const K& val);
	// 查找节点
	Node* find(const K& val);
	// 删除节点
	bool Erase(const K& val);
	// 中序遍历
	void InOrder();
private:
	//成员变量，树的根节点
	Node* _root
};
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

(1). 构造函数

将树的 _root 初始化为空即可

BSTree()
  :_root(nullptr)
{}
1
2
3

(2). 拷贝构造

拷贝构造就需要考虑深拷贝的问题，步骤如下 :
(1). 构造出根节点
(2). 递归构造左子树
(3). 递归构造右子树

Node* Copy(Node* root)
{
	if (root == nullptr)
		return nullptr;
	// 构造根节点
	Node* copy = new Node(root->_val);
	// 递归构造左子树
	copy->_left = Copy(root->_left);
	// 递归构造右子树
	copy->_right = Copy(root->_right);
	return copy;
}
BSTree(const BSTree<K>& t)
{
	_root = Copy(t._root);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

(3). 赋值运算符重载

b1 = b2 相当于调用 b1.operator=(b2)，由于是传值所以会调用上面写的拷贝构造函数，而这正是我们想要的，因此我们只需要交换两者的 _root 即可

BSTree& operator=(BSTree<K> t)
{
	swap(_root,t._root);
	return *this;
}
1
2
3
4
5

(4). 插入操作

插入操作非递归写法 :
(1). 定义一个parent和cur指针，parent指向cur的父亲
(2). 当插入的值比cur->_val小时，说明应该插入到cur的左边，让 parent = cur，cur = cur->_left
(3). 当插入的值比cur->_val大时，说明应该插入到cur的右边，让 parent = cur，cur = cur->_right
(4). 当插入的值和cur->_val相等时，说明值已经存在，返回false
(4). 重复(2)(3)的过程，直到cur为空，比较插入的值和parent->_val的大小，以此来决定插入到 parent->_left还是插入到 parent->_right

bool Insert(const K& key)
{
		Node* p = new Node(key);
		// 第一次插入，直接让 _root = p 即可
		if (_root == nullptr)
		{
			_root = p;
			return true;
		}
		Node* parent = nullptr, * cur = _root;
		while (cur)
		{
			// 插入的值比cur->_val小
			if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			// 插入的值比cur->_val大
			else if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			// 插入的值和cur->_val相等
			else
			{
				return false;
			}
		}
		// key 比 parent->_key 小，插入到parent的左边
		if (key < parent->_key) parent->_left = p;
		// key 比 parent->_key 大，插入到parent的右边
		else parent->_right = p;
		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

插入操作递归写法 :

参数使用 Node*& root，当 root 递归到空的时候，root 还是上一个节点的 _left 或 _right 的别名，让root = new Node(key)，相当于上一个节点的 _left 或 _right 连接了 new Node(key) 节点

bool _InsertR(Node*& root,const K& key)
{
	if (root == nullptr)
	{
		root = new Node(key);
		return true;
	}
	// 去左边插入
	if (key < root->_key) _InsertR(root->_left, key);
	// 去右边插入
	else if (key > root->_key) _InsertR(root->_right, key);
	// 已经存在返回 false
	else return false;
}
bool InsertR(const K& key)
{
	return _InsertR(_root, key);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

(5). 查找操作

查找操作非递归写法 :
(1). key 值比 cur->_val 小，去 cur 的左边去找
(2). key值比 cur->_val 大，去 cur 的右边去找
(3). 找到返回 cur，没找到返回 nullptr

Node* Find(const K& key)
{
	Node* cur = _root;
	while (cur)
	{
		// key 值比 cur->_val 小，去 cur 的左边去找
		if (key < cur->_key) cur = cur->_left;
		// key值比 cur->_val 大，去 cur 的右边去找
		else if (key > cur->_key) cur = cur->_right;
		// 找到返回 cur
		else return cur;
	}
	// 没找到返回 nullptr
	return nullptr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

查找操作递归写法 :
(1). root 为空时，说明没有找到，返回 nullptr 即可
(2). key 值比 cur->_key 小，递归去 root 的左边去找
(3). key 值比 cur->_key 大，递归去 root 的右边去找
(4). 找到了返回 root

Node* _FindR(Node* root, const K& key)
{
	// 没找到
	if (root == nullptr)
		return nullptr;
	// key 值比 cur->_key 小
	if (key < root->_key) _FindR(root->_left, key);
	// key 值比 cur->_key 大
	else if (key > root->_key) _FindR(root->_right, key);
	// 找到了
	else return root;
}
Node* FindR(const K& key)
{
	return _FindR(_root,key);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

(6). 删除操作

删除操作非递归写法 :
(1). 删除的是叶子节点或只有一个孩子的父节点
根据删除节点和父节点的大小关系，让父节点的 _left 或 _right 指向删除节点的左右孩子中不为空的节点(叶子节点则指向空)，最后删除该节点
(2). 删除的是有两个孩子的父节点
先找到能够替代该节点值的节点值，可以为左子树的最右节点值，右子树的最左节点值，这样就可以把问题转换成(1)

bool Erase(const K& key)
{
	Node* parent = nullptr, * cur = _root;
	while (cur)
	{
		if (key < cur->_key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (key > cur->_key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			// 删除叶子节点和只有一个孩子的父节点
			if (cur->_left == nullptr || cur->_right == nullptr)
			{
				if (cur->_key < parent->_key) 
					parent->_left = (cur->_left != nullptr) ? cur->_left : cur->_right;
				else
					parent->_right = (cur->_left != nullptr) ? cur->_left : cur->_right;
				delete cur;
			}
			// 删除有两个孩子的父节点
			else
			{
				Node* p = cur, * c = cur->_left;
				// 找到左子树的最右节点
				while (c->_right)
				{
					p = c;
					c = c->_right;
				}
				// 转换成问题(1)
				if (c->_val < p->_val)
					p->_left = c->_left;
				else
					p->_right = c->_left;
				// 将节点的值进行替换
				cur->_val = c->_val;
				// 删除节点，释放内存
				delete c;
			}
			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

删除操作递归写法 :

bool _EraseR(Node*& root,const K& key)
{
	if (root == nullptr)
		return false;
	if (key < root->_key) return _EraseR(root->_left, key);
	else if (key > root->_key) return _EraseR(root->_right,key);
	else
	{
		if (root->_left == nullptr || root->_right == nullptr)
		{
			Node* tmp = root;
			root = (root->_left != nullptr) ? root->_left : root->_right;
			delete tmp;
		}
		else
		{
			Node* cur = root->_left;
			while (cur->_right) cur = cur->_right;
			root->_val = cur->_val;
			_EraseR(root->_left,cur->_val);
		}
		return true;
	}
}
bool EraseR(const K& key)
{
	return _EraseR(_root,key);
}
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

(6). 析构函数

void Destory()
{
	_Destory(_root);
}
void _Destory(Node* root)
{
	if (root == nullptr)
		return;
	_Destory(root->_left);
	_Destory(root->_right);
	delete root;
}
~BSTree()
{
	Destory();
	_root = nullptr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

三.二叉搜索树的应用

(1). K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
以单词集合中的每个单词作为key，构建一棵二叉搜索树
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

(2). KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。
比如：实现一个简单的英汉词典dict，可以通过英文找到与其对应的中文，具体实现方式如下：
<单词，中文含义>为键值对构造二叉搜索树，注意：二叉搜索树需要比较，键值对比较时只比较
Key查询英文单词时，只需给出英文单词，就可快速找到与其对应的key

K模型代码实现
KV模型代码实现