一聚教程网:一个值得你收藏的教程网站

热门教程

C++实现二叉查找树过程详解教程【图】

时间:2022-06-25 04:53:06 编辑:袖梨 来源:一聚教程网

什么是二叉查找树

二叉树是每个结点最多有两个子树的有序树。二叉树常被用于实现二叉查找树和二叉堆。值得注意的是,二叉树不是树的特殊情形。在图论中,二叉树是一个连通的无环图,并且每一个顶点的度不大于2。有根二叉树还要满足根结点的度不大于2。有了根结点后,每个顶点定义了唯一的根结点,和最多2个子结点。然而,没有足够的信息来区分左结点和右结点。使二叉树成为一颗二叉查找树,需要满足以下两点:

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

二叉查找树的基本操作

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

 代码如下 复制代码

    template
    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 *root;
        void insert(const T &x, BinaryNode *&t) const;
        void remove(const T &x, BinaryNode *&t) const;
        BinaryNode *findMin(BinaryNode *t) const;
        BinaryNode *findMax(BinaryNode *t) const;
        bool contains(const T &x, BinaryNode *t) const;
        void printTree(BinaryNode *t) const;
        void makeEmpty(BinaryNode *&t) const;
    };


findMin和findMax实现

根据二叉查找树的性质:

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

我们可以从root节点开始:

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

如下图所示:

C++二叉查找树实现过程详解


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

1.使用递归实现;
2.使用非递归的方式实现。

对于finMin的实现,我这里使用递归的方式,代码参考如下:

 代码如下 复制代码

    BinaryNode *BinarySearchTree::findMin(BinaryNode *t) const
    {
        if (t == NULL)
        {
            return NULL;
        }
        else if (t->left == NULL)
        {
            return t;
        }
        else
        {
            return findMin(t->left);
        }
    }


在findMin()的内部调用findMin(BinaryNode *t),这样就防止了客户端知道了root根节点的信息。上面使用递归的方式实现了查找最小值,下面使用循环的方式来实现findMax。

 代码如下 复制代码

    template
    BinaryNode *BinarySearchTree::findMax(BinaryNode *t) const
    {
        if (t == NULL)
        {
            return NULL;
        }
        while (t->right)
        {
            t = t->right;
        }
        return t;
    }


在很多面试的场合下,面试官一般都是让写出非递归的版本;而在对树进行的各种操作,很多时候都是使用的递归实现的,所以,在平时学习时,在理解递归版本的前提下,需要关心一下对应的非递归版本。

contains实现

contains用来判断二叉查找树是否包含指定的元素。代码实现如下:

 代码如下 复制代码

    template
    bool BinarySearchTree::contains(const T &x, BinaryNode *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
    void BinarySearchTree::insert(const T &x, BinaryNode *&t) const
    {
        if (t == NULL)
        {
            t = new BinaryNode(x, NULL, NULL);
        }
        else if (x < t->element)
        {
            insert(x, t->left);
        }
        else if (x > t->element)
        {
            insert(x, t->right);
        }
    }


remove实现

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

 

C++二叉查找树实现过程详解

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

对于情况1,直接删除对应的节点即可;实现起来时比较简单的;
对于情况2,直接删除对应的节点,然后用其子节点占据删除掉的位置;
对于情况3,是比较复杂的。首先在需要被删除节点的右子树中找到最小值节点,然后使用该最小值替换需要删除节点的值,然后在右子树中删除该最小值节点。
假如现在需要删除包含值23的节点,步骤如下图所示:

C++二叉查找树实现过程详解

代码实现如下:

 代码如下 复制代码

    template
    void BinarySearchTree::remove(const T &x, BinaryNode *&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平衡树和红黑树的基础,希望这篇文章对大家有帮助。

 

热门栏目