二叉查找树

二叉查找树(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;
}