jiajupu.cpp

用二叉树表示族谱

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

struct BinaryNode 
{ 
string data; 
BinaryNode *left,*right,*parent; 
}; 

BinaryNode* create() 
{ 
//创建根结点 
BinaryNode *root; 
root=new BinaryNode; 
cout  << "输入根结点的数据(以'#'为空):"; 
string str; 
cin>>str; 
root->data=str; 
root->left=NULL;//初始化根结点的左孩子指针 
root->right=NULL;//初始化根结点的右孩子指针 
root->parent=NULL; 

if(root->data!="#") 
{ 
//创建根结点的左子树 
cout <<"请输入" <<root->data <<"的左孩子："; 
root->left=create();                                     
//创建根结点的右子树 
cout <<"请输入" <<root->data << "的右孩子:"; 
root->right=create(); 
} 

return root;                  //返回根结点的地址 
} 

//先序遍历函数 
void inorder(BinaryNode *root) 
{ 
if (root==NULL) return; //如果是空树，则返回 
else 
{ 
cout << root->data << "\t";  //访问根结点 
inorder(root->left); //先先序遍历左子树 
inorder(root->right); //最后先序遍历右子树 

} 
} 

void restor(BinaryNode *root) 
{ 
ofstream out2; 
out2.open("out.txt",ios::out|ios::app); 
if(root==NULL) return; 
else 
{ 
out2 << root->data; 
restor(root->left); 
restor(root->right); 
} 
} 

void TreeDestory(BinaryNode* &root) 
{ 
  if(root!=NULL) 
  { 
  TreeDestory ( root->left ) ;  // 删除左子树 
      TreeDestory ( root->right) ; // 删除右子树 
  delete root ; // 释放根结点的内存 
          root = NULL ; 
  } 
} 
void DispTree1(BinaryNode* b) 
{ 
if(b!=NULL) 
{ 
cout << b->data; 
if(b->left!=NULL||b->right!=NULL) 
{ 
cout << "("; 
DispTree1(b->left); 
if(b->right!=NULL) 
cout << ","; 
DispTree1(b->right); 
cout << ")"; 
} 
} 
} 

void DispTree2(BinaryNode* b) 
{ 
BinaryNode *St[30],*p; 
int Level[30][2],top,n,i,width=4; 
if(b!=NULL) 
{ 
cout <<">>家谱凹入表示法:\n"; 
top=1; 
St[top]=b; 
Level[top][0]=width; 
while(top>0) 
{ 
p=St[top]; 
n=Level[top][0]; 
for(i=1;i <=n;i++) 
cout << " "; 
cout << p->data; 
for(i=n+1;i <=20-6;i+=2) 
cout << "—"; 
top--; 
if(p->right!=NULL) 
{ 
top++;
St[top]=p->right;
Level[top][0]=n+width;
Level[top][1]=2; 
} 
if(p->left!=NULL) 
{top++;
St[top]=p->left;
Level[top][0]=n+width;
Level[top][1]=1;} 
} 
} 
} 

BinaryNode *FindNode(BinaryNode * bt,char xm[])              //采用先序递归算法找name为xm的结点 
{ 
BinaryNode *p=bt; 
if(p==NULL) 
return(NULL); 
else 
{ 
if(p->data.compare(xm)==0) 
return(p); 
else 
{ 
bt=FindNode(p->left,xm); 
if(bt!=NULL) 
return(bt); 
else 
return(FindNode(p->right,xm)); 
} 
} 
} 

void FindSon(BinaryNode * bt)            //输出某人所有儿子 
{
char xm[10]; 
BinaryNode *p; 
cout <<"输入父亲姓名:"; 
cin>>xm; 
p=FindNode(bt,xm); 
if(p==NULL) 
cout << "不存在此父亲!"; 
else 
{ 
p=p->left; 
p=p->right;
if(p==NULL)
cout << "没有儿子";
else
{
cout << "有以下儿子";
while (p!=NULL)
{cout << p->data;
p=p->right;
}
}
}
if(p==NULL) 
cout <<"无左孩子"; 
else 
{ /*
p=p->right; 
if(p==NULL) 
cout <<"无右孩子."; 
else 
{ 
cout <<"输出孩子:"<<xm; 
while(p!=NULL) 
{ 
cout << p->data; 
p=p->right; 
} 
cout << "\n"; 
} 
} 
int top=-1; 
string s[30]; 
while(p!=NULL||top!=-1) 
{ 
while(p!=NULL) 
{ 
cout << p->data <<"\t"; 

s[top++]=p; 
p=p->left; 
} 
if(top!=-1) 
{ 

p=s[top--]; 
p=p->right; 
} 
} 

*/} } 


int Path(BinaryNode *bt,BinaryNode *s) 
{ 
BinaryNode *St[30]; 
BinaryNode *p; 
int i,flag,top=-1;                    //栈指针置初值 
do 
{ 
while(bt) 
{ 
top++; 
St[top]=bt; 
bt=bt->left; 
} 
p=NULL; 
flag=1; 
while(top!=-1&&flag) 
{ 
bt=St[top]; 
if(bt->right==p) 
{ 
if(bt==s) 
{ 
cout << "所有祖先:"; 
for(i=0;i <top;i++) 
cout << St[i]->data; 
cout << "\n"; 
return 1; 
} 
else 
{ 
top--; 
p=bt; 
} 
} 
else 
{ 
bt=bt->right; 
flag=0; 
} 
} 

}while(top!=-1); 
return 0; 
} 


void Ancestor(BinaryNode * bt) 
{ 
BinaryNode *p; 

char xm[10]; 
cout << "输入姓名"; 
cin>>xm; 
p=FindNode(bt,xm); 
if(p!=NULL) 
Path(bt,p);
else 
cout << "不存在"; 
} 


void main() 
{ 
BinaryNode *rt; 
int d; 
do 
{ 
cout << "请选择功能:1文件操作功能,2家谱操作功能,3返回"; 
cin>>d; 
switch(d) 
{ 
case 1: 
{ 
while(d!=5) 
{ 
cout << "1记录输入;2记录输出;3清除全部文件记录;4将家谱记录存盘;5返回."; 
cin>>d; 
switch(d) 
{ 
case 1: 
{ 
rt=create(); 
break; 
} 
case 2: 
{ 
cout << "其中先序遍历序列："; 
inorder(rt); 
cout << endl; 
break; 
} 
case 3: 
{ 
TreeDestory(rt); 
cout << "清除完成;" << endl; 
break; 
} 
case 4: 
{ 
restor(rt); 
break; 
} 
case 5: break; 
} 
} 
break; 
} 
case 2: 
{ 
cout <<"1用括号表示法;2凹入法输出家谱二叉树;3查找某人所有的儿子;4查找某人的所有祖先;5返回."; 
while(1) 
{ 
cin>>d; 
switch(d) 
{ 
case 1:DispTree1(rt);break; 
case 2:DispTree2(rt);break; 
case 3:FindSon(rt);break; 
case 4:Ancestor(rt);break; 
case 5:break; 
} 
} 
} 
} 
}while(d!=3); 



}