/*
二叉查找樹的鏈表實現：
以及三種遍歷方式,刪除節點；
查找節點；
author:天下無雙
Date:2014-5-28
Version:3.0
*/
#include
#include
typedef int T;//樹內節點的數據類型
using namespace std;
class BiTree
{
private:
struct BiNode{
T data;
BiNode *lchild,*rchild;
BiNode(T d){
data=d;
lchild=nullptr;
rchild=nullptr;
}
};
BiNode *root;
public:
BiTree(){
//root=root->rchild=root->rchild=nullptr;
root=nullptr;
}
~BiTree(){
}
//使用遞歸創建二叉樹
//以二叉排序樹的規則建立
//指針的引用寫法（推薦使用）
bool addBiNode(BiNode *&nodeRoot,T d){
if(nodeRoot==nullptr){
BiNode *p=new BiNode(d);
nodeRoot=p;
cout<data<<" insert success!"<data){
//往左子樹遞歸
addBiNode(nodeRoot->lchild,d);
}else if(nodeRoot!=nullptr&&d>(nodeRoot)->data){
//往右子樹遞歸
addBiNode(nodeRoot->rchild,d);
}else{
cout<<"樹中已有該數據"<data==d){
return true;
}else if(nodeRoot->datarchild,d);
}else
return Search(nodeRoot->lchild,d);
}
}
//遞歸查找確定該節點所在位置
bool DeleteBST(BiNode *&nodeRoot,T d){
if(nullptr==nodeRoot)//當該節點為空
return false;
else{
if(nodeRoot->data==d){//
return Delete(nodeRoot);
//Delete(nodeRoot);
}else if(nodeRoot->datarchild,d);
//DeleteBST(nodeRoot->rchild,d);
}else
return DeleteBST(nodeRoot->lchild,d);
//DeleteBST(nodeRoot->lchild,d);
}
}
protected:
//刪除操作
//刪除相應節點
//如果該節點是葉子節點，即該節點左右孩子均為空，則只需將父節點指向該節點
//指針置空即可
//如果僅有左孩子或者僅有右孩子，則將對應節點上移
//nodeRoot為要刪除的節點
//若既有左孩子，又有右孩子，看下面的注釋
bool Delete(BiNode *&nodeRoot){
//如果要刪除的節點右子樹為空，則只需移動左子樹
if(nullptr==nodeRoot->rchild){
BiNode *temp=nodeRoot;
nodeRoot=nodeRoot->lchild;
delete temp;
return true;
}else if(nullptr==nodeRoot->lchild){//若左子樹空則移動右子樹
BiNode *temp=nodeRoot;
nodeRoot=nodeRoot->rchild;
delete temp;
return true;
}else{//左右子樹均非空
//將該節點的左子樹的最右邊的右節點數據和該節點互換
//或者是將該節點右子樹最左端的左節點和該節點數據互換
//我這裡是選擇左子樹的最右節點
BiNode *temp=nodeRoot->lchild;//temp為該節點左子樹的根節點
BiNode *preTemp=nodeRoot->lchild;
while(nullptr!=temp->rchild){
preTemp=temp;//令preTemp指向最右節點的前驅
temp=temp->rchild;//一直尋找最右的右節點
//temp指向待刪除的節點
}
//這時候temp指向最右的一個節點
nodeRoot->data=temp->data;//交換數據，由於二叉查找樹的特性，交換後依舊保持該特性。
/*
50
30 70
20
倘若刪除的是50，則preTemp=temp=&30
*/
if(temp!=preTemp)
preTemp->rchild=temp->lchild;//令前驅節點的右孩子變成被刪除節點的左孩子
else
nodeRoot->lchild=temp->lchild;
delete temp;//刪除右節點
return true;
}
return false;
}
//T如果是結構或者類類型，需重載<<運算符
void Visit(const BiNode *r)const{
cout<data<<" ";
}
//利用遞歸遍歷，三種遍歷原理都是一樣的
//前序遍歷,先根遍歷
void PreOrderTraverse(const BiNode *nodeRoot)const{
if(nodeRoot!=nullptr)
Visit(nodeRoot);
if(nodeRoot->lchild!=nullptr)
PreOrderTraverse(nodeRoot->lchild);
if(nodeRoot->rchild!=nullptr)
PreOrderTraverse(nodeRoot->rchild);
}
//中根遍歷
void InOrderTraverse(const BiNode *nodeRoot)const{
if(nodeRoot->lchild!=nullptr)
InOrderTraverse(nodeRoot->lchild);
if(nodeRoot!=nullptr)//當該點左子樹空時
Visit(nodeRoot);
if(nodeRoot->rchild!=nullptr)
InOrderTraverse(nodeRoot->rchild);
}
//後序遍歷
void PostOrderTraverse(const BiNode *nodeRoot)const{
if(nodeRoot->lchild!=nullptr)
PostOrderTraverse(nodeRoot->lchild);
if(nodeRoot->rchild!=nullptr)
PostOrderTraverse(nodeRoot->rchild);
if(nodeRoot!=nullptr)
Visit(nodeRoot);
}
};
感覺對於遞歸中的return還是有點不太清晰。
什麼時候該用，什麼時候不該用也不太清晰。
測試代碼
#include "bit4.cpp"
int main()
{
BiTree b;
//b.addBiNode(&b.root,50);//設立根節點值//二級指針寫法
b.addBiNode(b.getRoot(),50);//指針的引用寫法
int i;
int arr[9]={30,40,35,27,100,90,110,95,-999};
for(int j=0;j<9;j++)
{
i=arr[j];
if(i==-999)
break;
b.addBiNode(b.getRoot(),i);
}
b.Traverse(b.getPtrToRoot(),"PreOrderTraverse");
b.Traverse(b.getPtrToRoot(),"InOrderTraverse");
b.Traverse(b.getPtrToRoot(),"PostOrderTraverse");
while(true)
{
int k;
cout<<"\n輸入要查找的值:"<>k;
if(b.Search(b.getRoot(),k))
cout<<"OK"<
