?? bisorttree.cpp
字號(hào):
#include<iostream.h>
typedef struct TreeNode
{
int key;
struct TreeNode *left;
struct TreeNode *right;
}treeNode;
class BiSortTree
{
public:
BiSortTree(void);
void desplayTree(void);//顯示這個(gè)樹
void insertTree(int key);//在樹中插入一個(gè)值
deleteTree(int key);//在樹中刪除一個(gè)值
treeNode* searchTree(int key);//在樹中查找一個(gè)值
~BiSortTree();
private:
treeNode* buildTree(treeNode* head,int number);//建立一個(gè)樹
treeNode* search(treeNode* head ,int key);//查找
treeNode* BiSortTree::searchParent(treeNode* head,treeNode* p);//查找出p的父親節(jié)點(diǎn)的指針
treeNode* BiSortTree::searchMinRight(treeNode* head);//找到右子樹中最小的節(jié)點(diǎn)
void showTree(treeNode* head);//顯示
void destroyTree(treeNode* head);//刪除
treeNode *Head;
};
/**************以下是建立一個(gè)二叉排序樹****************/
BiSortTree::BiSortTree()
{
cout<<"建立一棵二叉排序樹,請(qǐng)輸入你要建樹的所有數(shù)(以-1 作為結(jié)束標(biāo)志!): "<<endl;
Head=NULL;
int number;
cin>>number;
while(number!=-1)
{
Head=buildTree(Head,number);
cin>>number;
}
}
treeNode* BiSortTree::buildTree(treeNode* head,int number)
{
treeNode *p;
p=new treeNode;
p->key=number;
p->left =p->right=NULL;
if(head==NULL)
{
return p;
}
else
{
if(p->key <head->key)
head->left=buildTree(head->left,number);
else
head->right=buildTree(head->right,number);
return head;
}
}
/*****************以下是在一棵二叉排序樹插入一個(gè)數(shù)***********************************/
void BiSortTree::insertTree(int key)
{
Head=buildTree(Head,key);
}
/*****************以下是在一個(gè)二叉排序樹查找一個(gè)數(shù)是否存在*************************/
treeNode* BiSortTree::searchTree(int key)
{
return search(Head,key);
}
treeNode* BiSortTree::search(treeNode* head ,int key)
{
if(head==NULL)
return NULL;
if(head->key==key)
return head;
else
{
if(key<head->key )
return search( head->left,key);
else
return search(head->right,key);
}
}
/************以下是在一個(gè)二叉排序樹刪除一個(gè)給定的值*********************************/
BiSortTree::deleteTree(int key)
{
treeNode *p;
p=NULL;
p=search(Head,key);
if(p==NULL)
{
cout<<"Don't find the key";
}
if(p==Head)
{
Head=NULL;
}
else
{
treeNode* parent;
parent=searchParent(Head,p);
if(p->left==NULL&&p->right==NULL)//葉子節(jié)點(diǎn)
{
if(parent->left==p)
{
parent->left=NULL;
}
else
{
parent->right=NULL;
}
}
else//非葉子節(jié)點(diǎn)
{
if(p->right==NULL)//該節(jié)點(diǎn)沒有右孩子
{
if(parent->left==p)
{
parent->left=p->left ;
}
else
{
parent->right=p->left;
}
}
else//該點(diǎn)有左右孩子
{
treeNode * rightMinSon,* secondParent;//secondParent為右子樹中的最小節(jié)點(diǎn)的父親
rightMinSon=searchMinRight(p->right);
secondParent=searchParent(p->right ,rightMinSon);
secondParent->left=rightMinSon->right;
if(p->right==rightMinSon)//右子樹中的最小節(jié)點(diǎn)的父親為p
{
p->right=rightMinSon->right ;
}
p->key=rightMinSon->key ;
}
}
}
}
treeNode* BiSortTree::searchParent(treeNode* head,treeNode* p)
{
if(head->left==p||head->right==p||head==p||head==NULL)
return head;
else
{
if(p->key<head->key)
return searchParent(head->left ,p);
else
return searchParent(head->right ,p);
}
}
treeNode* BiSortTree::searchMinRight(treeNode* head)//找到右子樹中最小的節(jié)點(diǎn)
{
if(head->left ==NULL||head==NULL)
{
return head;
}
else
{
return searchMinRight(head->left);
}
}
/*****************以下是顯示一個(gè)二叉排序樹****************************************/
void BiSortTree::desplayTree(void)
{
showTree(Head);
cout<<endl;
}
void BiSortTree::showTree(treeNode* Head)
{
if(Head!=NULL)
{
showTree(Head->left ) ;
cout<<Head->key<<' ' ;
showTree(Head->right) ;
}
}
/*****************以下是刪除一棵整二叉排序樹************************************/
BiSortTree::~BiSortTree()
{
cout<<"已經(jīng)消除了一棵樹!!!!"<<endl;
destroyTree(Head);
}
void BiSortTree::destroyTree(treeNode* head )
{
if(head!=NULL)
{
destroyTree(head->left );
destroyTree(head->right );
delete head;
}
}
/*********************/
void print()
{
cout<<endl<<endl<<"以下是對(duì)二叉排序樹的基本操作:"<<endl
<<"1.顯示樹"<<endl
<<"2.插入一個(gè)節(jié)點(diǎn)"<<endl
<<"3.尋找一個(gè)節(jié)點(diǎn)"<<endl
<<"4.刪除一個(gè)節(jié)點(diǎn)"<<endl;
}
void main()
{
BiSortTree tree;
int number;
int choiceNumber;
char flag;
while(1)
{
print() ;
cout<<"請(qǐng)選擇你要進(jìn)行的操作(1~4)"<<endl;
cin>>choiceNumber;
switch(choiceNumber)
{
case 1:
tree.desplayTree();break;
case 2:
cout<<"請(qǐng)插入一個(gè)數(shù): "<<endl;
cin>>number;
tree.insertTree(number);
tree.desplayTree();
break;
case 3:
cout<<"請(qǐng)插入你要找數(shù): "<<endl;
cin>>number;
if(tree.searchTree(number)==NULL)
{
cout<<"沒有發(fā)現(xiàn)"<<endl;
}
else
{
cout<<"發(fā)現(xiàn)"<<endl;
}
break;
case 4:
cout<<"請(qǐng)輸入你要?jiǎng)h除的數(shù): "<<endl;
cin>>number;
tree.deleteTree(number);
tree.desplayTree();
break;
default: break;
}
cout<<"你是否要繼續(xù)(Y/N)?"<<endl;
cin>>flag;
if(flag=='N'||flag=='n')
break;
}
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -