第九章

二叉搜索树

9.1  基本概念

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

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

     6
    / \
   2   8
  / \
 1   4
    /
   3

二叉搜索树的性质决定了它在搜索方面有着非常出色的表现:要找到一棵树的最小结点,只需要从根结点开始,只要有左儿子就向左进行,终止结点就是最小的结点。找最大的结点则是往右进行。例如上面的例子中,最小的结点是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次,恐怕人脑的“堆栈”就要溢出了。

好了,牢骚完毕,来解释一下:

  1. Find():如果树为空,则返回NULL;如果根结点比它的左儿子要小,就往左进行,否则如果比右儿子小就往右进行,一直到既不大于也不小于它的儿子为止,那么这个结点就一定是我们要找的了。

  2. FindMin():从根结点开始,只要有左儿子就向左进行,直到遇到终止结点为止。

  3. FindMax():除分支朝右儿子进行外,其余过程与FindMin()相同。

  4. Insert():如果找到了相同的元素,则什么都不做;否则,递归查找到遍历路径的最后一点上,然后执行Insert操作。

  5. Delete():正如许多数据结构一样,最困难的操作是删除。删除的操作可以分成下面几种情况:

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