数据结构-课程设计:二叉排序树的实现
发布网友
发布时间：2022-04-25 14:51
共3个回答
热心网友
时间：2022-05-01 23:24
代码写好了。
VC下经测试通过。
不过如果你还要论文之类的或者设计文档，我也比较难帮到你了。
#include <iostream>
using namespace std;
class node
{
public:
node(int i):data(i),left(NULL),right(NULL){}
void inorder(node *&root) //中序遍历，符合升序输出
{
if(root!=NULL)
{
inorder(root->left);
cout<<root->data<<' ';
inorder(root->right);
}
}
void insert(node *&ptr,int item) //在查找树中插入元素
{
if(ptr==NULL)
ptr=new node(item);
else if(item<ptr->data)
insert(ptr->left,item);
else insert(ptr->right,item);
}
node *find(node *&ptr,int item) //在查找树中查找元素,找到返回所在结点指针，找不到返回空指针。
{
if(ptr==NULL)
return NULL;
if(ptr->data==item)
return ptr;
else if(item<ptr->data)
find(ptr->left,item);
else find(ptr->right,item);
}
node *&findy(node *&ptr,int item) //在查找树中查找肯定存在的元素,并返回其引用
{
if(ptr->data==item)
return ptr;
else if(item<ptr->data)
findy(ptr->left,item);
else findy(ptr->right,item);
}
node* rl(){return left;}
node* rr(){return right;}
void dele(node *&ptr) //删除值为item所在结点
{
if(ptr->rl()==NULL&&ptr->rr()==NULL)
ptr=NULL;
else if(ptr->rr()==NULL)
ptr=ptr->rl();
else
ptr=ptr->rr();
}
private:
int data;
node *left; //左孩子结点
node *right; //右孩子结点
};
int main()
{
int t,i=0,j;
cout<<"输入数字个数(结点个数):";
cin>>t;
cout<<"输入"<<t<<"个数字，数字之间用空格隔开:";
cin>>j;
node *x=new node(j);
for(;i<t-1;i++)
{
cin>>j;
x->insert(x,j);
}
cout<<"中序遍历为:";
x->inorder(x); //作中序遍历
cout<<"\n输入操作(当输入-1时程序结束):"<<endl;
cin>>j;
while(j!=-1)
{
node *t=x->find(x,j); //定位结点
if(t!=NULL)
{
node *&y=x->findy(x,j);
x->dele(y);
cout<<"中序遍历为:";
x->inorder(x);
}
else cout<<"无"<<j;
cout<<"\n输入操作(当输入-1时程序结束):"<<endl;
cin>>j;
}
return 0;
}
附测试数据一组
8
22 33 1 50 88 99 77 55
33
50
51
55
-1
有什么不明的话可以M我或者留言我。
热心网友
时间：2022-05-02 00:42
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;
}
}
热心网友
时间：2022-05-02 02:17
