【二叉树】二叉树学习小结1

冷不防 2022-06-01 06:24 146阅读 0赞

一、主干功能部分代码分享  
1.存储定义

struct Tree{
      char data;/*数据域*/
      struct Tree *left;/*指针域-指向左子树*/
      struct Tree *right;/*指针域-指向右子树*/
    };

2.按先序遍历输入的字符序列建立二叉树，如abc,de,g,f, (其中,表示空结点)

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    struct Tree{
      char data;/*数据域*/
      struct Tree *left;/*指针域-指向左子树*/
      struct Tree *right;/*指针域-指向右子树*/
    };
    
    int k;
    char st[104];
    
    Tree * build_tree();/*建树*/
    
    int main(){
      while(~scanf("%s", st)){
        k = 0;
        Tree *root;
        root = build_tree();
        printf("%c\n", root->data);
      }
      return 0;
    }
    Tree * build_tree(){
      Tree *rt;
      if(st[k] == ','){
        rt = NULL;
        k++;
      }
      else {
        k++;
        rt = (struct Tree *)malloc(sizeof(struct Tree));
        rt->data = st[k-1];
        rt->left = build_tree();
        rt->right = build_tree();
      }
      return rt;
    }

3.先序遍历

void fir_vis(Tree *rt){
      if(rt){
        printf("%c", rt->data);/*根*/
        fir_vis(rt->left);/*左子树*/
        fir_vis(rt->right);/*右子树*/
      }
    }

4.中序遍历

void mid_vis(Tree *rt){
      if(rt){
        mid_vis(rt->left);/*左子树*/
        printf("%c", rt->data);/*根*/
        mid_vis(rt->right);/*右子树*/
      }
    }

5.后序遍历

void las_vis(Tree *rt){
      if(rt){
        las_vis(rt->left);/*左子树*/
        las_vis(rt->right);/*右子树*/
        printf("%c", rt->data);/*根*/
      }
    }

6.内存释放

void del_tree(Tree *rt){
      if(rt){
        del_tree(rt->left);/*递归左子树*/
        del_tree(rt->right);/*递归右子树*/
        delete rt;/*释放根节点*/
      }
    }

[SDUT-数据结构实验之二叉树二：遍历二叉树][SDUT-]  
以下为Accepted代码

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    struct Tree{
      char data;/*数据域*/
      struct Tree *left;/*指针域-指向左子树*/
      struct Tree *right;/*指针域-指向右子树*/
    };
    
    int k;
    char st[104];
    
    Tree * build_tree();/*建树*/
    void fir_vis(Tree *rt);/*先序遍历*/
    void mid_vis(Tree *rt);/*中序遍历*/
    void las_vis(Tree *rt);/*后序遍历*/
    void del_tree(Tree *rt);/*内存释放*/
    
    int main(){
      while(~scanf("%s", st)){
        k = 0;
        Tree *root;
        root = build_tree();
        /*fir_vis(root);
        printf("\n");*/
        mid_vis(root);
        printf("\n");
        las_vis(root);
        printf("\n");
        del_tree(root);
      }
      return 0;
    }
    Tree * build_tree(){
      Tree *rt;
      if(st[k] == ','){
        rt = NULL;
        k++;
      }
      else {
        k++;
        rt = (struct Tree *)malloc(sizeof(struct Tree));
        rt->data = st[k-1];
        rt->left = build_tree();
        rt->right = build_tree();
      }
      return rt;
    }
    void fir_vis(Tree *rt){
      if(rt){
        printf("%c", rt->data);/*根*/
        fir_vis(rt->left);/*左子树*/
        fir_vis(rt->right);/*右子树*/
      }
    }
    void mid_vis(Tree *rt){
      if(rt){
        mid_vis(rt->left);/*左子树*/
        printf("%c", rt->data);/*根*/
        mid_vis(rt->right);/*右子树*/
      }
    }
    void las_vis(Tree *rt){
      if(rt){
        las_vis(rt->left);/*左子树*/
        las_vis(rt->right);/*右子树*/
        printf("%c", rt->data);/*根*/
      }
    }
    void del_tree(Tree *rt){
      if(rt){
        del_tree(rt->left);/*递归左子树*/
        del_tree(rt->right);/*递归右子树*/
        free(rt);/*释放根节点*/
      }
    }

7.递归寻找叶子节点数量

int get_leaves(Tree *rt){
      if(rt == NULL) return 0;
      if(rt->left == NULL && rt->right == NULL) return 1;
      int num1 = get_leaves(rt->left);/*递归寻找左子树的叶子节点数量*/
      int num2 = get_leaves(rt->right);/*递归寻找右子树的叶子节点数量*/
      return num1+num2;
    }

[SDUT-数据结构实验之二叉树三：统计叶子数][SDUT- 1]  
以下为Accepted代码

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    struct Tree{
      char data;/*数据域*/
      struct Tree *left;/*指针域-指向左子树*/
      struct Tree *right;/*指针域-指向右子树*/
    };
    
    int k;
    char st[104];
    
    Tree * build_tree();
    int get_leaves(Tree *rt);
    void del_tree(Tree *rt);
    
    int main(){
      while(~scanf("%s", st)){
        Tree *root;
        k = 0;
        root = build_tree();
        printf("%d\n", get_leaves(root));
        del_tree(root);
      }
      return 0;
    }
    Tree * build_tree(){
      Tree *rt;
      if(st[k] == ','){
        rt = NULL;
        k++;
      }
      else {
        k++;
        rt = (struct Tree *)malloc(sizeof(struct Tree));
        rt->data = st[k-1];
        rt->left = build_tree();
        rt->right = build_tree();
      }
      return rt;
    }
    int get_leaves(Tree *rt){
      if(rt == NULL) return 0;
      if(rt->left == NULL && rt->right == NULL) return 1;
      int num1 = get_leaves(rt->left);/*递归寻找左子树的叶子节点数量*/
      int num2 = get_leaves(rt->right);/*递归寻找右子树的叶子节点数量*/
      return num1+num2;
    }
    void del_tree(Tree *rt){
      if(rt){
        del_tree(rt->left);
        del_tree(rt->right);
        free(rt);
      }
    }

8.递归寻找二叉树的深度

int get_depth(Tree *rt){
      if(rt == NULL) return 0;
      int d1 = get_depth(rt->left);/*递归左子树深度*/
      int d2 = get_depth(rt->right);/*递归右子树深度*/
      if(d1 > d2) return d1+1;
      else return d2+1;
    }

[SDUT-数据结构实验之二叉树的建立与遍历][SDUT- 2]  
以下为Accepted代码

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    struct Tree{
      char data;/*数据域*/
      struct Tree *left;/*指针域-指向左子树*/
      struct Tree *right;/*指针域-指向右子树*/
    };
    
    int k;
    char st[104];
    
    Tree * build_tree();
    void mid_vis(Tree *rt);
    void las_vis(Tree *rt);
    int get_leaves(Tree *rt);
    int get_depth(Tree *rt);
    void del_tree(Tree *rt);
    
    int main(){
      while(~scanf("%s", st)){
        Tree *root;
        k = 0;
        root = build_tree();
        mid_vis(root);
        printf("\n");
        las_vis(root);
        printf("\n");
        printf("%d\n", get_leaves(root));
        printf("%d\n", get_depth(root));
        del_tree(root);
      }
      return 0;
    }
    Tree * build_tree(){
      Tree *rt;
      if(st[k] == ','){
        rt = NULL;
        k++;
      }
      else {
        k++;
        rt = (struct Tree *)malloc(sizeof(struct Tree));
        rt->data = st[k-1];
        rt->left = build_tree();
        rt->right = build_tree();
      }
      return rt;
    }
    void mid_vis(Tree *rt){
      if(rt){
        mid_vis(rt->left);
        printf("%c", rt->data);
        mid_vis(rt->right);
      }
    }
    void las_vis(Tree *rt){
      if(rt){
        las_vis(rt->left);
        las_vis(rt->right);
        printf("%c", rt->data);
      }
    }
    int get_leaves(Tree *rt){
      if(rt == NULL) return 0;
      if(rt->left == NULL && rt->right == NULL) return 1;
      int num1 = get_leaves(rt->left);/*递归寻找左子树的叶子节点数量*/
      int num2 = get_leaves(rt->right);/*递归寻找右子树的叶子节点数量*/
      return num1+num2;
    }
    int get_depth(Tree *rt){
      if(rt == NULL) return 0;
      int d1 = get_depth(rt->left);/*递归左子树深度*/
      int d2 = get_depth(rt->right);/*递归右子树深度*/
      if(d1 > d2) return d1+1;
      else return d2+1;
    }
    void del_tree(Tree *rt){
      if(rt){
        del_tree(rt->left);
        del_tree(rt->right);
        free(rt);
      }
    }

[SDUT-]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2383/pid/3341
[SDUT- 1]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2383/pid/3342
[SDUT- 2]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2383/pid/2136