|
什么是二叉查找树
二叉树是每个结点最多有两个子树的有序树。二叉树常被用于实现二叉查找树和二叉堆。值得注意的是，二叉树不是树的特殊情形。在图论中，二叉树是一个连通的无环图，并且每一个顶点的度不大于2。有根二叉树还要满足根结点的度不大于2。有了根结点后，每个顶点定义了唯一的根结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。使二叉树成为一颗二叉查找树，需要满足以下两点：
1.对于树中的每个节点X，它的左子树中所有项的值都要小于X中的项；
2.对于树中的每个节点Y，它的右子树中所有项的值都要大于X中的项。
二叉查找树的基本操作
以下是对于二叉查找树的基本操作定义类，然后慢慢分析是如何实现它们的。
| 代码如下 |
复制代码 |
template<class T>
class BinarySearchTree
{
public:
// 构造函数，初始化root值
BinarySearchTree() : root(NULL){}
// 析构函数，默认实现
~BinarySearchTree() {}
// 查找最小值，并返回最小值
const T &findMin() const;
// 查找最大值，并返回最大值
const T &findMax() const;
// 判断二叉树中是否包含指定值的元素
bool contains(const T &x) const;
// 判断二叉查找树是否为空
bool isEmpty() const { return root ? false : true; }
// 打印二叉查找树的值
void printTree() const;
// 向二叉查找树中插入指定值
void insert(const T &x);
// 删除二叉查找树中指定的值
void remove(const T &x);
// 清空整个二叉查找树
void makeEmpty() const;
private:
// 指向根节点
BinaryNode<T> *root;
void insert(const T &x, BinaryNode<T> *&t) const;
void remove(const T &x, BinaryNode<T> *&t) const;
BinaryNode<T> *findMin(BinaryNode<T> *t) const;
BinaryNode<T> *findMax(BinaryNode<T> *t) const;
bool contains(const T &x, BinaryNode<T> *t) const;
void printTree(BinaryNode<T> *t) const;
void makeEmpty(BinaryNode<T> *&t) const;
}; |
findMin和findMax实现
根据二叉查找树的性质：
1.对于树中的每个节点X，它的左子树中所有项的值都要小于X中的项；
2.对于树中的每个节点Y，它的右子树中所有项的值都要大于X中的项。
我们可以从root节点开始：
1.一直沿着左节点往下找，直到子节点等于NULL为止，这样就可以找到最小值了；
2.一直沿着右节点往下找，直到子节点等于NULL为止，这样就可以找到最大值了。
如下图所示：
在程序中实现时，有两种方法：
1.使用递归实现；
2.使用非递归的方式实现。
对于finMin的实现，我这里使用递归的方式，代码参考如下：
| 代码如下 |
复制代码 |
BinaryNode<T> *BinarySearchTree<T>::findMin(BinaryNode<T> *t) const
{
if (t == NULL)
{
return NULL;
}
else if (t->left == NULL)
{
return t;
}
else
{
return findMin(t->left);
}
} |
在findMin()的内部调用findMin(BinaryNode<T> *t)，这样就防止了客户端知道了root根节点的信息。上面使用递归的方式实现了查找最小值，下面使用循环的方式来实现findMax。
| 代码如下 |
复制代码 |
template<class T>
BinaryNode<T> *BinarySearchTree<T>::findMax(BinaryNode<T> *t) const
{
if (t == NULL)
{
return NULL;
}
while (t->right)
{
t = t->right;
}
return t;
} |
在很多面试的场合下，面试官一般都是让写出非递归的版本；而在对树进行的各种操作，很多时候都是使用的递归实现的，所以，在平时学习时，在理解递归版本的前提下，需要关心一下对应的非递归版本。
contains实现
contains用来判断二叉查找树是否包含指定的元素。代码实现如下：
| 代码如下 |
复制代码 |
template<class T>
bool BinarySearchTree<T>::contains(const T &x, BinaryNode<T> *t) const
{
if (t == NULL)
{
return false;
}
else if (x > t->element)
{
return contains(x, t->right);
}
else if (x < t->element)
{
return contains(x, t->left);
}
else
{
return true;
}
} |
算法规则如下：
1.首先判断需要查找的值与当前节点值的大小关系；
2.当小于当前节点值时，就在左节点中继续查找；
3.当大于当前节点值时，就在右节点中继续查找；
4.当找到该值时，直接返回true。
insert实现
insert函数用来向儿茶查找树中插入新的元素，算法处理如下：
1.首先判断需要插入的值域当前节点值得大小关系；
2.当小于当前节点值时，就在左节点中继续查找插入点；
3.当大于当前节点值时，就在右节点中继续查找插入点；
4.当等于当前节点值时，什么也不干。
代码实现如下：
| 代码如下 |
复制代码 |
template<class T>
void BinarySearchTree<T>::insert(const T &x, BinaryNode<T> *&t) const
{
if (t == NULL)
{
t = new BinaryNode<T>(x, NULL, NULL);
}
else if (x < t->element)
{
insert(x, t->left);
}
else if (x > t->element)
{
insert(x, t->right);
}
} |
remove实现
remove函数用来删除二叉查找树中指定的元素值，这个处理起来比较麻烦。在删除子节点时，需要分以下几种情况进行考虑（结合下图进行说明）： 如下图所示：
1.需要删除的子节点，它没有任何子节点；例如图中的节点9、节点17、节点21、节点56和节点88；这些节点它们都没有子节点；
2.需要删除的子节点，只有一个子节点（只有左子节点或右子节点）；例如图中的节点16和节点40；这些节点它们都只有一个子节点；
3.需要删除的子节点，同时拥有两个子节点；例如图中的节点66等。
对于情况1，直接删除对应的节点即可；实现起来时比较简单的；
对于情况2，直接删除对应的节点，然后用其子节点占据删除掉的位置；
对于情况3，是比较复杂的。首先在需要被删除节点的右子树中找到最小值节点，然后使用该最小值替换需要删除节点的值，然后在右子树中删除该最小值节点。
假如现在需要删除包含值23的节点，步骤如下图所示：
代码实现如下：
| 代码如下 |
复制代码 |
template<class T>
void BinarySearchTree<T>::remove(const T &x, BinaryNode<T> *&t) const
{
if (t == NULL)
{
return;
}
if (x < t->element)
{
remove(x, t->left);
}
else if (x > t->element)
{
remove(x, t->right);
}
else if (t->left != NULL && t->right != NULL)
{
// 拥有两个子节点
t->element = findMin(t->right)->element;
remove(t->element, t->right);
}
else if (t->left == NULL && t->right == NULL)
{
// 没有子节点，直接干掉
delete t;
t = NULL;
}
else if (t->left == NULL || t->right == NULL)
{
// 拥有一个子节点
BinaryNode *pTemp = t;
t = (t->left != NULL) ? t->left : t->right;
delete pTemp;
}
} |
makeEmpty实现
makeEmpty函数用来释放整个二叉查找树占用的内存空间，同理，也是使用的递归的方式来实现的。具体代码请下载文中最后提供的源码。
总结
这篇文章对数据结构中非常重要的二叉查找树进行了详细的总结，虽然二叉查找树非常重要，但是理解起来还是非常容易的，主要是需要掌握对递归的理解。如果对递归有非常扎实的理解，那么对于树的一些操作，那都是非常好把握的，而理解二叉查找树又是后续的AVL平衡树和红黑树的基础，希望这篇文章对大家有帮助。
|
