C語言中文網 目錄
首頁 > 編程筆記 > C++筆記 閱讀:210

二叉搜索樹基本操作詳解

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

創建二叉搜索樹

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

使用 insert 成員函數構建的二叉樹
圖 1 使用 insert 成員函數構建的二叉樹

二叉搜索樹操作的實現

許多二叉樹操作都有非常自然的遞歸實現。這是因為二叉樹是一種固有的遞歸數據結構:每一個非空二叉樹都由一個根結點和左右子樹組成,當然,這些子樹也都是二叉樹。許多二叉樹操作可以通過在根結點處執行一些處理然后在左右子樹上遞歸地執行操作來實現。

例如,如果根結點由一個指針表示:

TreeNode *tree;

那么根結點中的值將是 tree->value,左右子樹將由 tree->left 和 tree->right 給出。遞歸操作可能首先處理 tree->value,然后遞歸操作 tree->left 和 tree->right。

二叉搜索樹插入元素

將數字插入到二叉搜索樹中的工作由私有成員函數執行,即:

insert(TreeNode *&tree, int num)

該語句將指針 tree 傳遞給二叉搜索樹的根結點,并將數字 num 插入樹中。它使用遞歸策略:如果二叉樹是空的(這是遞歸的基本情況),那么它將創建一個新的 TreeNode 對象,其值成員是給定的數字,并使其成為樹的根:
if (!tree)
{
    tree = new TreeNode(num);
    return;
}
但是,如果二叉搜索樹不為空,則 insert 函數會將 num 與 tree->value(根結點中的值)進行比較。根據這個比較的結果,新值被遞歸地插入到左邊或右邊的子樹中:
if (num < tree->value)
    insert(tree->left, num);
else
    insert(tree->right, num);
整個函數給定如下:
void IntBinaryTree::insert(TreeNode * &tree, int num)
{
    //如果樹是空的,則創建一個新結點
    //并且使該結點成為根結點
    if (!tree)
    {
        tree = new TreeNode(num);
        return;
    }
    //如果num已經在樹中,則返回
    if (tree->value == num)
        return;
    //如果樹不為空,則插入新結點到左子樹或右子樹中
    if (num < tree->value)
        insert(tree->left, num);
    else
        insert(tree->right, num);
}
請注意,該函數被傳遞對指針的引用,因為傳遞的指針可能需要由函數修改。這也是 remove 和 makeDeletion 函數通過引用傳遞其形參的原因。

注意,如圖 1 所示的樹的形狀由值的插入順序決定。根結點保存值 5,因為它是插入的第一個值。通過遍歷該函數,可以看到其他結點是如何出現在它們圖示的位置上的。

二叉搜索樹的遍歷

遍歷非空二叉樹和處理每個結點的值有3種常用的方法:中序遍歷、前序遍歷后序遍歷。這些方法中的每一個的最佳實現方式都是遞歸函數。

中序遍歷算法的實現思路是:
  • 遍歷結點的左子樹。
  • 結點的數據被處理。
  • 遍歷結點的右子樹。

前序遍歷算法的實現思路是:
  • 結點的數據被處理。
  • 遍歷結點的左子樹。
  • 遍歷結點的右子樹。

后序遍歷算法的實現思路是:
  • 遍歷結點的左子樹。
  • 遍歷結點的右子樹。
  • 結點的數據被處理。

IntBinaryTree 類可以使用這 3 種算法顯示樹中的所有值。該算法將由以下內聯公共成員函數進行初始化:

void showInOrder(void){ displayInOrder (root); }
void showPreOrder(){ displayPreOrder(root); }
void showPostOrder(){ displayPostOrder(root); }

每個公共成員函數都調用遞歸私有成員函數,并將根指針作為參數傳遞。這些遞歸函數都非常簡單直接:
void IntBinaryTree::displayInOrder(TreeNode *tree) const
{
    if (tree)
    {
        displayInOrder(tree->left);
        cout << tree->value << " ";
        displayInOrder(tree->right);
    }
}

void IntBinaryTree::displayPreOrder(TreeNode *tree) const
{
    if (tree)
    {
        cout << tree->value << " ";
        displayPreOrder(tree->left);
        displayPreOrder(tree->right);
    }
}

void IntBinaryTree::displayPostOrder(TreeNode *tree) const
{
    if (tree)
    {
        displayPostOrder(tree->left);
        displayPostOrder(tree->right);
        cout << tree->value << " ";
    }
}
下面的程序演示了這 3 種遍歷方法中的每一種。
//This program builds a binary tree with 5 nodes. The nodes are displayed with inorderA preorder, and postorder algorithms.
#include <iostream>
#include "IntBinaryTree.h"
using namespace std;

int main()
{
    IntBinaryTree tree;
    cout << "Inserting the numbers 5 8 3 12 9.\n";
    tree.insert(5);
    tree.insert(8);
    tree.insert(3);
    tree.insert(12);
    tree.insert(9);
    cout << "Inorder traversal: ";
    tree.showInOrder();
    cout << "\nPreorder traversal: ";
    tree.showPreOrder();
    cout << "\nPostorder traversal: ";
    tree.showPostOrder();
    return 0;
}
程序執行結果:

Inserting the numbers 5 83 12 9.
Inorder traversal: 3 5 8 9 12
Preorder traversal: 5 3 8 12 9
Postorder traversal: 3 9 12 8 5

搜索二叉搜索樹

IntBinarySearchTree 類具有公共成員函數 search,如果在樹中找到給定值,則返回 true,否則返回 false。

該函數只是開始搜索整個樹。將 num (正在搜索的值)與當前正在搜索的樹的根值進行比較。如果值匹配,則函數返回 true。如果該值不匹配,則該函數用其左子樹或其右子樹替換該樹,并繼續搜索。當函數找到值或搜索樹變空時,搜索將終止。
bool IntBinaryTree::search(int num) const
{
    TreeNode *tree = root;
    while (tree)
    {
        if (tree->value == num)
            return true;
        else if (num < tree->value)
            tree = tree->left;
        else
            tree = tree->right;
    }
    return false;
}
下面的程序演示了該函數:
//This program builds a binary tree with 5 nodes. The search function determines if the value 3 is in the tree.
#include <iostream>
#include "IntBinarytree.h"
using namespace std;

int main()
{
    IntBinaryTree tree;
    cout << "Inserting the numbers 5 8 3 12 9.\n";
    tree.insert (5);
    tree.insert(8);
    tree.insert (3);
    tree.insert (12);
    tree.insert (9);
    if (tree.search(3))
        cout << "3 is found in the tree.\n";
    else
        cout << "3 was not found in the tree.\n";
    return 0;
}
程序輸出結果:

Inserting the numbers 5 83 12 9.
3 is found in the tree.

二叉搜索樹刪除元素

要移除一個元素,首先需要找到包含該元素的結點,然后才能刪除該結點。

刪除結點 X 的過程取決于其子結點的數量。如果 X 沒有子元素,則首先找到它的父元素,將連接到 X 的父元素的子指針設置為 nullptr,然后釋放分配給 X 的內存。如果 X 是樹的根,則剛剛描述的過程不會工作。在這種情況下,只需刪除 X,并將指向樹根的指針設置為 nullptr。

刪除非葉結點的過程必須確保該結點鏈接的子樹保持為樹的一部分。該過程將根據被刪除的結點是否有一個或兩個子結點而有所不同。圖 2 顯示了一個樹,其中有一個要刪除的結點,而該結點本身具有一個子樹。

要刪除的結點具有一個子樹
圖 2 要刪除的結點具有一個子樹

圖 3 顯示了如何將結點的子樹與其父結點鏈接起來。

將結點的子樹與其父結點鏈接起來以方便刪除結點
圖 3 將結點的子樹與其父結點鏈接起來以方便刪除結點

但是,當要刪除的結點有 2 個子樹時,這個問題就變得不那么容易被解決,如圖 4 所示。

如果要刪除的結點有 2 個子樹則問題就變得相對復雜
圖 4 如果要刪除的結點有 2 個子樹則問題就變得相對復雜

很顯然,不能將結點的兩個子樹都連接到它的父結點(因為任何二叉樹的結點都不能擁有 3 個子結點),所以必須有另一種解決方案。解決這個問題的一種方法是將結點的右側子樹連接到父結點,然后在右側子樹中找到一個位置來連接左側子樹。結果如圖 5 所示。

刪除擁有 2 個子結點的結點的解決方案
圖 5 刪除擁有 2 個子結點的結點的解決方案

請注意,在將左側子樹連接到右側子樹時,必須注意保留二叉樹的搜索屬性。

從 IntBinaryTree 對象中刪除值是通過調用公共成員函數 remove 來完成的,后者又調用同名的私有成員函數。后面這個函數被傳遞(二叉搜索樹的根)tree 和一個要從樹中刪除的值 num:

remove (TreeNode *&tree, int num)

該函數使用了遞歸策略:
  • 如果樹為空,則立即返回;
  • 如果 num 小于存儲在根結點中的值,則函數遞歸地從左子樹中刪除 num;
  • 如果 num 大于存儲在根結點中的值,則函數遞歸地從右子樹中刪除 num;
  • 如果在根結點中找到 num,則將由 makeDeletion 函數來處理;

以下是 remove 函數的代碼:
void IntBinaryTree::remove(TreeNode *&tree, int num)
{
    if (tree == nullptr)
        return;
    if (num < tree->value)
        remove(tree->left, num);
    else if (num > tree->value)
        remove(tree->right,num);
    else
        //已經找到要刪除的結點
        makeDeletion(tree);
}
makeDeletion 函數設計用來刪除作為參數傳遞給它的二叉搜索樹的根結點,留下由剩余結點組成的二叉搜索樹。

現在來看一看 makeDeletion 函數背后的邏輯,它有以下幾種情況需要考慮:
  • 傳遞給 makeDeletion 函數的樹的根結點沒有子結點。在這種情況下,刪除根結點并用 nullptr 替換樹。
  • 樹的根結點只有一個子結點。在這種情況下,可以刪除根結點,并使用已被刪除的根結點的子結點來代替樹:
TreeNode *nodeToDelete = tree;
if (tree->right == nullptr)
    tree = tree->left;
else if (tree->left == nullptr)
    tree = tree->right;
  • 傳遞給 makeDelete 的樹有兩個子結點。在這種情況下,刪除根結點會留下兩個子樹,因此這兩個子結點都需要進行一些處理。這里采用的策略是將兩個子樹合并為一個二叉搜索樹,然后用合并的子樹構建的樹代替原樹。如圖 5 所示,可以將原始樹的左子樹連接作為原始樹的右子樹中最小結點的左子樹。

以下是整個函數的代碼:
void IntBinaryTree::makeDeletion(TreeNode *&tree)
{
    //用于保存將被刪除的結點
    TreeNode *nodeToDelete = tree;
    //用于找到左子樹要連接的點
    TreeNode *attachPoint;
    if (tree->right == nullptr)
    {
        //使用其左子樹替換該樹
        tree = tree->left;
    }
    else if (tree->left == nullptr)
    {
        //使用其右子樹替換該樹
        tree = tree->right;
    }
    else//該結點有2個子結點
    {
        //移動到右子樹
        attachPoint = tree->right;
        //找到右子樹中的最小結點移動到最左側
        while (attachPoint->left != nullptr)
            attachPoint = attachPoint->left;
        //連接原始樹的左子樹作為右子樹中的最小結點的左子樹
        attachPoint一>left = tree->left;
        //使用右子樹替換原始樹
        tree = tree->right;
    }
    //刪除原始樹
    delete nodeToDelete;
}
下面的程序演示了這些函數:
// This program builds a binary tree with 5 nodes.
// The deleteNode function is used to remove 2 of them.
#include <iostream>
#include "IntBinaryTree.h"
using namespace std;

int main()
{
    IntBinaryTree tree;
    cout << "Inserting the numbers 5 8 3 12 9.";
    tree.insert(5);
    tree.insert(8);
    tree.insert(3);
    tree.insert(12);
    tree.insert(9);
    cout << "\nHere are the values in the tree:\n"; tree.showInOrder();
    cout << "\nDeleting 8...\n";
    tree.remove(8);
    cout << "Deleting 12... \n";
    tree.remove(12);
    cout << "Now, here are the nodes:\n";
    tree.showInOrder();
    return 0;
}
程序輸出結果:

Inserting the numbers 5 8 3 12 9.
Here are the values in the tree:
3 5 8 9 12
Deleting 8...
Deleting 12...
Now, here are the nodes: 3 5 9

精美而實用的網站,提供C語言、C++、STL、Linux、Shell、Java、Go語言等教程,以及socket、GCC、vi、Swing、設計模式、JSP等專題。

Copyright ?2011-2018 biancheng.net, 陜ICP備15000209號

底部Logo