二叉搜索樹的插入與刪除(詳細(xì)解析)
題目：創(chuàng)建一個(gè)類，類中的數(shù)據(jù)成員時(shí)一棵二叉搜索樹，對(duì)外提供的接口有添加結(jié)點(diǎn)和刪除結(jié)點(diǎn)這兩種方法。用戶不關(guān)注二叉樹的情況。要求我們給出這個(gè)類的結(jié)構(gòu)以及實(shí)現(xiàn)類中的方法。
思路
添加結(jié)點(diǎn)：
添加結(jié)點(diǎn)其實(shí)很容易，我們只需要找到結(jié)點(diǎn)所行對(duì)應(yīng)的位置就可以了，而且沒有要求是平衡的二叉搜索樹，因此每次添加結(jié)點(diǎn)都是在葉子結(jié)點(diǎn)上操作，不需要修改二叉搜索樹整體的結(jié)構(gòu)。要找出添加節(jié)點(diǎn)在二叉搜索樹中的位置，可以用一個(gè)循環(huán)解決。判斷插入結(jié)點(diǎn)與當(dāng)前頭結(jié)點(diǎn)的大小，如果大于頭結(jié)點(diǎn)則繼續(xù)搜索右子樹，如果小于頭結(jié)點(diǎn)則繼續(xù)搜索左子樹。直到搜索到葉子結(jié)點(diǎn)，此時(shí)進(jìn)行插入結(jié)點(diǎn)操作。如果插入的結(jié)點(diǎn)等于二叉搜索樹中當(dāng)前某一結(jié)點(diǎn)的值，那么退出插入操作，并告知用戶該結(jié)點(diǎn)已經(jīng)存在。
刪除結(jié)點(diǎn)：
刪除結(jié)點(diǎn)比較麻煩，因?yàn)樾枰{(diào)整樹的結(jié)構(gòu)，這是因?yàn)閯h除結(jié)點(diǎn)并不一定發(fā)生在葉子結(jié)點(diǎn)。如果刪除的是葉子結(jié)點(diǎn)，那么操作非常簡單，只是做相應(yīng)的刪除就可以了，但如果刪除的是非葉子結(jié)點(diǎn)，那么就需要調(diào)整二叉搜索樹的結(jié)構(gòu)。調(diào)整的策略有兩個(gè)。假設(shè)當(dāng)前需要?jiǎng)h除的結(jié)點(diǎn)為A，
1.找出A結(jié)點(diǎn)左子樹中的最大值結(jié)點(diǎn)B，將B調(diào)整到原先A的位置。
2.找出A結(jié)點(diǎn)右子樹中的最小值結(jié)點(diǎn)C，將C調(diào)整到原先A的位置。
這其中涉及到許多復(fù)雜的指針操作，在下面的代碼示例中并沒有完成結(jié)點(diǎn)刪除操作，等有空再補(bǔ)充研究一下。
代碼示例
#include<iostream>
#include<stdlib.h>
#include<cassert>
using namespace std;
//二叉樹結(jié)點(diǎn)
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é)點(diǎn)
void DeleteNode(int value);//刪除結(jié)點(diǎn)
BinaryTreeNode* CreateBinaryTreeNode(int value);//創(chuàng)建一個(gè)二叉樹結(jié)點(diǎn)
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é)點(diǎn)
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é)點(diǎn)不為空
//最大值在右子樹上，因此一直遍歷右子樹，讓pNode等于其右子樹；如果只有一個(gè)結(jié)點(diǎn)則直接返回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é)點(diǎn)
void BST::AddNode(int value)
{
BinaryTreeNode* pInsertNode=CreateBinaryTreeNode(value);//初始化需要?jiǎng)?chuàng)建的結(jié)點(diǎn)。
BinaryTreeNode* pNode=pRoot;
while(true)
{
//如果插入的值在二叉搜索樹中已經(jīng)存在，則不進(jìn)行插入操作，跳出循環(huán)。
if(pNode->m_nValue==value)
{
cout<<"結(jié)點(diǎn)值已經(jīng)存在"<<endl;
break;
}
//尋找結(jié)點(diǎn)插入的位置，如果待插入結(jié)點(diǎn)小于當(dāng)前頭結(jié)點(diǎn)，則繼續(xù)搜索左子樹
else if(pNode->m_nValue > value)
{
if(pNode->m_pLeft==NULL)//如果當(dāng)前頭結(jié)點(diǎn)是葉子結(jié)點(diǎn)了，那么直接將待插入結(jié)點(diǎn)插入到左子樹中，然后跳出循環(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é)點(diǎn)
{
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é)點(diǎn)
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;
}
}
//因?yàn)樾枰褂眠f歸來進(jìn)行中序遍歷，所以還需要調(diào)用一個(gè)帶參數(shù)的中序遍歷函數(shù)
void BST::InOrderPrintTree()//中序遍歷
{
InOrderPrintTree(pRoot);
}
void main()
{
BST* b=new BST(10);//初始化類的時(shí)候定義了二叉搜索樹的頭結(jié)點(diǎn)，這樣省去了頭結(jié)點(diǎn)為空的判斷
b->AddNode(6);
b->AddNode(14);
b->InOrderPrintTree();
system("pause");
}
相關(guān)文章
C++封裝遠(yuǎn)程注入類CreateRemoteThreadEx實(shí)例
這篇文章主要介紹了C++封裝遠(yuǎn)程注入類CreateRemoteThreadEx實(shí)例,詳細(xì)講述了注入DLL到指定的地址空間以及從指定的地址空間卸載DLL的方法,需要的朋友可以參考下2014-10-10
VC++實(shí)現(xiàn)文件與應(yīng)用程序關(guān)聯(lián)的方法(注冊(cè)表修改)
這篇文章主要介紹了VC++實(shí)現(xiàn)文件與應(yīng)用程序關(guān)聯(lián)的方法,涉及VC++針對(duì)注冊(cè)表的相關(guān)操作技巧,需要的朋友可以參考下2016-08-08
C語言之整數(shù)與浮點(diǎn)數(shù)運(yùn)算的類型轉(zhuǎn)換規(guī)則詳解
這篇文章主要介紹了C語言之整數(shù)與浮點(diǎn)數(shù)運(yùn)算的類型轉(zhuǎn)換規(guī)則,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2025-03-03
C語言數(shù)據(jù)結(jié)構(gòu)之串插入操作
這篇文章主要介紹了C語言數(shù)據(jù)結(jié)構(gòu)之串插入操作的相關(guān)資料,希望通過本文能幫助到大家，讓大家實(shí)現(xiàn)這樣的功能，需要的朋友可以參考下2017-10-10
如何調(diào)用C標(biāo)準(zhǔn)庫的exit函數(shù)詳解
這篇文章主要給大家介紹了關(guān)于如何調(diào)用C標(biāo)準(zhǔn)庫的exit函數(shù)的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-07-07
C++中volatile限定符的實(shí)現(xiàn)示例
volatile關(guān)鍵字在C和C++中用于確保編譯器不優(yōu)化特定變量的訪問,主要用于多線程和硬件交互場(chǎng)景,本文就來介紹C++中volatile限定符的實(shí)現(xiàn)示例,感興趣的可以了解一下2024-11-11
本文給大家分享的是一則使用C語言來實(shí)現(xiàn)的一個(gè)簡單日歷的代碼，根據(jù)項(xiàng)目需求，實(shí)現(xiàn)了3個(gè)簡單的小功能，推薦給大家，有需要的小伙伴可以參考下。2015-03-03
C/C++ 動(dòng)態(tài)數(shù)組的創(chuàng)建的實(shí)例詳解
這篇文章主要介紹了C/C++ 動(dòng)態(tài)數(shù)組的創(chuàng)建的實(shí)例詳解的相關(guān)資料,希望通過本文能幫助到大家，讓大家掌握這樣的功能，需要的朋友可以參考下2017-10-10
Vue?3?顯著增強(qiáng)了自定義指令的功能,使其封裝更加靈活和易用,本文將分為基礎(chǔ)和進(jìn)階兩部分,介紹如何實(shí)現(xiàn)常用的自定義指令,并提供最佳的項(xiàng)目組織方式,需要的朋友可以參考下2024-12-12
C++輸出上三角/下三角/菱形/楊輝三角形(實(shí)現(xiàn)代碼)
本篇文章是對(duì)C++中輸出上三角/下三角/菱形/楊輝三角形的示例代碼進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-07-07