題目：創建一個類，類中的數據成員時一棵二叉搜索樹，對外提供的接口有添加結點和刪除結點這兩種方法。用戶不關注二叉樹的情況。要求我們給出這個類的結構以及實現類中的方法。
思路
添加結點：
添加結點其實很容易，我們只需要找到結點所行對應的位置就可以了，而且沒有要求是平衡的二叉搜索樹，因此每次添加結點都是在葉子結點上操作，不需要修改二叉搜索樹整體的結構。要找出添加節點在二叉搜索樹中的位置，可以用一個循環解決。判斷插入結點與當前頭結點的大小，如果大於頭結點則繼續搜索右子樹，如果小於頭結點則繼續搜索左子樹。直到搜索到葉子結點，此時進行插入結點操作。如果插入的結點等於二叉搜索樹中當前某一結點的值，那麼退出插入操作，並告知用戶該結點已經存在。
刪除結點：
刪除結點比較麻煩，因為需要調整樹的結構，這是因為刪除結點並不一定發生在葉子結點。如果刪除的是葉子結點，那麼操作非常簡單，只是做相應的刪除就可以了，但如果刪除的是非葉子結點，那麼就需要調整二叉搜索樹的結構。調整的策略有兩個。假設當前需要刪除的結點為A，
1.找出A結點左子樹中的最大值結點B，將B調整到原先A的位置。
2.找出A結點右子樹中的最小值結點C，將C調整到原先A的位置。
這其中涉及到許多復雜的指針操作，在下面的代碼示例中並沒有完成結點刪除操作，等有空再補充研究一下。
代碼示例
代碼如下：
#include<iostream>
#include<stdlib.h>
#include<cassert>
using namespace std;
//二叉樹結點
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
class BST
{
public:
BST(int value);//構造函數
~BST();//析構函數
void AddNode(int value);//添加結點
void DeleteNode(int value);//刪除結點
BinaryTreeNode* CreateBinaryTreeNode(int value);//創建一個二叉樹結點
void InOrderPrintTree();//中序遍歷
void InOrderPrintTree(BinaryTreeNode* pRoot);//中序遍歷
BinaryTreeNode* GetMaxNode(BinaryTreeNode* pNode);//求二叉搜索樹最大值
BinaryTreeNode* GetMinNode(BinaryTreeNode* pNode);//求二叉搜索樹最小值
private:
BinaryTreeNode* pRoot;
};
//構造函數
BST::BST(int value)
{
pRoot=CreateBinaryTreeNode(value);
}
//析構函數
BST::~BST()
{
delete pRoot;
pRoot=NULL;
}
//創建二叉樹結點
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); // 使用斷言，保證傳入的頭結點不為空
//最大值在右子樹上，因此一直遍歷右子樹，讓pNode等於其右子樹；如果只有一個結點則直接返回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;
}
//二叉搜索樹添加結點
void BST::AddNode(int value)
{
BinaryTreeNode* pInsertNode=CreateBinaryTreeNode(value);//初始化需要創建的結點。
BinaryTreeNode* pNode=pRoot;
while(true)
{
//如果插入的值在二叉搜索樹中已經存在，則不進行插入操作，跳出循環。
if(pNode->m_nValue==value)
{
cout<<"結點值已經存在"<<endl;
break;
}
//尋找結點插入的位置，如果待插入結點小於當前頭結點，則繼續搜索左子樹
else if(pNode->m_nValue > value)
{
if(pNode->m_pLeft==NULL)//如果當前頭結點是葉子結點了，那麼直接將待插入結點插入到左子樹中，然後跳出循環
{
pNode->m_pLeft=pInsertNode;
break;
}
else//否則繼續遍歷其左子樹
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)//如果是頭結點
{
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);
//遍歷左子樹的葉子結點
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;
}
}
//因為需要使用遞歸來進行中序遍歷，所以還需要調用一個帶參數的中序遍歷函數
void BST::InOrderPrintTree()//中序遍歷
{
InOrderPrintTree(pRoot);
}
void main()
{
BST* b=new BST(10);//初始化類的時候定義了二叉搜索樹的頭結點，這樣省去了頭結點為空的判斷
b->AddNode(6);
b->AddNode(14);
b->InOrderPrintTree();
system("pause");
}
