二叉搜索树基本操作详解

本节将介绍可能在二叉搜索树上执行的一些基本操作。接下来要讲解的是一个简单的类，该类实现了用一个二叉树来存储整数值。

创建二叉搜索树

现在使用 IntBinaryTree 类来演示基本的二叉树操作。在本示例中，二叉树结点的基础是下面的类声明：

class TreeNode
{
    int value;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int value1,TreeNode *left1 = nullptr,TreeNode *right1 = nullptr)
    {
        value = value1;
        left = left1;
        right = right1;
    }
};

请注意，树的每个结点都有一个 value 成员，另外还有两个指针，用于跟踪结点的左侧和右侧子结点。这个类只能被 IntBinaryTree 的方法使用。

//IntBinaryTree.h的内容
class IntBinaryTree
{
    private:
        //The TreeNode struct is used to build the tree.
        struct TreeNode
        {
            int value;
            TreeNode *left;
            TreeNode *right;
            TreeNode(int value1,TreeNode *left1 = nullptr,TreeNode *right1 = nullptr)
            {
                value = value1;
                left = left1;
                right = right1;
            }
        };
        TreeNode *root; // Pointer to the root of the tree
        // Various helper member functions.
        void insert(TreeNode *&, int);
        void destroySubtree(TreeNode *);
        void remove(TreeNode *&, int);
        void makeDeletion(TreeNode *&);
        void displayInOrder(TreeNode *) const;
        void displayPreOrder(TreeNode *) const;
        void displayPostOrder(TreeNode *) const;
    public:
        // These member functions are the public interface.
        IntBinaryTree。    // Constructor
        {
            root = nullptr;
        }
        ~IntBinaryTree()    // Destructor
        {
            destroySubtree(root);
        }
        void insert(int num)
        {
            insert (root, num);
        }
        bool search(int) const;
        void remove(int num)
        {
            remove(root, num);
        }
        void showInOrder(void) const
        {
            displayInOrder(root);
        }
        void showPreOrder() const
        {
            displayPreOrder(root);
        }
        void showPostOrder() const
        {
            displayPostOrder(root);
        }
}

除了 TreeNode 类声明之外，该类还有一个 root 成员。这是一个指向二叉树根结点的指针，起着类似于链表中 head 指针的作用。在许多情况下，将指向二叉树根结点的指针视为二叉树本身是很有用的。因此，可以写作如下形式：

TreeNode *tree;
或
TreeNode *root;

它们都可以视为代表二叉树，因为根结点提供对整个树的访问。另一方面，将 IntBinaryTree 类的对象看作二叉树也是有用的，并且可以写作以下形式：

IntBinaryTree Tree;

为了避免混淆，当使用由 IntBinaryTree 类的对象表示二叉树时，该二叉树的标识符首字母釆用大写形式，例如 "IntBinaryTreeTree;"；当使用由指向其根结点的指针表示二叉树时，则该二叉树的标识符首字母釆用小写形式，例如 "TreeNode *root;"。

IntBinaryTree 的公共成员函数包括：构造函数、析构函数、用于在树中插入新数字的成员函数、用于搜索树以确定给定的数字是否在树中的成员函数、用于从树中移除数字的成员函数，以及根据不同的顺序显示存储在树中的数字的成员函数。

下面的程序演示了创建一个 IntBinaryTree 对象和使用公共 insert 成员函数来构建一个二叉搜索树：

// This program builds a binary tree with 5 nodes.
#include <iostream>
#include "IntBinaryTree.h"
using namespace std;

int main()
{
    IntBinaryTree tree;
    cout << "Inserting numbers. ";
    tree.insert (5);
    tree.insert(8);
    tree.insert (3);
    tree.insert(12);
    tree.insert (9);
    cout << "Done. \n";
    return 0;
}

程序执行结果如图 1 所示: