C语言数据结构顺序二叉树的创建、遍历

淡淡的烟草味﹌ 2022-01-21 01:03 187阅读 0赞

/\*  
\*顺序二叉树的创建  
\*初始化  
\*创建  
\*测试  
\*递归的使用  
\*遍历其节点  
\*/

#include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    #define MAXSIZE 1024
    typedef char SeqTree[MAXSIZE];//自己定义的一个字符数组
    void init_seqtree(SeqTree tree);//二叉树的初始化
    void creat_seqtree(SeqTree tree ,int i);//二叉树的创建
    void test_seqtree();//测试函数
    char getdata_seqtree(SeqTree tree);//得到根节点的字符
    int length_seqtree(SeqTree tree);//得到树的节点数
    int depth_seqtree(SeqTree tree);//得到树的深度
    int main()
    {
        test_seqtree();//测试函数
    
        return 0;
    }
    void init_seqtree(SeqTree tree)//二叉树的初始化
    {
        int i;
        for(i=0;i<MAXSIZE;i++)
              tree[i]='\0';
    }
    void creat_seqtree(SeqTree tree,int i)//二叉树的创建
    {
        char ch;
        ch=getchar();
        fflush(stdin);
        if(ch=='^')
        {
            tree[i]='\0';
            return ;
    
        }
        tree[i]=ch;
        printf("请输入左孩子节点:\n");
        creat_seqtree(tree,2*i+1);
        printf("请输入右孩子节点:\n");
         creat_seqtree(tree,2*(i+1));
    }
    void test_seqtree()//测试函数
    {
        SeqTree tree;
        init_seqtree(tree);
        printf("请输入根节点的数据:\n");
         creat_seqtree(tree,0);
         int i;
         for(i=0;i<15;i++)
             printf("%d\t",tree[i]);
             printf("该二叉树的根节点为:%d\n", getdata_seqtree(tree));
             printf("该二叉树的长度为:%d\n",length_seqtree(tree));
             printf("该二叉树的深度为:%d\n",depth_seqtree( tree));
    }
    char getdata_seqtree(SeqTree tree)//得到根节点的字符
    {
         return tree[0];
    }
    int length_seqtree(SeqTree tree)//得到树的节点数
    {
        int i;
        int  n=0;
        for(i=0;i<MAXSIZE;i++)
              {if(tree[i]=='\0')
               continue;
               else
                n++;
              }
               return n;
    }
    int depth_seqtree(SeqTree tree)//得到树的深度
    {
        //树的第k层节点数最大为(2^k)-1
        int depth=0;
        /*
        //考虑极端情况的出现 假如一次循环都没有执行 结果会是怎样 从这里出发
         //假如循环结束的话 层数为一  depth等于一的话 循环第一次结束 结果为2 不满足
        */
       int len=length_seqtree(tree);
        while((int)pow(2,depth)-1<len)
                depth++;
             return depth;
    }