玩技术,Geeker
一个原创技术文章分享网站

C++实现二叉查找树

啥是二叉查找树

在数据结构中,有一个奇葩的东西,说它奇葩,那是因为它重要,这就是树。而在树中,二叉树又是当中的贵族。二叉树的一个重要应用是它们在查找中的应用,于是就有了二叉查找树。 使二叉树成为一颗二叉查找树,需要满足以下两点:

  1. 对于树中的每个节点X,它的左子树中所有项的值都要小于X中的项;
  2. 对于树中的每个节点Y,它的右子树中所有项的值都要大于Y中的项。

二叉查找树的基本操作

以下是对于二叉查找树的基本操作定义类,然后慢慢分析是如何实现它们的。

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,它的右子树中所有项的值都要大于Y中的项。

我们可以从root节点开始:

  1. 一直沿着左节点往下找,直到子节点等于NULL为止,这样就可以找到最小值了;
  2. 一直沿着右节点往下找,直到子节点等于NULL为止,这样就可以找到最大值了。

如下图所示: alt

在程序中实现时,有两种方法:

  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函数用来删除二叉查找树中指定的元素值,这个处理起来比较麻烦。在删除子节点时,需要分以下几种情况进行考虑(结合下图进行说明): 如下图所示: alt

  1. 需要删除的子节点,它没有任何子节点;例如图中的节点9、节点17、节点21、节点56和节点88;这些节点它们都没有子节点;
  2. 需要删除的子节点,只有一个子节点(只有左子节点或右子节点);例如图中的节点16和节点40;这些节点它们都只有一个子节点;
  3. 需要删除的子节点,同时拥有两个子节点;例如图中的节点66等。

对于情况1,直接删除对应的节点即可;实现起来时比较简单的;

对于情况2,直接删除对应的节点,然后用其子节点占据删除掉的位置;

对于情况3,是比较复杂的。首先在需要被删除节点的右子树中找到最小值节点,然后使用该最小值替换需要删除节点的值,然后在右子树中删除该最小值节点。
假如现在需要删除包含值23的节点,步骤如下图所示: alt

代码实现如下:

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平衡树和红黑树的基础,希望这篇文章对大家有帮助。 这里提供文中所有代码的下载:源码下载

点击下载全文(PDF格式)

2014年10月23日 于深圳。

打赏

未经允许不得转载:果冻想 » C++实现二叉查找树

分享到:更多 ()

评论 15

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #8

    remove的例子有问题,remove 23后,右子树最小的应该是40, 不是56。

    weibest3年前 (2014-11-02)回复
    • 恩。的确有问题,谢谢你的提出,已经修改。

      果冻想3年前 (2014-11-05)回复
  2. #7

    感觉查找树最麻烦的就是删除结点了>,

    hypo3年前 (2014-11-22)回复
    • 恩,删除分三种情况了:1.没有节点;2.一个节点;3.两个节点了。就是删除比较麻烦的。

      果冻想3年前 (2014-11-22)回复
  3. #6

    面霸网到此一游 http://www.51mx.org

    面霸网3年前 (2015-03-24)回复
  4. #5

    写得非常非常的赞啊。www.51mx.org

    面霸网3年前 (2015-03-24)回复
  5. #4

    remove实现中57的右节点中有比其小的56,这不太合理吧

    Hunter2年前 (2015-04-14)回复
    • 恩,的确是,谢谢你提出的问题。我已经更改了示例图。

      果冻想2年前 (2015-04-14)回复
  6. #3

    [太开心]

    面霸网2年前 (2015-11-18)回复
  7. #2

    很赞,示例图做的好棒!请教博主是图用什么画的?谢谢~

    示例图尤其赞2年前 (2016-01-04)回复
    • 我用的是这个在线工具:https://www.processon.com/

      果冻想2年前 (2016-01-04)回复
  8. #1

    源码已失效

    xx1个月前 (08-17)回复

在这里玩技术,享受技术带来的疯狂

捐赠名单关于果冻