二元搜尋樹基本操作詳解

本節將介紹可能在二元搜尋樹上執行的一些基本操作。接下來要講解的是一個簡單的類，該類實現了用一個二元樹來儲存整數值。

建立二元搜尋樹

現在使用 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 所示:

---