二叉樹——家譜管理系統

二叉樹——家譜管理系統

#include<iostream>
#include<string>
using namespace std;

class Node
{
friend class Person;
public:
Node():name("?"),lchild(NULL),rchild(NULL){};
private:
string name;
Node* lchild;
Node* rchild;
};

class Person
{
public:
Person():root(NULL){};
void Create(Person& L);
void Add(Person& L);
void Delete(Person& L);
void Insert(Person& L);
void Update(Person& L);
void Show(Person& L);
void Print(Node* p);
Node* Lookup(Node* p,string name);
private:
Node* root;
};

void Person::Create(Person& L)
{
cout<<"請輸入祖先的名字:";
string rootname;
cin>>rootname;
Node* p=new Node;
p->name=rootname;
L.root=p;
cout<<"此家譜的祖先:"<<p->name<<endl;
}

void Person::Add(Person& L)
{
cout<<"請輸入要創立家庭的人的姓名:";
string rootname;
cin>>rootname;
Node* s=Person::Lookup(L.root,rootname);
if(s){
Node* r=s;
cout<<"請輸入"<<s->name<<"的兒女數:";
int n;
cin>>n;
int m=n;
cout<<"請依次輸入"<<s->name<<"的兒女的姓名:";
while(m){
string na;
cin>>na;
Node* p=new Node;
p->name=na;
if(m==n){
s->lchild=p;
s=s->lchild;
}
else{
s->rchild=p;
s=s->rchild;
}
m--;
}
Person::Print(r);
}
else{
cout<<"查無此人，請重新輸入!"<<endl;
Person::Add(L);
}
}

Node* Person::Lookup(Node* p,string name)//是否可以用分治查找
{
Node* t=NULL;
Node* s[100];
int top=0;
while(p||top>0)
{
while(p)
{
if(p->name==name)
{
t=p;
}
s[++top]=p;
p=p->lchild;
}
p=s[top--];
p=p->rchild;
}
return t;
}

Node* Person::Lookup(Node* p,string name)
{
Node* t=NULL;
if(p->name==name)
{
t=p;
return t;
}
Node* s=Person::Lookup(p->lchild,name);
Node* r=Person::Lookup(p->rchild,name);
if(s) t=s;
if(r) t=r;

return t;
}

void Person::Print(Node* p)
{
cout<<p->name<<"的第一代子孫是:"<<p->lchild->name<<'\t';
p=p->lchild;
while(p->rchild)
{
cout<<p->rchild->name<<'\t';
p=p->rchild;
}
cout<<endl;
}

void Person::Insert(Person& L)
{
cout<<"請輸入要添加子女的人的姓名:";
string rootname;
cin>>rootname;
Node* s=Person::Lookup(L.root,rootname);
if(s)
{
Node* r=s;
cout<<"請輸入"<<s->name<<"新添加的子女的姓名:";
Node* p=new Node;
string name;
cin>>name;
p->name=name;
if(!s->lchild)
{
s->lchild=p;
}
else
{
s=s->lchild;
while(s->rchild)
{
s=s->rchild;
}
s->rchild=p;
}
Person::Print(r);
}
else
{
cout<<"查無此人，請重新輸入!"<<endl;
Person::Insert(L);
}
}

void Person::Delete(Person& L)
{
cout<<"請輸入要解散家庭的人的姓名:";
string rootname;
cin>>rootname;
Node* s=Person::Lookup(L.root,rootname);
if(s)
{
if(s->lchild)
{
cout<<"要解散家庭的人是:"<<s->name<<endl;
Person::Print(s);
s->lchild=NULL;
}
else
{
cout<<s->name<<"尚未有家庭!";
}
}
else
{
cout<<"查無此人，請重新操作!"<<endl;
Person::Delete(L);
}
}

void Person::Update(Person& L)
{
cout<<"請輸入要更改姓名的人的目前姓名:";
string rootname;
cin>>rootname;
Node* s=Person::Lookup(L.root,rootname);
if(s)
{
cout<<"請輸入更改後的名字:";
string name;
cin>>name;
s->name=name;
cout<<rootname<<"已更改為"<<s->name<<endl;
}
else
{
cout<<"查無此人，請重新操作!"<<endl;
Person::Update(L);
}
}

void main()
{
cout<<" 家譜管理系統 "<<endl;
cout<<" 請選擇要執行的操作: "<<endl;
cout<<" A.完善家譜 "<<endl;
cout<<" B.添加家庭成員 "<<endl;
cout<<" C.解散局部家庭 "<<endl;
cout<<" D.更改家庭成員姓名 "<<endl;
cout<<" E.退出程序 "<<endl;

cout<<" 首先建立一個家譜"<<endl;
Person L;
L.Create(L);
char ch;
while(ch!='F')
{
cout<<" 請輸入要執行的操作:";
cin>>ch;
switch(ch)
{
case'A':
{
L.Add(L);
break;
}
case'B':
{
L.Insert(L);
break;
}
case'C':
{
L.Delete(L);
break;
}
case'D':
{
L.Update(L);
break;
}
case'E':
break;
default:
cout<<"請輸入正確操作!"<<endl;
}
}
}