#include<iostream>
#include<string>
struct feng //记录分数
{
int pshuxue;
int penglish;
int pchinese;
int count;
}total;
class stunode //子节点
{
private:
int id;
string name;
int shuxue;
int english;
int chinese;
stunode *left; //左节点
stunode *right; //右节点
public:
stunode(void); //构造函数
stunode(int sid,string sname,int sshuxue,int senglish,int schinese);
~stunode(void);
void insertleft(stunode* newnode);
void insertright(stunode* newnode);
stunode* returnleft(void);
stunode* returnright(void);
int getid(void);
void setname(string nwname)
{name=nwname;}
void setshuxue(int ssx){shuxue=ssx;}
void setenglish(int se){english=se;}
void setchinese(int sc){chinese=sc;}
friend void printnode(stunode* head); //打印学生分数
friend void pingchengji(stunode* head); //计算平均成绩
};
stunode::stunode(void)
{
left=NULL;
right=NULL;
}
stunode::stunode(int sid,string sname,int sshuxue,int senglish,int schinese)
{
id=sid;
name=sname;
shuxue=sshuxue;
english=senglish;
chinese=schinese;
left=NULL;
right=NULL;
}
stunode::~stunode(void)
{
left=NULL;
right=NULL;
}
void stunode::insertleft(stunode* newnode)
{
left=newnode;
}
void stunode::insertright(stunode* newnode)
{
right=newnode;
}
stunode* stunode::returnleft(void)
{
return left;
}
stunode* stunode::returnright(void)
{
return right;
}
int stunode::getid(void)
{
return id;
}
void printnode(stunode *head)
{
cout<<head->id<<" "<<head->name<<" "<<head->shuxue<<" "<<head->english<<" "<<head->chinese<<endl;
}
void pingchengji(stunode *head)
{
total.pshuxue=total.pshuxue+head->shuxue;
total.penglish=total.penglish+head->english;
total.pchinese=total.pchinese+head->chinese;
total.count=total.count+1;
}
class stutree //二叉树类
{
private:
stunode *root,*newnode,*currnode,*parent;
void print(stunode* temp);
void zonghe(stunode* temp);
int ischild(stunode* pnode,stunode* childnode);
stunode* findnode(const int rid,stunode*& parentnode);
public:
stutree(void);
void creattree(stunode *node);
void prints(void);
stunode* findnode(const int rid);
void insertnode(stunode* temp);
void pingjun(void);
stunode* deletenode(int did);
void deletetree(stunode* temp);
~stutree(void);
};
stutree::stutree(void)
{
root=NULL;
newnode=NULL;
currnode=NULL;
parent=NULL;
}
void stutree::deletetree(stunode* temp)
{
if(temp!=NULL)
{
deletetree(temp->returnleft());
deletetree(temp->returnright());
delete temp;
}
}
stutree::~stutree(void)
{
deletetree(root);
}
void stutree::creattree(stunode *node) //创建二叉树
{
if(root==NULL)
{
root=node;
}
else
{
if(node->getid()<root->getid())
{
parent=root;
currnode=root->returnleft();
}
if(node->getid()>root->getid())
{
parent=root;
currnode=root->returnright();
}
if(node->getid()==root->getid())
{
cout<<"the student was in list"<<endl;
return;
}
while(currnode!=NULL)
{
if(node->getid()==currnode->getid())
{
cout<<"the student was in list"<<endl;
return;
}
if(node->getid()<currnode->getid())
{
parent=currnode;
currnode=parent->returnleft();
}
else
{
parent=currnode;
currnode=parent->returnright();
}
}
if(node->getid()<parent->getid())
{
parent->insertleft(node);
currnode=node;
}
if(node->getid()>parent->getid())
{
parent->insertright(node);
currnode=node;
}
}
}
void stutree::print(stunode* temp)
{
if(temp!=NULL)
{
print(temp->returnleft());
printnode(temp);
print(temp->returnright());
}
}
void stutree::zonghe(stunode* temp)
{
if(temp!=NULL)
{
zonghe(temp->returnleft());
pingchengji(temp);
zonghe(temp->returnright());
}
}
void stutree::prints(void)
{
print(root);
}
stunode* stutree::findnode(const int rid)
{
if(root->getid()==rid)
{
return root;
}
if(rid<root->getid())
{
parent=root;
currnode=root->returnleft();
}
if(rid>root->getid())
{
parent=root;
currnode=root->returnright();
}
while(currnode!=NULL)
{
if(currnode->getid()==rid)
{
return currnode;
}
if(rid<currnode->getid())
{
parent=currnode;
currnode=currnode->returnleft();
}
else if(rid>currnode->getid())
{
parent=currnode;
currnode=currnode->returnright();
}
}
return NULL;
}
stunode* stutree::findnode(const int rid,stunode*& parentnode)
{
if(root->getid()==rid)
{
parentnode=NULL;
return root;
}
if(rid<root->getid())
{
parent=root;
currnode=root->returnleft();
}
if(rid>root->getid())
{
parent=root;
currnode=root->returnright();
}
while(currnode!=NULL)
{
if(currnode->getid()==rid)
{
parentnode=parent;
return currnode;
}
if(rid<currnode->getid())
{
parent=currnode;
currnode=currnode->returnleft();
}
else if(rid>currnode->getid())
{
parent=currnode;
currnode=currnode->returnright();
}
}
}
void stutree::insertnode(stunode* temp)
{
creattree(temp);
}
void stutree::pingjun(void)
{
zonghe(root);
cout<<"shuxue: "<<total.pshuxue/total.count<<endl;
cout<<"english: "<<total.penglish/total.count<<endl;
cout<<"chinese: "<<total.pchinese/total.count<<endl;
}
int stutree::ischild(stunode* pnode,stunode* childnode)
{ //判断父节点和子节点的位子关系
if(pnode==NULL)
{
return -1;
}
if(pnode->returnleft()==childnode)
{
return 1;
}
if(pnode->returnright()==childnode)
{
return 0;
}
}
stunode* stutree::deletenode(int did) //删除节点
{
stunode *parentnode,*temp;
stunode *leftnode,*rightnode;
stunode *minxnode,*minright,*parenode=NULL,*renode;
int postion;
temp=findnode(did,parentnode); //temp是要删除的节点
if(temp==NULL)
{
cout<<"student not find"<<endl;
}
postion=ischild(parentnode,temp);
leftnode=temp->returnleft();
rightnode=temp->returnright();
if(leftnode==NULL && rightnode==NULL) //temp左右节点为空
{
switch(postion)
{
case 1:
parentnode->insertleft(NULL);
break;
case 0:
parentnode->insertright(NULL);
break;
case -1:
break;
}
delete temp;
return root;
}
if(leftnode!=NULL && rightnode==NULL) //有左节点没有右节点
{
switch(postion)
{
case 1:
parentnode->insertleft(leftnode);
break;
case 0:
parentnode->insertright(leftnode);
break;
case -1:
root=root->returnleft();
break;
}
delete temp;
return root;
}
if(leftnode==NULL && rightnode!=NULL) 有右节点没有左节点
{
switch(postion)
{
case 1:
parentnode->insertleft(rightnode);
break;
case 0:
parentnode->insertright(rightnode);
break;
case -1:
root=root->returnright();
break;
}
delete temp;
return root;
}
if(leftnode!=NULL && rightnode!=NULL) 左右节点都有
{
parenode=rightnode;
renode=rightnode; //renode是替换的节点
while(renode->returnleft()!=NULL) //查找替换的节点
{ //被删除节点右子树中最小的节点就是我们要找的替换节点
parenode=renode;//也可以查找被删除节点左子树中最大的节点
renode=renode->returnleft();
}
if(renode==rightnode) //一种情况是:替换节点就是temp的右儿子
{
rightnode->insertleft(leftnode);
}
else{ //如果不是右儿子就执行如下操作
parenode->insertleft(renode->returnright());
renode->insertleft(leftnode);
renode->insertright(rightnode);
}
switch(postion)
{
case -1:
root=renode;
break;
case 1:
parentnode->insertleft(renode);
break;
case 0:
parentnode->insertright(renode);
break;
}
delete temp;
return root;
}
}
void main(void)
{
int select,nid,nshuxue,nenglish,nchinese;
string nname,space;
stunode* newstudent,*findrezult;
stutree stulist;
int wid,deid;
for(;;)
{
cout<<"1>creat a chengji list"<<endl;
cout<<"2>print a list"<<endl;
cout<<"3>find student"<<endl;
cout<<"4>insert a student"<<endl;
cout<<"5>ping jun cheng ji"<<endl;
cout<<"6>delete a student"<<endl;
cout<<"7>chang student information"<<endl;
cout<<"0>exit"<<endl;
cin>>select;
switch(select)
{
case 1:
cout<<"please input a id"<<endl;
cin>>nid;
getline(cin,space,'\n');
cout<<"please input a name"<<endl;
getline(cin,nname,'\n');
cout<<"please input a shuxue"<<endl;
cin>>nshuxue;
cout<<"please input a english"<<endl;
cin>>nenglish;
cout<<"please input a chinese"<<endl;
cin>>nchinese;
newstudent=new stunode(nid,nname,nshuxue,nenglish,nchinese);
if(newstudent==NULL)
{
cout<<"error"<<endl;
exit(1);
}
stulist.creattree(newstudent);
break;
case 2:
stulist.prints();
break;
case 3:
cout<<"please input a id for student"<<endl;
cin>>wid;
findrezult=stulist.findnode(wid);
if(findrezult!=NULL)
{
printnode(findrezult);
}
else
{
cout<<"student not find"<<endl;
}
break;
case 4:
cout<<"please input a id"<<endl;
cin>>nid;
getline(cin,space,'\n');
cout<<"please input a name"<<endl;
getline(cin,nname,'\n');
cout<<"please input a shuxue"<<endl;
cin>>nshuxue;
cout<<"please input a english"<<endl;
cin>>nenglish;
cout<<"please input a chinese"<<endl;
cin>>nchinese;
newstudent=new stunode(nid,nname,nshuxue,nenglish,nchinese);
if(newstudent==NULL)
{
cout<<"error"<<endl;
exit(1);
}
stulist.insertnode(newstudent);
break;
case 5:
stulist.pingjun();
break;
case 6:
cout<<"please input a id"<<endl;
cin>>deid;
stulist.deletenode(deid);
break;
case 7:
cout<<"please input a student id for chenge"<<endl;
cin>>nid;
findrezult=stulist.findnode(nid);
cout<<"20.change name"<<endl;
cout<<"21.change shuxue"<<endl;
cout<<"22.change english"<<endl;
cout<<"23.change chinese"<<endl;
cin>>select;
switch(select)
{
case 20:
getline(cin,space,'\n');
cout<<"please input new name"<<endl;
getline(cin,nname,'\n');
findrezult->setname(nname);
break;
case 21:
cout<<"please input new shuxue"<<endl;
cin>>nshuxue;
findrezult->setshuxue(nshuxue);
break;
case 22:
cout<<"please input new english"<<endl;
cin>>nenglish;
findrezult->setenglish(nenglish);
break;
case 23:
cout<<"please input new chinese"<<endl;
cin>>nchinese;
findrezult->setchinese(nchinese);
break;
}
break;
case 0:
exit(0);
}
}
}
本程序在linux环境下调试通过.程序源代码遵守GPL协议.
参考书目:
<<数据结构C++语言描述>> 作者:William Ford William Topp著 清华大学初版社
<<数据结构(C语言版)>> 作者:黄国瑜 叶乃菁 清华大学出版社
请大家斧正