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



}