二叉搜索樹的插入與刪除(詳細解析)

更新時間：2013年09月04日 09:22:31 作者：

添加結(jié)點其實很容易，我們只需要找到結(jié)點所行對應的位置就可以了，而且沒有要求是平衡的二叉搜索樹，因此每次添加結(jié)點都是在葉子結(jié)點上操作，不需要修改二叉搜索樹整體的結(jié)構(gòu)

題目：創(chuàng)建一個類，類中的數(shù)據(jù)成員時一棵二叉搜索樹，對外提供的接口有添加結(jié)點和刪除結(jié)點這兩種方法。用戶不關注二叉樹的情況。要求我們給出這個類的結(jié)構(gòu)以及實現(xiàn)類中的方法。

思路
添加結(jié)點：
添加結(jié)點其實很容易，我們只需要找到結(jié)點所行對應的位置就可以了，而且沒有要求是平衡的二叉搜索樹，因此每次添加結(jié)點都是在葉子結(jié)點上操作，不需要修改二叉搜索樹整體的結(jié)構(gòu)。要找出添加節(jié)點在二叉搜索樹中的位置，可以用一個循環(huán)解決。判斷插入結(jié)點與當前頭結(jié)點的大小，如果大于頭結(jié)點則繼續(xù)搜索右子樹，如果小于頭結(jié)點則繼續(xù)搜索左子樹。直到搜索到葉子結(jié)點，此時進行插入結(jié)點操作。如果插入的結(jié)點等于二叉搜索樹中當前某一結(jié)點的值，那么退出插入操作，并告知用戶該結(jié)點已經(jīng)存在。

刪除結(jié)點：
刪除結(jié)點比較麻煩，因為需要調(diào)整樹的結(jié)構(gòu)，這是因為刪除結(jié)點并不一定發(fā)生在葉子結(jié)點。如果刪除的是葉子結(jié)點，那么操作非常簡單，只是做相應的刪除就可以了，但如果刪除的是非葉子結(jié)點，那么就需要調(diào)整二叉搜索樹的結(jié)構(gòu)。調(diào)整的策略有兩個。假設當前需要刪除的結(jié)點為A，

1.找出A結(jié)點左子樹中的最大值結(jié)點B，將B調(diào)整到原先A的位置。
2.找出A結(jié)點右子樹中的最小值結(jié)點C，將C調(diào)整到原先A的位置。

這其中涉及到許多復雜的指針操作，在下面的代碼示例中并沒有完成結(jié)點刪除操作，等有空再補充研究一下。

代碼示例

復制代碼代碼如下:

#include<iostream>
#include<stdlib.h>
#include<cassert>
using namespace std;

//二叉樹結(jié)點
struct BinaryTreeNode
{
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};

class BST
{
public:
    BST(int value);//構(gòu)造函數(shù)
    ~BST();//析構(gòu)函數(shù)
    void AddNode(int value);//添加結(jié)點
    void DeleteNode(int value);//刪除結(jié)點
    BinaryTreeNode* CreateBinaryTreeNode(int value);//創(chuàng)建一個二叉樹結(jié)點
    void InOrderPrintTree();//中序遍歷
    void InOrderPrintTree(BinaryTreeNode* pRoot);//中序遍歷
    BinaryTreeNode* GetMaxNode(BinaryTreeNode* pNode);//求二叉搜索樹最大值
    BinaryTreeNode* GetMinNode(BinaryTreeNode* pNode);//求二叉搜索樹最小值

private:
BinaryTreeNode* pRoot;
};

//構(gòu)造函數(shù)
BST::BST(int value)
{
pRoot=CreateBinaryTreeNode(value);
}

//析構(gòu)函數(shù)
BST::~BST()
{
delete pRoot;
pRoot=NULL;
}

//創(chuàng)建二叉樹結(jié)點
BinaryTreeNode* BST::CreateBinaryTreeNode(int value)
{
    BinaryTreeNode* pNode=new BinaryTreeNode();
    pNode->m_nValue=value;
    pNode->m_pLeft=NULL;
    pNode->m_pRight=NULL;
    return pNode;
}

//求二叉搜索樹最大值
BinaryTreeNode* BST::GetMaxNode(BinaryTreeNode* pNode)
{
    assert(pNode!=NULL); // 使用斷言，保證傳入的頭結(jié)點不為空
    //最大值在右子樹上，因此一直遍歷右子樹，讓pNode等于其右子樹；如果只有一個結(jié)點則直接返回pNode
    while(pNode->m_pRight!=NULL)
    {
        pNode=pNode->m_pRight;
    }
    return pNode;

}
//求二叉搜索樹最小值
BinaryTreeNode* BST::GetMinNode(BinaryTreeNode* pNode)
{
    assert(pNode!=NULL); // 使用斷言
    //最小值在左子樹上，整體思路跟求最大值相同。
    while(pNode->m_pLeft!=NULL)
    {
        pNode=pNode->m_pLeft;
    }
    return pNode;
}
//二叉搜索樹添加結(jié)點
void BST::AddNode(int value)
{
    BinaryTreeNode* pInsertNode=CreateBinaryTreeNode(value);//初始化需要創(chuàng)建的結(jié)點。
    BinaryTreeNode* pNode=pRoot;
    while(true)
    {
        //如果插入的值在二叉搜索樹中已經(jīng)存在，則不進行插入操作，跳出循環(huán)。
        if(pNode->m_nValue==value)
        {
            cout<<"結(jié)點值已經(jīng)存在"<<endl;
            break;
        }

        //尋找結(jié)點插入的位置，如果待插入結(jié)點小于當前頭結(jié)點，則繼續(xù)搜索左子樹
        else if(pNode->m_nValue > value)
        {
            if(pNode->m_pLeft==NULL)//如果當前頭結(jié)點是葉子結(jié)點了，那么直接將待插入結(jié)點插入到左子樹中，然后跳出循環(huán)
            {
                pNode->m_pLeft=pInsertNode;
                break;
            }
            else//否則繼續(xù)遍歷其左子樹
                pNode=pNode->m_pLeft;
        }
        //思路跟上述相同
        else if(pNode->m_nValue < value)
        {
            if(pNode->m_pRight==NULL)
            {
                pNode->m_pRight=pInsertNode;
                break;
            }
            pNode=pNode->m_pRight;
        }
    }

}

//未完成
void BST::DeleteNode(int value)
{
    BinaryTreeNode* pNode=pRoot;
    while(true)
    {
        if(pRoot->m_nValue==value)//如果是頭結(jié)點
        {
            if(pRoot->m_pLeft!=NULL)
            {
                BinaryTreeNode* pLeftMaxNode=GetMaxNode(pRoot->m_pLeft);
            }
            else if(pRoot->m_pRight!=NULL)
            {

            }
            else
            {
                delete pRoot;
                pRoot=NULL;
            }
        }

        if(pNode->m_nValue==value)
        {
            if(pNode->m_pLeft!=NULL)
            {

            }
            else if(pNode->m_pRight!=NULL)
            {

            }
            else
            {

            }
        }
    }
}
void BST::InOrderPrintTree(BinaryTreeNode* pRoot)//中序遍歷
{
    if(pRoot!=NULL)
    {
        //如果左子樹不為空，則遍歷左子樹
        if(pRoot->m_pLeft!=NULL)
            InOrderPrintTree(pRoot->m_pLeft);
        //遍歷左子樹的葉子結(jié)點
        cout<<"value of this node is "<<pRoot->m_nValue<<endl;
        //如果右子樹不為空，遍歷右子樹
        if(pRoot->m_pRight!=NULL)
            InOrderPrintTree(pRoot->m_pRight);
    }
    else
    {
        cout<<"this node is null."<<endl;
    }
}
//因為需要使用遞歸來進行中序遍歷，所以還需要調(diào)用一個帶參數(shù)的中序遍歷函數(shù)
void BST::InOrderPrintTree()//中序遍歷
{
    InOrderPrintTree(pRoot);
}
void main()
{
    BST* b=new BST(10);//初始化類的時候定義了二叉搜索樹的頭結(jié)點，這樣省去了頭結(jié)點為空的判斷
    b->AddNode(6);
    b->AddNode(14);
    b->InOrderPrintTree();
    system("pause");
}