C语言数据结构双亲法创建二叉树

た入场券 2022-01-22 11:35 255阅读 0赞

/\*  
\*双亲法创建二叉树  
\*建立双亲节点  
\*创建数据节点  
\*创建一维数组  
\*输入数据  
\*查找指定节点的双亲在数组中的位置  
\*返回指点节点的在数组中的位置  
\*/

#include<stdio.h>
    #include<stdlib.h>
    #define MAXSIZE 100 //一维数组的大小
    //typedef int element;
    static char   name='A';
    typedef struct ptreenode
    {
        char name;
        int parent;//双亲节点下标
    
    }PtreeNode;//数据结构体
    typedef struct ptree
    {
        PtreeNode data[MAXSIZE];
        int r;//根节点在数组中的小标
       int n;//数组中根节点的数目
    }PTree;//总的数据结构体
    PTree*creatptree(int n);//二叉树的双亲表示法的创建
    void printptree(PTree*p);//遍历出二叉树  （层序遍历）
    int  research_ptree(PTree*p,char  x);//查找指定数据在数组中的位置
    PtreeNode getdataptree(PTree*p,char x);//返回指定数据的双亲数据结构体
    void main()
    {
           PTree*p;
           int n;
           char x='B';//为什么不能动态赋值 
             char y='E';
            PtreeNode result;//节点数据结构体
          printf("请输入要输入的节点个数;\n");
            scanf("%d",&n);
          p=creatptree(n);
        if(p==NULL)
            printf("树创建失败:\n");
           else
            printf("树创建成功;\n");
              printf("遍历的结果\n");
              printptree(p);
               printf("\n");
             //printf("请输入要返回数组位置的元素\n");
              //scanf("%c",&x);
             printf("数据在数组中的位置为:%d",research_ptree(p,x));
               printf("\n");
              //printf("请输入要返回其双亲数据的数据:\n");
                  //scanf("%c",&y);
                  result= getdataptree(p,y);
            printf("数据双亲节点为[%c,%d]",result.name,result.parent);
    
    
    }
    PTree*creatptree(int n)//二叉树的双亲表示法的创建
    {
        PTree*p;
        int i;
        p=(PTree*)malloc(sizeof(PTree));
        if(p==NULL)
            return NULL;
        else
        {
            p->r=1;
            p->n=n;
        }
        printf("请输入相关的数据和其双亲节点的下标：\n");
         for(i=0;i<p->n;i++)
         {
             p->data[i].name=name++;
             scanf("%d",&p->data[i].parent);
    
         }
         return p;
    
    
    }
    void printptree(PTree*p)//遍历出二叉树  （层序遍历）
    {
        int i;
        if(p==NULL)
           {
               printf("二叉树遍历失败\n");
               return ;
           }
    
        for(i=0;i<p->n;i++)
        {
            printf("[%c,%d]-",p->data[i].name,p->data[i].parent);
    
        }
    }
    int research_ptree(PTree*p,char x)//查找指定数据在数组中的位置
    {
        int i=0;
        
        if(p->n==0)
          {
              printf("查找失败\n");
               exit(0);
          }
           else
           {
               while(i<p->n&&p->data[i].name!=x)
                     i++;
           }
    
    
        if(i<p->n)//循环是因为有与x值相等的值出现
            return i;
        else
            return 0;//反过来不成立  返回0
    
    }
    PtreeNode getdataptree(PTree*p,char  x)//返回指定数据的双亲数据结构体
    {
        int i;
        i=research_ptree(p,x);
        if(i==-1)
        {
             printf("没有找到数据的双亲节点:\n");
             exit(0);//程序安全退出
        }
    
           else if(p->data[i].parent==-1)
               {
                   printf("数据的双亲节点为树的根节点\n");
                    exit(0);
               }
               else
               {
                   return(p->data[p->data[i].parent]);
               }
    
    }