第1个回答 2019-07-03
/*以下是用c++
实现的二叉排序树的源代码*/
#include<iostream.h>
typedef
struct
TreeNode
{
int
key;
struct
TreeNode
*left;
struct
TreeNode
*right;
}treeNode;
class
BiSortTree
{
public:
BiSortTree(void);
void
desplayTree(void);//显示这个树
void
insertTree(int
key);//在树中插入一个值
deleteTree(int
key);//在树中删除一个值
treeNode*
searchTree(int
key);//在树中查找一个值
~BiSortTree();
private:
treeNode*
buildTree(treeNode*
head,int
number);//建立一个树
treeNode*
search(treeNode*
head
,int
key);//查找
treeNode*
BiSortTree::searchParent(treeNode*
head,treeNode*
p);//查找出p的父亲节点的指针
treeNode*
BiSortTree::searchMinRight(treeNode*
head);//找到右子树中最小的节点
void
showTree(treeNode*
head);//显示
void
destroyTree(treeNode*
head);//删除
treeNode
*Head;
};
/**************以下是建立一个二叉排序树****************/
BiSortTree::BiSortTree()
{
cout<<"建立一棵二叉排序树,请输入你要建树的所有数(以-1
作为结束标志!):
"<<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;
}
}
/*****************以下是在一棵二叉排序树插入一个数***********************************/
void
BiSortTree::insertTree(int
key)
{
Head=buildTree(Head,key);
}
/*****************以下是在一个二叉排序树查找一个数是否存在*************************/
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);
}
}
/************以下是在一个二叉排序树删除一个给定的值*********************************/
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)//叶子节点
{
if(parent->left==p)
{
parent->left=NULL;
}
else
{
parent->right=NULL;
}
}
else//非叶子节点
{
if(p->right==NULL)//该节点没有右孩子
{
if(parent->left==p)
{
parent->left=p->left
;
}
else
{
parent->right=p->left;
}
}
else//该点有左右孩子
{
treeNode
*
rightMinSon,*
secondParent;//secondParent为右子树中的最小节点的父亲
rightMinSon=searchMinRight(p->right);
secondParent=searchParent(p->right
,rightMinSon);
secondParent->left=rightMinSon->right;
if(p->right==rightMinSon)//右子树中的最小节点的父亲为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)//找到右子树中最小的节点
{
if(head->left
==NULL||head==NULL)
{
return
head;
}
else
{
return
searchMinRight(head->left);
}
}
/*****************以下是显示一个二叉排序树****************************************/
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<<"已经消除了一棵树!!!!"<<endl;
destroyTree(Head);
}
void
BiSortTree::destroyTree(treeNode*
head
)
{
if(head!=NULL)
{
destroyTree(head->left
);
destroyTree(head->right
);
delete
head;
}
}
/*********************/
void
print()
{
cout<<endl<<endl<<"以下是对二叉排序树的基本操作:"<<endl
<<"1.显示树"<<endl
<<"2.插入一个节点"<<endl
<<"3.寻找一个节点"<<endl
<<"4.删除一个节点"<<endl;
}
void
main()
{
BiSortTree
tree;
int
number;
int
choiceNumber;
char
flag;
while(1)
{
print()
;
cout<<"请选择你要进行的操作(1~4)"<<endl;
cin>>choiceNumber;
switch(choiceNumber)
{
case
1:
tree.desplayTree();break;
case
2:
cout<<"请插入一个数:
"<<endl;
cin>>number;
tree.insertTree(number);
tree.desplayTree();
break;
case
3:
cout<<"请插入你要找数:
"<<endl;
cin>>number;
if(tree.searchTree(number)==NULL)
{
cout<<"没有发现"<<endl;
}
else
{
cout<<"发现"<<endl;
}
break;
case
4:
cout<<"请输入你要删除的数:
"<<endl;
cin>>number;
tree.deleteTree(number);
tree.desplayTree();
break;
default:
break;
}
cout<<"你是否要继续(Y/N)?"<<endl;
cin>>flag;
if(flag=='N'||flag=='n')
break;
}
}