搜索二叉树概念

搜索二叉树作为一种树型结构，他和普通二叉树有如下几种区别：
搜索二叉树的左子树，如果不为空的情况下，左子树上面所有节点的值都小于根节点
搜索二叉树的右子树，如果不为空的情况下，右子树上面所有节点的值都大于根节点
这个性质可以适用于该搜索二叉树的任意节点。
这样看来对于一个搜索二叉树的中序遍历，即可实现从小到大遍历该二叉树中的所有节点

实现搜索二叉树

构成

搜索二叉树节点的结构体和正常二叉树相同，都是由左右节点指针和其中存放的key值构成的，但是搜索二叉树还有key-value版本的下一篇博客进行实现。

template<class K>
struct BSTreeNode
{
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;
	BSTreeNode(const K& key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{

	}
};
template<class K>
struct BSTree
{
	typedef BSTreeNode<K> Node;
public:
	BSTree()
		:_root(nullptr)
	{

	}
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

插入

搜索二叉树的插入和正常二叉树插入方式的区别就在于需要找到插入节点对应的位置，即判断该节点中存放的值与根节点的大小，来判断插入左子树还是右子树中。
这里分别使用了非递归和递归来实现搜索二叉树插入节点的操作

bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}
		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
			{
				return false;
			}
		}
		cur = new Node(key);
		if (parent->_key > key)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = 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

	bool InsertR(const K& key)
	{
		return _InsertR(_root, key);
	}
	bool _InsertR(Node*& root, const K& key)
	{

		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}
		if (root->_key < key)
		{
			return _InsertR(root->_right, key);
		}
		else if (root->_key > key)
		{
			return _InsertR(root->_left, key);
		}
		else
		{
			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

中序遍历

这里的中序遍历方法和普通二叉树一样，使用递归即可

	void InOrder()
	{
		_InOrder(_root);
	}
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->_left);
		std::cout << (root->_key) << " ";
		_InOrder(root->_right);
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

使用如下代码进行测试

void TestBSTree()
{
	BSTree<int> t;
	int a[] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };
	for (auto e : a)
	{
		t.InsertR(e);
	}
	t.InOrder();
	std::cout << std::endl;
}
1
2
3
4
5
6
7
8
9
10
11

这里可以看到按顺序输出了二叉树中的值

查找

这里在搜索二叉树中查找一个值时，只需要判断需要查找的值与根节点中的值的大小，便可以判断进入左子树还是右子树中查找，如果非极端情况下，可以以log2n的时间复杂度进行数据查找，下面还是以递归和非递归两种来实现查找功能

bool 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 true;
			}
		}
		return false;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Node* FindR(Node* root,const K& key)//递归查找
	{
		return _FindR(root, key);
	}
Node* _FindR(Node* root, const K& key)//递归查找
	{
		if (_root == nullptr)
		{
			return nullptr;
		}
		if (_root->_key < key)
		{
			return _FindR(_root->_right, key);
		}
		else if (_root->_key > key)
		{
			return _FindR(_root->_left, key);
		}
		else
		{
			return _root;
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

删除

搜索二叉树中删除会比较麻烦一点。这里的删除有3种情况
1、 需要删除的节点，该节点是叶子节点，那么直接删除即可
2、 需要删除的节点左子树或者右子树其中一个为空，那么将不为空的子树和删除节点的父节点链接即可
3、 需要删除的节点左右子树都不为空。这种情况就比较复杂。需要用被删除节点的左子树中的最右节点或者右子树中的最左节点来与该节点值进行替换，这样可以保证搜索二叉树的性质。具体操作如下：

	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 (parent == nullptr)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_right;
						}
						else
						{
							parent->_right = cur->_right;
						}
					}

					delete cur;
				}
				else if(cur->_right == nullptr)
				{
					if (parent == nullptr)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}

					delete cur;

				}
				else
				{
					Node* minparent = cur;
					Node* min = cur->_right;
					while (min->_left)
					{
						minparent = min;
						min = min->_left;
					}
					cur->_key = min->_key;
					if (minparent->_left == min)
					{
						minparent->_left = min->_right;
					}
					else
					{
						minparent->_right = min->_right;
					}
					delete min;
				}
				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

递归实现：

	bool EraseR(const K& key)
	{
		return _EraseR(_root, key);
	}
		bool _EraseR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			return false;
		}
		if (root->_key < key)
		{
			return _EraseR(root->_right, key);
		}
		else if (root->_key > key)
		{
			return _EraseR(root->_left, key);
		}
		else
		{
			Node* del = root;
			if (root->_left == nullptr)
			{
				root = root->_right;
			}
			else if (root->_right == nullptr)
			{
				root = root->_left;
			}
			else
			{
				Node* min = root->_right;
				while (min->_left)
				{
					min = min->_left;
				}
				std::swap(min->_key, root->_key);
				//递归到右子树删除
				return _EraseR(root->_right, key);
			}
			delete del;
			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
38
39
40
41
42
43
44

测试代码如下：

void TestBSTree()
{
	BSTree<int> t;
	int a[] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };
	for (auto e : a)
	{
		t.InsertR(e);
	}
	t.InOrder();
	std::cout << std::endl;

	//排序加去重
	t.EraseR(7);
	t.InOrder();
	std::cout << std::endl;

	t.Erase(5);
	t.InOrder();
	std::cout << std::endl;


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22