C语言数据结构顺序二叉树（改进版）（创建、遍历、求深度、长度）

短命女 2022-01-16 00:23 187阅读 0赞

/\*

*  顺序二叉树的创建  
    \*顺序存储结构  
    \*左孩子节点的下标为2乘以i+1  
    \*右孩子节点的下标为2乘以(i+1)  
    \*采用递归的方式进行处理  
    \*操作 （遍历、创建、求长度、求深度）  
    \*/

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<math.h>
    #define ERROR 0
    #define OK 1
    #define MAXSIZE 1024//数组的最大长度
    #define NAMESIZE 255//字符串的最大长度
    typedef char*NameType;//字符串的指针数据类型
    typedef int IdType;//数据域的编号的数据类型
    static int id=0;//数据域的编号
    typedef struct elementtype
    {
        IdType id;
        NameType name;
    
    
    }ElementType;//数据域的结构体
    typedef struct seqtree
    {
        ElementType *data;//数据域 的指针
        int count;//数据域的节点的个数
    }Seq_Tree;//树的结构体
    void INit_seqtree(Seq_Tree*tree);//顺序二叉树的初始化
    void create_seqtree(Seq_Tree*tree,int i);//二叉树的创建
    void Display_seqtree(Seq_Tree*tree);//二叉树的遍历
    int length_seqtree(Seq_Tree *tree);//计算树的长度
    int deepth_seqtree(Seq_Tree *tree);//计算树的深度
    void main()
    {
        Seq_Tree*tree;
          tree=(Seq_Tree*)malloc(sizeof(Seq_Tree));
          if(tree!=NULL)
            //对其进行初始化
            INit_seqtree(tree);
            //对其进行创建
            printf("请输入根节点的数据：");
            create_seqtree(tree,0);
            printf("树的节点的个数为%d\n",tree->count);
            printf("遍历的结果:\n");
             Display_seqtree(tree);
             printf("\n");
             printf("树的长度为:%d\n",length_seqtree(tree));
               printf("树的深度为%d\n",deepth_seqtree(tree));
    
    }
    void INit_seqtree(Seq_Tree*tree)//顺序二叉树的初始化
    {
         tree->data=(ElementType*)malloc(sizeof(ElementType)*MAXSIZE);//对其进行分配空间
        //对数组的元素进行初始化
        int i;//循环变量
          for(i=0;i<MAXSIZE;i++)
              {
                  tree->data[i].name=(NameType)malloc(sizeof(char)*NAMESIZE);
                  strcpy(tree->data[i].name,"^");//对其数据域的名称进行初始化
                  tree->data[i].id=-1;
            }
               tree->count=0;//计数
    }
    void  create_seqtree(Seq_Tree*tree,int i)//二叉树的创建
    {
           char name[NAMESIZE];
    
             gets(name);
            if(strcmp("\0",name)==0)
            {
                return ;
            }
                  else
                  {
                      //tree->data[i].name=(NameType)malloc(sizeof(char)*NAMESIZE);
                        strcpy(tree->data[i].name,name);
                        tree->data[i].id=++id;
                        tree->count++;//树节点的个数
                     
                    }
                  printf("左孩子：");
                  create_seqtree(tree,2*i+1);
                  printf("右孩子：");
                    create_seqtree(tree,2*(i+1));
    }
    void Display_seqtree(Seq_Tree*tree)//二叉树的遍历
    {
          int  i;//循环变量
          for(i=0;i<15;i++)
          printf("[%d,%s]->",tree->data[i].id,tree->data[i].name);
    
    }
    int length_seqtree(Seq_Tree *tree)//计算树的长度
    {
        int i;//循环变量
        int count=0;//计数的变量
           for(i=0;i<MAXSIZE;i++)
           {
               if(strcmp(tree->data[i].name,"^")==0)
                  continue;
                  else
                  count++;
    
           }
              return count;
    
    }
    int deepth_seqtree(Seq_Tree *tree)//计算树的深度
    {
        int len=length_seqtree(tree);//树的长度
         int length=1; //树的每层节点数至多为（2^k-1）
        while(pow(length,2)<len)
          {
              length++;
          }
            return length;//树的最大深度
    
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjEzNjM0_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjEzNjM0_size_16_color_FFFFFF_t_70]: /images/20220115/74e06b13cc71410897d13e8506bbe3cd.png