第九章

二叉搜索树

9.1 基本概念

二叉树的一个重要的应用是它们在查找中的使用。二叉搜索树的概念相当容易理解，即：对于树中的每个结点X，它的左子树中所有关键字的值都小于X的关键字值，而它的右子树中的所有关键字值都大于X的关键字值。这意味着该树所有的元素都可以用某种统一的方式排序。

例如下面就是一棵合法的二叉搜索树：

二叉搜索树的性质决定了它在搜索方面有着非常出色的表现：要找到一棵树的最小结点，只需要从根结点开始，只要有左儿子就向左进行，终止结点就是最小的结点。找最大的结点则是往右进行。例如上面的例子中，最小的结点是1，在最左边；最大的结点是8，在最右边。

9.2 代码实现

二叉树的代码实现如下：

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   bstree.h
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-17 22:53:52
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#ifndef __BINARY_SEARCH_TREE_H__
#define __BINARY_SEARCH_TREE_H__

#include "../../btree/src/btree.h"

template<typename T>
class CBSTree : public CBTree<T>
{
private:
    CBTNode<T>* Find(const T &data, CBTNode<T> *p) const;
    CBTNode<T>* FindMin(CBTNode<T> *p) const;
    CBTNode<T>* FindMax(CBTNode<T> *p) const;
    CBTNode<T>* Insert(const T &data, CBTNode<T> *p);
    CBTNode<T>* Delete(const T &data, CBTNode<T> *p);

public:
    CBTNode<T>* Find(const T &data) const;
    CBTNode<T>* FindMin() const;
    CBTNode<T>* FindMax() const;
    CBTNode<T>* Insert(const T &data);
    CBTNode<T>* Delete(const T &data);
};

template<typename T>
inline CBTNode<T>* CBSTree<T>::Find(const T &data) const
{
    return Find(data, m_pNodeRoot);
}

template<typename T>
inline CBTNode<T>* CBSTree<T>::Find(const T &data, CBTNode<T> *p) const
{
    if (NULL == p)
        return NULL;
    if (data < p->data)
        return Find(data, p->left);
    else if (data > p->data)
        return Find(data, p->right);
    else
        return p;
}

template<typename T>
inline CBTNode<T>* CBSTree<T>::FindMin() const
{
    return FindMin(m_pNodeRoot);
}

template<typename T>
inline CBTNode<T>* CBSTree<T>::FindMin(CBTNode<T> *p) const
{
    if (NULL == p)
        return NULL;
    else if (NULL == p->left)
        return p;
    else
        return FindMin(p->left);
}

template<typename T>
inline CBTNode<T>* CBSTree<T>::FindMax() const
{
    return FindMax(m_pNodeRoot);
}

template<typename T>
inline CBTNode<T>* CBSTree<T>::FindMax(CBTNode<T> *p) const
{
    if (NULL == p)
        return NULL;
    else if (NULL == p->right)
        return p;
    else
        return FindMax(p->right);
}

template<typename T>
inline CBTNode<T>* CBSTree<T>::Insert(const T &data)
{
    return Insert(data, m_pNodeRoot);
}

template<typename T>
inline CBTNode<T>* CBSTree<T>::Insert(const T &data, CBTNode<T> *p)
{
    if (NULL == p)
    {
        p = new CBTNode<T>;
        if (NULL == p)
            return NULL;
        else
        {
            p->data = data;
            p->left = NULL;
            p->right = NULL;
            if (NULL == m_pNodeRoot)
            {
                m_pNodeRoot = p;
                m_pNodeRoot->parent = NULL;
            }
        }
    }
    else if (data < p->data)
    {
        p->left = Insert(data, p->left);
        if (p->left)
            p->left->parent = p;
    }
    else if (data > p->data)
    {
        p->right = Insert(data, p->right);
        if (p->right)
            p->right->parent = p;
    }
    // else data is in the tree already, we'll do nothing!

    return p;
}

template<typename T>
inline CBTNode<T>* CBSTree<T>::Delete(const T &data)
{
    return Delete(data, m_pNodeRoot);
}

template<typename T>
inline CBTNode<T>* CBSTree<T>::Delete(const T &data, CBTNode<T> *p)
{
    if (NULL == p)
    {
        // Error! data not found!
    }
    else if (data < p->data)
    {
        p->left = Delete(data, p->left);
    }
    else if (data > p->data)
    {
        p->right = Delete(data, p->right);
    }
    else if (p->left && p->right)   // found it, and it has two children
    {
        CBTNode<T> *pTmp = FindMin(p->right);
        p->data = pTmp->data;
        p->right = Delete(p->data, p->right);
    }
    else    // found it, and it has one or zero children
    {
        CBTNode<T> *pTmp = p;
        if (NULL == p->left)
            p = p->right;
        else if (NULL == p->right)
            p = p->left;

        if (p)
            p->parent = pTmp->parent;

        if (m_pNodeRoot == pTmp)
            m_pNodeRoot = p;

        delete pTmp;
    }

    return p;
}

#endif  // __BINARY_SEARCH_TREE_H__

测试代码：

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   bstree.cpp
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-17 22:55:12
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#include "bstree.h"

int main()
{
    CBSTree<int> bstree;

#ifdef _DEBUG
    _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#endif

    bstree.Insert(1);
    bstree.Insert(2);
    bstree.Insert(3);

    bstree.Delete(1);
}

9.3 说明

我的二叉搜索树是从二叉树继承而来的，我写了Find()、FindMin()、FindMax()、Insert()和Delete()一共5个成员函数。这里要说的是，对非线性数据结构的操作总是特别的不直观，因为一般来说我们会选择使用递归——而人脑一般不太容易“调试”递归的程序——如果递归的层数比较少（例如只有1、2次）那还好点，但一旦超过5、6次，恐怕人脑的“堆栈”就要溢出了。

好了，牢骚完毕，来解释一下：

Find()：如果树为空，则返回NULL；如果根结点比它的左儿子要小，就往左进行，否则如果比右儿子小就往右进行，一直到既不大于也不小于它的儿子为止，那么这个结点就一定是我们要找的了。
FindMin()：从根结点开始，只要有左儿子就向左进行，直到遇到终止结点为止。
FindMax()：除分支朝右儿子进行外，其余过程与FindMin()相同。
Insert()：如果找到了相同的元素，则什么都不做；否则，递归查找到遍历路径的最后一点上，然后执行Insert操作。
Delete()：正如许多数据结构一样，最困难的操作是删除。删除的操作可以分成下面几种情况：
- 如果结点是一片树叶，那么它可以被立即删除。
- 如果结点有一个儿子，那么该结点可以在其父结点调整指针绕过该结点后被删除。
- 最复杂的情况是处理具有两个儿子的结点。我们可以用其右子树的最小的数据（很容易找到）代替该结点的数据，并递归地删除那个结点。为什么？因为一个结点肯定比它的右子树的所有结点都小，同时又比它的左子树的所有结点都大，所以我们只要在其右子树中找到最小的那个结点来代替它，就能满足二叉树的性质了。（根据这个规则，我们还可以用其左子树的最大的数据来代替该结点的数据，道理是一样的，不再叙述）

说了那么多，估计我还是没有讲清楚（主要是有点抽象），请读者编译我的代码并亲自动手调试一下吧。我的测试代码没有输出结果，因为要写个打印二叉树的函数我觉得有点烦，您可以在相应的函数中下断点，我个人认为只要能弄懂Delete()函数，那别的应该都没问题了。:)

第九章 二叉搜索树

9.1 基本概念

9.2 代码实现

9.3 说明

第九章

二叉搜索树