二叉树——家谱管理系统

二叉树——家谱管理系统

二叉树——家谱管理系统

#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;
  }
 }
}

二叉树的常见问题及其解决程序

【递归】二叉树的先序建立及遍历

在JAVA中实现的二叉树结构

【非递归】二叉树的建立及遍历

二叉树递归实现与二重指针