C语言数据结构二叉排序算法(二叉排序树)

女爷i 2022-01-21 04:35 248阅读 0赞

/\*二叉排序树的相关操作  
\*二叉排序树的创建使用二级指针  
\*顺序表的创建 顺序表的数据递增排序  
\*对树的节点的数据进行赋值操作  
\*利用二分查找法进行二叉排序树的创建（递归实现二叉排序树的创建）  
\*对数据进行查找 （递归实现）  
\*对数据进行插入  
\*/

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define MAX_SIZE 1024 //顺序表的节点的个数
    #define MAX_NAME 255 //字符串的最大长度
    #define OK 1
    #define ERROR 0
    typedef int Statu;//返回值的数据类型
    typedef  int KeyType;//关键字的数据类型
    typedef char* Value_Type;//表节点的名称标记
    typedef struct element
    {
        KeyType key;//关键字
        Value_Type value;//标志名称
    
    }ElementType;//顺序表的数据节点的结构体
    typedef struct seqlist
    {
        ElementType *datas;//顺序表的数组（指针类型）
          int length;//顺序表的长度
    }SeqList;//顺序表的结构体类型
    typedef struct treenode
    {
        ElementType data;
        struct treenode *Lchild;//左孩子节点
        struct treenode *Rchild;//右孩子节点
    
    }TreeNode;//二叉排序树结构体
    #define fun(M) M=(TreeNode*)malloc(sizeof(TreeNode));
    void Init_seqlist(SeqList *s);//顺序表的初始化
    void  creat_seqlist(SeqList*s);//顺序表的创建
    void sort_seqlistdata(SeqList*s);//对顺序表的元素进行递增排序
    void Init_binarytree(TreeNode**tree);//对二叉树的根节点进行初始化
    void creat_binarytree(TreeNode**tree,SeqList *s,int L,int H);
    //利用二分查找法的规则进行二叉排序树的创建
    void Inorder_traverse(TreeNode*node);//对二叉排序树进行递增遍历
    void search_treenode(TreeNode*tree,int key,TreeNode**node);//查找指定节点数据函数
    //查找数据 返回数据所在的指针位置 为空代表没有找到
    void Insert_node(TreeNode**tree,ElementType ele);//在合适位置处插入节点 继续保持有序
    void test();//测试函数
    void main()
    {
        test();//测试函数
    }
    void Init_seqlist(SeqList *s)//顺序表的初始化
    {
        s->datas=(ElementType*)malloc(sizeof(ElementType)*MAX_SIZE);
        s->length=0;//对顺序表的长度进行初始化
    }
    void  creat_seqlist(SeqList*s)//顺序表的创建
    {
        int keys[]={12,54,89,99,21};
        int i;//循环变量
        char*values[]={"c语言","c++","c#","java","JavaScript"};
        int len=sizeof(keys)/sizeof(keys[0]);
          for(i=0;i<len;i++)
          {
              s->datas[i].key=keys[i];
              s->datas[i].value=(Value_Type)malloc(sizeof(char)*MAX_NAME);
              strcpy(s->datas[i].value,values[i]);s-
              s->length++;
          }
    }
    void sort_seqlistdata(SeqList*s)
    {
        int  i=s->length-1;//比较的轮数
        int j;
        int flag;
        ElementType t;
          while(flag)
          {
              flag=0;//结束for循环的标志
              for(j=0;j<i;j++)
              {
                  if(s->datas[j].key>s->datas[j+1].key)
                  {//交换数据
                      t=s->datas[j];
                      s->datas[j]=s->datas[j+1];
                      s->datas[j+1]=t;
                      flag=1;
                }
              }
              i--;//比较的轮数减一
          }
    }
    void Init_binarytree(TreeNode**tree)//对二叉树的根节点进行初始化
    {
        (*tree)=(TreeNode*)malloc(sizeof(TreeNode));
        (*tree)->Lchild=NULL;//对根节点进行初始化操作
        (*tree)->Rchild=NULL;
    }
    void creat_binarytree(TreeNode**tree,SeqList *s,int L,int H)//利用二级指针创建操作（？？？）
    {
            int  M=(L+H)/2;
          if(L>H)
            return ;//当节点的数据为空时  退出循环
            //创建一个二叉排序树
           //根据二分法创建一个二叉排序树
    
          if((*tree)==NULL)//根节点为空  对根节点再次进行初始化
          {
             (*tree)=(TreeNode*)malloc(sizeof(TreeNode));
              (*tree)->Lchild=NULL;
              (*tree)->Rchild=NULL;
           }
           (*tree)->data.key=s->datas[M].key;
           (*tree)->data.value=(Value_Type)malloc(sizeof(char)*10);
           strcpy((*tree)->data.value,s->datas[M].value);
            //创建左孩子节点
           creat_binarytree(&((*tree)->Lchild),s,L,M-1);//使用二级指针
           //创建右孩子节点
           creat_binarytree(&((*tree)->Rchild),s,M+1,H);
    }
    void Inorder_traverse(TreeNode*node)
    {
         if(node!=NULL)
        {
    
               Inorder_traverse(node->Lchild);
              printf("[%d,%s]->",node->data.key,node->data.value);
              Inorder_traverse(node->Rchild);
        }
    }
    void test()//测试函数
    {
        SeqList*s;
        int i;
         TreeNode*node;
         ElementType data;//插入元素的结构体
         int key;//待查找的数据
        TreeNode*tree;
        Init_seqlist(s);
         Init_binarytree(&tree);
    
        //创建顺序表
        creat_seqlist(s);
         sort_seqlistdata(s);
    
           printf("顺序表遍历的结果为:\n");
             for(i=0;i<s->length;i++)
                printf("%d %s\n",s->datas[i].key,s->datas[i].value);
                 creat_binarytree(&tree,s,0,s->length-1);
                 printf("二叉排序树遍历的结果为:\n");
          Inorder_traverse(tree);
          printf("\n");//换行
            printf("请输入要查询的数据：\n");
              scanf("%d",&key);
              search_treenode(tree,key,&node);
              if(node==NULL)
              {
                  printf("查找数据失败:\n");
              }
              else
              {
                  printf("查询成功\n");
                  printf("查找的数据为[%d,%s]\n",node->data.key,node->data.value);
              }
              printf("\n");
              printf("请输入要插入的数据:\n");
              scanf("%d",&(data.key));
              data.value=(Value_Type)malloc(sizeof(char)*20);
                 strcpy(data.value,"pathon");
                 //printf("data的数据为:%d %s",data.key,data.value);
                 Insert_node(&tree,data);
                 printf("插入后的遍历的结果为:\n");
                 Inorder_traverse(tree);
    
    }
    void  search_treenode(TreeNode*tree,int key,TreeNode**node)
    //当找到时node的指针指的是数据的地址 否则返回为空指针
    {
        if(tree==NULL||tree->data.key==key)
            *node=tree;//包括找到和没找到的情况
        else if(key>tree->data.key)
        {
            search_treenode(tree->Rchild,key,node);
    
        }
        else
        {
            search_treenode(tree->Lchild,key,node);
        }
    
    }
    void Insert_node(TreeNode**tree,ElementType ele)//在合适位置处插入节点 继续保持有序
    {
        if(*tree==NULL)//创建该节点的空间
        {
           /* tree=(TreeNode*)malloc(sizeof(TreeNode));
            //fun(tree);
            tree->Lchild=NULL;
            tree->Rchild=NULL;
            tree->data=ele;//创建空间进行赋值操作
            printf("[%d,%s]",tree->data.key,tree->data.value);*/
            TreeNode*newnode=(TreeNode*)malloc(sizeof(TreeNode));
            newnode->Lchild=NULL;
            newnode->Rchild=NULL;
            newnode->data=ele;
            *tree=newnode;
        }
    
        else if (ele.key<(*tree)->data.key)
        {
            Insert_node(&(*tree)->Lchild,ele);
        }
        else if(ele.key>(*tree)->data.key)
        {
            Insert_node(&(*tree)->Rchild,ele);
    
        }
    }