C语言数据结构孩子兄弟法创建树（非二叉树）

向右看齐 2022-01-22 11:37 317阅读 0赞

/\*  
\*孩子兄弟法创建树（不是二叉树）  
\*先输入长子节点再输入孩子节点  
\*用树的遍历去实现类似二叉树的遍历  
\*使用创建链式二叉树的方法创建孩子兄弟树  
\*/

#include<stdlib.h>
    #include<stdio.h>
    #include<string.h>
    #define MAXSIZE 255
    static int id=0;
    typedef struct //数据的结构体
    {
        int id;
        char name[MAXSIZE];
    }ElementType;
    typedef struct cbtree
    {
        ElementType data;
        struct cbtree *firstchilld;//长子节点
        struct cbtree *nextsibling;//兄弟节点
    }CbTree;//树节点结构体
    int  createcbtree(CbTree*node);//创建树（孩子兄弟法）
    void initcbtree(CbTree*tree);//初始化树
    void testcbtree();//测试函数
    void preordercbtree(CbTree*node);//前序遍历
    void main()
    {
        testcbtree();//测试函数
    
    }
    void initcbtree(CbTree*tree)//初始化树
    {
        tree->firstchilld=NULL;//初始化空树的长子节点 为创建孩子节点空间 做前提
        tree->nextsibling=NULL;
    
    }
    void testcbtree()//测试函数
    {
        CbTree*tree;
        tree=(CbTree*)malloc(sizeof(CbTree));
         if(tree!=NULL)
         {
              initcbtree(tree);
            printf("请输入根节点的数据:\n");
             createcbtree(tree);
             printf("前序遍历的结果为;\n");
             preordercbtree(tree);//遍历树
    
    
         }
    }
    int createcbtree(CbTree*node)//创建树（孩子兄弟法）
    {
        char inputname  [MAXSIZE];
         gets(inputname);
          if(strcmp(inputname,"\0")==0)
          {
              return 0;
           }
          /*if(node==NULL)//采用层次规则创建
          {
             node=(CbTree*)malloc(sizeof(CbTree));
              node->firstchilld=NULL;
              node->nextsibling=NULL;
          }*/
    
          node->data.id=++id;
          strcpy(node->data.name,inputname);
          node->firstchilld=(CbTree*)malloc(sizeof(CbTree));
           node->nextsibling=(CbTree*)malloc(sizeof(CbTree));
          printf("请输入长子节点");
           if(createcbtree(node->firstchilld)==0)
           {
               free(node->firstchilld);
               node->firstchilld=NULL;
    
           }
            printf("请输入兄弟节点");
            if(createcbtree(node->nextsibling)==0)
            {
                free(node->nextsibling);
                node->nextsibling=NULL;
    
            }
            return 1;
    
    }
    void preordercbtree(CbTree*node)//前序遍历（孩子兄弟法）
    {
    
            if(node!=NULL){
              printf("[%d,%s]-",node->data.id,node->data.name);
               CbTree*p=node->firstchilld;
              preordercbtree(p);//if的判断用在判断长子节点的结束 便于接下来的兄弟节点的遍历
              //一直遍历长子节点 之后再遍历兄弟节点  长子节点为空 结束长子节点的遍历
               while(p)//长子节点结束 一直遍历兄弟节点  兄弟节点结束再遍历长子节点
               {
                   p=p->nextsibling;
                   preordercbtree(p);
               }
            }
    
    
    
    
    
    
    }