树的存储结构--双亲表示法

树的存储结构--双亲表示法

#include<stdio.h>
#include<stdlib.h>
#define maxsize 20
#include<iostream>
using namespace std;
typedef struct 
{
    char data;
 int parent;//双亲位置
}pnode;
typedef struct
{
 pnode s[maxsize];
 int n;  //结点数；
}ptree;
//初始化，也可以不初始化
void inittree(ptree &T)
{  
T.n=0;
} 
//创建并存储
void create(ptree &T)
{   
 
 int i;
 cout<<"请输入节点数：";
 cin>>T.n;
 cout<<"请输入节点基本信息->节点的值，双亲位置（根节点的双亲位置为-1）：";
 for(i=0;i<T.n;i++)
 {
  cin>>T.s[i].data>>T.s[i].parent;
 }
}
//查找c的父亲
void reserch(ptree &T,char c)
{   
 
 for(int i=0;i<T.n;i++)
 {
  if(T.s[i].data==c)   //有二种情况；有可能为根节点；有可能不是根节点；
  {
   
   if(T.s[i].parent>=0)
   { 
    cout<<"其父亲为：";
    cout<<T.s[ T.s[i].parent].data<<endl;
    break;  //因为父亲只有一个找到后立即结束整个for(int i=0;i<T.n;i++)循环
   }
   else 
   {
    cout<<"其为根节点所以没有父亲"<<endl;
    break;
   }
  }
  else if(T.s[i].data!=c&&i>=T.n-1)  // //在整个数组中层层寻找字符c,并且寻遍整个数组(i>=T.n-1为界)都没找到
  {
   cout<<"该字符不在范围内"<<endl;
  }
  
 }
 
}
//查找c的孩子
void reserch2(ptree &T,char c)
{   
 
 for(int i=0;i<T.n;i++)
 {
  if(T.s[i].data==c) //找到c；有二种情况：有左右孩子或左孩子或右孩子的节点；为叶子；
  {   
   int m=0;//记录孩子的个数
   for(int j=0;j<T.n;j++) 
   {   
    
    if(T.s[j].parent==i)
    {  
     m++;  
     cout<<"其孩子为：";
     cout<<T.s[j].data<<endl;
    } //可能有多个孩子所以找到一个孩子后没有结束整个for(int j=0;j<T.n;j++)循环；
    else if(T.s[j].parent!=i&&j>=T.n-1&&m==0) //确定其为叶子；因为如果没有m=0,即便查找的字符不是叶子而整个数组最后一个字符即使
    {                                         //不是其孩子也满足T.s[j].parent!=i&&j>=T.n-1，也会输出语句"其为叶子所以没有孩子"；
     cout<<"其为叶子所以没有孩子"<<endl;
    }
   }
   break; //找到c并且找到了的孩子后结束整个for(int i=0;i<T.n;i++)循环；因为数组中仅且只有一个字符c
  }
  
  else  if(T.s[i].data!=c&&i>=T.n-1)  //在整个数组中层层寻找字符c,并且寻遍整个数组(i>=T.n-1为界)都没找到
  {
   cout<<"该字符不在范围内"<<endl;
  }
  
 }
 
}
//打印
void print(ptree &T)
{
 for(int i=0;i<T.n;i++)
  cout<<T.s[i].data<<" "<<T.s[i].parent<<endl;
    
}
void main()
{   
 char c;
 ptree T;
 create(T);
 cout<<"您刚才输入的基本信息为："<<endl;
    print(T);
 cout<<"请输入要查找父亲的字符："<<endl;
    while((cin>>c&&c!='n'))  //当输入的字符为n时结束循环
 {  
    reserch(T,c);
    cout<<"请输入要查找孩子的字符："<<endl;
 cin>>c;
    reserch2(T,c);
 cout<<"请输入要查找父亲的字符："<<endl;
 }
  
}