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

什么是二叉查找树

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

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;

    }

}