C语言数据结构链式二叉树的创建、前序、中序、后序遍历

谁践踏了优雅 2022-01-21 00:59 143阅读 0赞

/\*  
\*链式二叉树的创建  
\*二叉树的初始化  
\*前序 中序 后序遍历  
\*/

#include<stdio.h>
    #include<stdlib.h>
    #define MAXSIZE 1024
    static int id=0;
    typedef struct elementtype//数据结构体创建
    {
        char name[MAXSIZE];
        int id;
    }ElementType;
    typedef struct treenode//节点结构体的创建
    {
        ElementType data;
        struct treenode*left;//左节点
        struct treenode*right;//右节点
    }TreeNode;
    typedef struct binarytree//二叉链的结构体
    {
        TreeNode *root;
         int length;//长度
         int depth;//深度
         int diameter;//从叶节点到叶节点的最长路径
    }BinaryTree;
    void init_binarytree(BinaryTree*tree);//二叉树的初始化
    int  creat_binarytree(TreeNode*root);//二叉树的创建
    void test_binarytree();//测试函数
    void preordertrevers(TreeNode*node);//前序遍历
    void inordertravers(TreeNode*node);//中序遍历
    void postordertravers(TreeNode*node);//后序遍历
    int main()
    {
        test_binarytree();
        return 0;
    }
    void init_binarytree(BinaryTree*tree)//二叉树的初始化
    {
        if(tree==NULL)
            return ;
        else
        {
            tree->depth=0;
            tree->diameter=0;
            tree->length=0;
            tree->root=NULL;
        }
    
    }
    int  creat_binarytree(TreeNode*root)//二叉树的创建
    {
        if(root==NULL)
            return ;
         char inputname[MAXSIZE];
          //printf("请输入姓名:\n");
           gets(inputname);
           if(strcmp(inputname,"\0")==0)
           {//输入回车结束节点的录入  \0为回车符   \n为空格键
               return 0;
    
           }
           strcpy(root->data.name,inputname);
             root->data.id=++id;
             //位左右孩子节点创造空间
             root->left=(TreeNode*)malloc(sizeof(TreeNode));
             root->right=(TreeNode*)malloc(sizeof(TreeNode));
             printf("左孩子节点:\n");
              if( creat_binarytree(root->left)==0)
              {
                  //销毁节点
                  free(root->left);
                  root->left=NULL;
    
              }
              printf("右孩子节点:\n");
              if(creat_binarytree(root->right)==0)
              {
                  //销毁节点
                  free(root->right);
                  root->right=NULL;
                  }
                return 1;
    
    }
    void test_binarytree()//测试函数
    {
        BinaryTree tree;//创建第一个节点
    
           init_binarytree(&tree);
           tree.root=(TreeNode*)malloc(sizeof(TreeNode));
             printf("请输入根节点数据:\n");
           creat_binarytree(tree.root);
             // free(tree.root);
           printf("前序遍历的结果为:\n");
           preordertrevers(tree.root);
           printf("\n");
           printf("中序遍历的结果为;\n");
           inordertravers(tree.root);
            printf("\n");
           printf("后序遍历的结果为;\n");
                    postordertravers(tree.root);
    }
    void preordertrevers(TreeNode*node)//前序遍历
    {
        if(node!=NULL)
        {
            printf("[%d,%s]-",node->data.id,node->data.name);
            preordertrevers(node->left);
            preordertrevers(node->right);
        }
    }
    //带*号才能用->指向 不带*号只能用 .来指向
    void inordertravers(TreeNode*node)//中序遍历的结果
    {
        if(node)
        {    //左->根->右的顺序进行遍历
            inordertravers(node->left);
            printf("[%d,%s]-",node->data.id,node->data.name);
            inordertravers(node->right);
        }
    }
    void postordertravers(TreeNode*node)//后序遍历
    {     //遍历顺序为左->右->根
        if(node)
        {
            inordertravers(node->left);
            inordertravers(node->right);
            printf("[%d,%s]-",node->data.id,node->data.name);
        }
    }