二叉查找树

Posted on | In

二叉查找树（Binary Search Tree）是一种特殊的二叉树，通常应用于动态数据的查找。

二叉查找树具有以下特性：

  • 若左子树不为空，则左子树的值小于它的根节点的值；
  • 若右子树不为空，则右子树的值大于它的根节点的值；
  • 任意节点的左右子树均为二叉查找树；
  • 没有键值相等的节点。

二叉查找树的表示

由BST特性可知，BST是一个递归的数据结构，且中序遍历BST，可以得到一个递增的有序序列。

BST的节点定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<class T>
class BSTNode{
public:
    BSTNode(const T &e, BSTNode *l = NULL, BSTNode *r = NULL, BSTNode *p = NULL)：
    {
        data_ = e;
        left_child_ = l;
        right_child_ = r;
        parent_ = p;
    }
    
public:
	T element_;
	BSTNode *left_;
	BSTNode *right_;
	BSTNode *parent_;
};

二叉查找树（BSTree）定义如下：

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
template<class T>
class BSTree{
public:
	BSTree() : root_(NULL) {}
	~BSTree() { delete root_; }
	// 插入值
	bool Insert(T dat) const;
	
	// 搜索值
	BSTNode<T>* Search(T dat) const;
	
	// 前序遍历
	void PreOrder();
	// 中序遍历
	void InOrder();
	// 后序遍历
	void PostOrder();
	// 查找最小结点：返回最小结点的元素
	T Minimum();
	// 查找最大结点：返回最大结点的元素
	T Maximum();
	// 找结点(x)的后继结点。即，查找"二叉树中数据值大于该结点"的"最小结点"。
	BSTNode<T>* Successor(BSTNode<T> *x);
	// 找结点(x)的前驱结点。即，查找"二叉树中数据值小于该结点"的"最大结点"。
	BSTNode<T>* Predecessor(BSTNode<T> *x);
	// 删除结点(key为节点元素)
	void Remove(T key);
	// 销毁二叉树
	void Destroy();
private:
    BSTNode<T> *root_;
};

二叉查找树的插入

二叉查找树插入的基本思路为：若二叉查找树为空，则直接插入，若不为空，则关键值小于根节点的插入至其左子树中，关键值大于根节点的插入至其右子树中。

1
2
3
4
5
6
7
8
9
10
// 插入值
template<class T>
bool BSTree<T>::Insert(T dat) const
{
	BSTNode<T> *node = new BSTNode<T>(dat);
	if (node == NULL)
		return false;
	return IterativeInsert((BSTNode<T>*&)root_, node);
}
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
// 非递归实现
template<class T>
bool BSTree<T>::IterativeInsert(BSTNode<T>* &tree, BSTNode<T> *node) const
{
	BSTNode<T> *cur_par = NULL;
	BSTNode<T> *cur = tree;
	while (cur != NULL) {
		cur_par = cur;
		if (node->element_ == cur->element_)
			return false;
		else if (node->element_ < cur->element_)
			cur = cur->left_;
		else
			cur = cur->right_;
	}
	node->parent_ = cur_par;
	if (cur_par == NULL)
		tree = node;
	else if (node->element_ < cur_par->element_)
		cur_par->left_ = node;
	else
		cur_par->right_ = node;
}

二叉查找树的查找

二叉查找树除了Search（查找）操作外，通常还支持Minimun（最小值）、Maximum（最大值）、Predecessor（前驱）、Successor（后继）等操作。

1. Search（查找）

从根节点开始，若二叉树非空，给定值与根节点的值比较，若不相等，则根据左小右大原则继续查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
template<class T>
BSTNode<T>* BSTree<T>::Search(T dat) const
{
	if (root_->element_ == dat) {
		std::cout << root_ << std::endl;
		return root_;
	}
	if (dat < root_->element_)
		Search(dat, root_->left_);
	else
		Search(dat, root_->right_);
}

递归实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
template<class T>
BSTNode<T>* BSTree<T>::Search(T dat, BSTNode<T>* node) const
{
	if (node == NULL || node->element_ == dat) {
		std::cout << node << std::endl;
		return node;
	}
	if (dat < node->element_)
		Search(dat, node->left_);
	else
		Search(dat, node->right_);
}

非递归实现如下：

1
2
3
4
5
6
7
8
9
10
11
template<class T>
inline BSTNode<T>* BSTree<T>::iterativeSearch(BSTNode<T>* node, T dat) const
{
	while (node != NULL || node->element_ != dat) {
		if (dat < node->element_)
			node = node->left_;
		else
			node = node->right_;
	}
	return node;
}

2. Minimun（最小值）

根据二叉查找树的规则，树中最小值应当位于最左的节点，且该节点不能有左子树，代码如下：

1
2
3
4
5
6
7
8
 template<class T>
inline T BSTree<T>::Minimum()
{
	BSTNode<T> *p = Minimum(root_);
	if (p != NULL)
		return p->element_;
	return T(NULL);
}

3. Maximum（最大值）

根据二叉查找树的规则，树中最小值应当位于最右的节点，且该节点不能有右子树。

1
2
3
4
5
6
7
8
template<class T>
inline T BSTree<T>::Maximum()
{
	BSTNode<T> *p = Maximum(root_);
	if (p != NULL)
		return p->element_;
	return T(NULL);
}

4. Predecessor（前驱）

找结点(x)的前驱结点。即，查找”二叉树中数据值小于该结点”的”最大结点”。

找到某个节点的前驱节点，返回为前驱或者Null。存在两种情况：

  • 若节点x的左子树非空，则x的左子树中最右的节点为其前驱
  • 若x的左子树为空，且x有一个前驱y，则y是x的最低祖先节点，且y的右儿子也是x的祖先，针对的是中序遍历下的前驱
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<class T>
inline BSTNode<T>* BSTree<T>::Predecessor(BSTNode<T>* x)
{
	// 如果x存在左孩子，则"x的前驱节点"为 "以其左孩子为根的子树的最大结点"。
	if (x->left_ != NULL)
		return Maximum(x->left_);
	// 如果x没有左孩子。则x有以下两种可能：
	// 1. x没有前驱节点
	// 2. x有一个前驱y，则y是x的最低祖先节点，且y的右儿子也是x的祖先
	BSTNode<T>* y = x->parent_;
	while ((y != NULL) && (x == y->left_)){
		x = y;
		y = y->parent_;
	}
	return y;
}

5. Successor（后继）

找到某个节点的后继节点，返回为后继或者null。存在两种情况：

找结点(x)的后继结点。即，查找”二叉树中数据值大于该结点”的”最小结点”。

  • 若节点x的右子树非空，则x的右子树中最左的节点为其后继
  • 若x的右子树为空，且x有一个后继y，则y是x的最低祖先节点，且y的左儿子也是x的祖先，针对的是中序遍历下的后继
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<class T>
inline BSTNode<T>* BSTree<T>::Successor(BSTNode<T>* x)
{
	if (x->right_ != NULL)
		return Minimum(x->right_);
	BSTNode<T>* y = x->parent_;
	while ((y != NULL) && (x == y->right_)){
		x = y;
		y = y->parent_;
	}
	return y;
}

二叉查找树删除

二叉查找树的删除分为三种情况：

  • 若被删除节点为叶子节点，则直接删除，不会影响二叉查找树的特性；
  • 若节点node只有左子树或者右子树，则让node的子树成为node父节点的子树，代替node的位置；
  • 若节点既有左子树又有右子树，则用node的后继（Successor）的值代替node的值，然后从二叉树中删除这个后继，这样就转换成第一或第二种情况。
1
2
3
4
5
6
7
8
9
template<class T>
inline void BSTree<T>::Remove(T key)
{
	BSTNode<T> *z, *node;
	if ((z = Search(root_, key)) != NULL)
		if ((node = Remove(root_, z)) != NULL)
			delete node;
}
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
/*
* 基于后继，进行删除节点, 主要分两种情况：
* 1）若没有子女，则直接删除，
* 2）若只有一个子女，则删除本身
* 3）若有两个子女，则删除其后继y，y最多只有一个子女，最后，用Y中的关键字和其它数据替换掉z中关键字和其它数据
*/
template<class T>
inline BSTNode<T>* BSTree<T>::Remove(BSTNode<T>*& tree, BSTNode<T>* z)
{
	BSTNode<T> *x = NULL;
	BSTNode<T> *y = NULL;
	if ((z->left_ == NULL) || (z->right_ == NULL))
		y = z;
	else
		y = Successor(z);
	if (y->left_ != NULL)
		x = y->left_;
	else
		x = y->right_;
	if (x != NULL)
		x->parent_ = y->parent_;
	if (y->parent_ == NULL)
		tree = x;
	else if (y == y->parent_->left_)
		y->parent_->left_ = x;
	else
		y->parent_->right_ = x;
	if (y != z)
		z->element_ = y->element_;
	return y;
}

二叉查找树销毁

二叉查找树销毁原理也很简单，使用递归，遍历每一个节点，将其销毁便可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<class T>
inline void BSTree<T>::Destroy(BSTNode<T>*& tree)
{
	if (tree == NULL)
		return;
	if (tree->left_ != NULL)
		return Destroy(tree->left_);
	if (tree->right_ != NULL)
		return Destroy(tree->right_);
	delete tree;
	tree = NULL;
}

二叉查找树求深度

1. 递归求法

递归求二叉树深度比较简单，直接上代码：

1
2
3
4
5
6
7
8
9
10
11
12
// 获取二叉树深度，递归求法
template<class T>
inline int BSTree<T>::GetDeepth(BSTNode<T>* tree) const
{
	if (tree == NULL)
		return 0;
	int left = GetDeepth(tree->left_);
	int right = GetDeepth(tree->right_);
	return std::max(left, right) + 1;
}

2. 非递归求法

经典的非递归遍历，利用队列（std::queue），先将头节点入队列，若队列不为空，记出队列的节点为cur_node，若cur_node的左节点不为空，则入队列，若cur_node右节点不为空也入队列，如此循环。

此方法也可同时求树的最大宽度，以及访问某一层某一列的节点。

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
// 获取二叉树深度，非递归求法
template<class T>
inline int BSTree<T>::iterativeGetDeepth(BSTNode<T>* tree) const
{
	using std::queue;
	using std::size_t;
	queue<BSTNode<T>*> width_queue;
	size_t deepth = 0;
	size_t width, max_width = 0;
	width_queue.push(tree);
	while (!width_queue.empty()) {
		width = width_queue.size();
		max_width = width > max_width ? width : max_width;	// 获取二叉树最大宽度
		for (size_t i = 0; i < width; i++) {
			BSTNode<T>* cur_node = width_queue.front();
			width_queue.pop();
			if (cur_node->left_ != NULL)
				width_queue.push(cur_node->left_);
			if (cur_node->right_ != NULL)
				width_queue.push(cur_node->right_);
		}
		deepth++;
	}
	return deepth;
}