• 数据结构有关树的练习题目

                                     |
                                     |
               /---------------------2:1.58 1-------------------------\
               |                                                      |
               |                                                      |
    /----------4:1.81 0---\                     /---------------------9:1.75 0---\
    |                     |                     |                                |
    |                     |                     |                                |
    8:1.74 0              5:1.68 0              1:1.64 1---\                     6:1.72 1
                                                           |
                                                           |
                                                           7:1.55 1

    先序遍历序列：
    2 1.58 1
    4 1.81 0
    8 1.74 0
    5 1.68 0
    9 1.75 0
    1 1.64 1
    7 1.55 1
    6 1.72 1

    每位同学的身高增加0.1后的二叉树：
                                     |
                                     |
               /---------------------2:1.68 1-------------------------\
               |                                                      |
               |                                                      |
    /----------4:1.91 0---\                     /---------------------9:1.85 0---\
    |                     |                     |                                |
    |                     |                     |                                |
    8:1.84 0              5:1.78 0              1:1.74 1---\                     6:1.82 1
                                                           |
                                                           |
                                                           7:1.65 1


    交换左右子树后的二叉树：
                                                |
                                                |
               /--------------------------------2:1.68 1--------------\
               |                                                      |
               |                                                      |
    /----------9:1.85 0--------------\        

    1. //records.txt
    2. 2  1.58 1
    3. 4  1.81 0
    4. 8  1.74 0
    5. 0
    6. 0
    7. 5  1.68 0
    8. 0
    9. 0
    10. 9  1.75 0
    11. 1  1.64 1
    12. 0
    13. 7  1.55 1
    14. 0
    15. 0
    16. 6  1.72 1
    17. 0
    18. 0

    1. #include 
    2. #include 
    3. #include 
    4. typedef struct {
    5.      int xh;   /*学号*/
    6.      float sg; /*身高*/
    7.      int sex;  /*性别，0为男生，1为女生*/
    8. } datatype;
    9. typedef struct node{
    10.     datatype data;
    11.     struct node *left,*right;
    12. } BiNode,*BiTree;
    13.  
    14.  
    15. //以下函数声明为二叉树显示，不要求掌握
    16. #define NODE_WIDTH 11
    17. #define NODE_HEIGHT 3
    18. BiNode* createTree();
    19. BiNode* createTree2(FILE *fp);
    20. void show_tree(BiTree bt);
    21. void showBuf(char x[][500],int m, int n);
    22. void printInBuf(BiTree bt, char buf[][500], int x, int y);
    23. int getWidth(BiTree bt);
    24. int getHeight(BiTree bt);
    25.  
    26. //以下为二叉树显示，不要求掌握
    27. void show_tree(BiTree bt)
    28. {
    29.     char buf[50][500];
    30.     int m=50,n=500,i,j; //以二维数组的方式存储二叉树，行m，列n，字符串长度10
    31.     for (i=0; i
    32.         for (j=0; j
    33.             buf[i][j]=0;
    34.     m=getHeight(bt)*NODE_HEIGHT;
    35.     n=getWidth(bt)*NODE_WIDTH;
    36.     printInBuf(bt,buf,0,0);
    37.     showBuf(buf,m,n);
    38.     printf("\n");
    39. }
    40.  
    41. void showBuf(char x[][500],int m,int n)
    42. {
    43.     int i,j;
    44.     for (i=0; i
    45.     {
    46.         for (j=0; j
    47.             printf("%c",x[i][j]=='\0'?' ':x[i][j]);
    48.         printf("\n");
    49.     }
    50. }
    51.  
    52. void printInBuf(BiTree bt, char buf[][500], int x, int y)
    53. {
    54.     int pl,pr,rootpos,i;
    55.     char sv[500];
    56.     char tempsg[5],tempsex[5];
    57.     sprintf(sv,"%d:",bt->data.xh);
    58.     sprintf(tempsg,"%.2f",bt->data.sg);
    59.     sprintf(tempsex,"%d",bt->data.sex);
    60.     strcat(sv,tempsg);
    61.     strcat(sv," ");
    62.     strcat(sv,tempsex);
    63.  
    64.     if (bt->left==NULL)
    65.         pl=0;
    66.     else
    67.     {
    68.         pl=NODE_WIDTH;
    69.         if (bt->left->right!=NULL)
    70.             pl+=getWidth(bt->left->right)*NODE_WIDTH;
    71.     }
    72.  
    73.     if (bt->right==NULL)
    74.         pr=0;
    75.     else
    76.     {
    77.         pr=NODE_WIDTH;
    78.         if (bt->right->left!=NULL)
    79.             pr+=getWidth(bt->right->left)*NODE_WIDTH;
    80.     }
    81.  
    82.     rootpos=x;
    83.     if (bt->left!=NULL)
    84.         rootpos+=getWidth(bt->left)*NODE_WIDTH;
    85.  
    86.     for (i=0; i
    87.         buf[y+i][rootpos]='|';
    88.     for (i=rootpos-pl; i<=rootpos+pr; i++)
    89.         buf[y+NODE_HEIGHT-1][i]='-';
    90.     for (i=rootpos; istrlen(sv); i++)
    91.         buf[y+NODE_HEIGHT-1][i]=sv[i-rootpos];
    92.     if (pl>0)
    93.         buf[y+NODE_HEIGHT-1][rootpos-pl]='/';
    94.     if (pr>0)
    95.         buf[y+NODE_HEIGHT-1][rootpos+pr]='\\';
    96.  
    97.     if (bt->left!=NULL)
    98.         printInBuf(bt->left,buf,x,y+NODE_HEIGHT);
    99.     if (bt->right!=NULL)
    100.         printInBuf(bt->right,buf,rootpos+NODE_WIDTH,y+NODE_HEIGHT);
    101. }
    102.  
    103. int getWidth(BiTree bt)
    104. {
    105.     int w=1;
    106.     if (bt==NULL)
    107.         return 0;
    108.     w += getWidth(bt->left);
    109.     w += getWidth(bt->right);
    110.     return w;
    111. }
    112. int getHeight(BiTree bt)
    113. {
    114.     int h=1,l,r;
    115.     if (bt==NULL)
    116.         return 0;
    117.     l = getHeight(bt->left);
    118.     r = getHeight(bt->right);
    119.     h += l>r ? l : r;
    120.     return h;
    121. }
    122.  
    123. BiNode* createTree()
    124. {
    125.     BiNode* T;
    126.     FILE *fp;
    127.     if((fp=fopen("records.txt","r"))==NULL)
    128.     {
    129.         printf("can not open read file !");
    130.         exit(1) ;
    131.     }
    132.     while(!feof(fp))
    133.     {
    134.         T = createTree2(fp);
    135.     }
    136.     fclose(fp);
    137.     return T;
    138. }
    139.  
    140. BiNode* createTree2(FILE *fp)
    141. {
    142.     BiNode* T;
    143.     datatype stu;
    144.     fscanf(fp,"%d",&stu.xh);
    145.     if (stu.xh==0)
    146.         return NULL;
    147.     fscanf(fp,"%f%d",&stu.sg,&stu.sex);
    148.     T=(BiNode*)malloc(sizeof(BiNode)); /*生成二叉树的根结点*/
    149.     T->data=stu;
    150.     T->left=createTree2(fp);  /*递归实现左子树的建立*/
    151.     T->right=createTree2(fp); /*递归实现右子树的建立*/
    152.  
    153.     return  T;
    154. }

    1. #define _CRT_SECURE_NO_WARNINGS
    2. /*
    3. 1．题目要求
    4. 阅读程序文件sy3.c，调用bitree2.c提供的功能函数（以#include " bitree2.c" 方式导入函数库），从数据文件records.txt中读取学生信息，建立学生信息二叉树并打印在屏幕上。调用自定义的函数完成以下操作：
    5. 先序遍历二叉树；
    6. 将二叉树中所有学生的身高增加0.1；
    7. 二叉树中所有结点的左右子树交换；
    8. 统计二叉树中度为1的结点个数；
    9. 统计二叉树中身高达标人数；
    10. 统计二叉树的深度；
    12. 在程序文件sy3.c中需再定义以下6个功能函数：*/
    13. //(1)void preOrder(BiNode * T);    /*前序遍历*/
    14. //(2)void changeHeight(BiNode* T); /*每位同学的身高+0.1*/
    15. //(3)void exchange(BiNode* T);     /*二叉树左右子树交换*/
    16. //(4)int oneChild(BiNode* T);       /*求度为1结点数，并返回*/
    17. //(5)int count(BiNode* T, float sg); /*求身高高于 sg变量的结点数，并返回*/
    18. //(6)int deep(BiNode* T);         /*求二叉树深度*/
    19.  
    20. //2．请根据题目功能要求或程序中的注释完成sy3.c代码
    21.  
    22.  
    23. #include "bitree2.h"
    24. void preOrder(BiNode* T);    /*前序遍历*/
    25. void changeHeight(BiNode* T); /*每位同学的身高+0.1*/
    26. void exchange(BiNode* T);     /*二叉树左右子树交换*/
    27. int oneChild(BiNode* T);        /*求度为1结点数，并返回*/
    28. int count(BiNode* T, float sg); /*求身高高于 sg变量的结点数，并返回*/
    29. int deep(BiNode* T);         /*求二叉树深度*/
    30.  
    31. int main()
    32. {
    33.     BiNode* root, * tmp;
    34.     root = createTree();  /*利用二叉树前序遍历的结果建成一棵二叉树*/
    35.     show_tree(root);    /*二叉树的显示，不要求掌握*/
    36.     printf("先序遍历序列：\n");
    37.     preOrder(root);
    38.  
    39.     printf("\n每位同学的身高增加0.1后的二叉树：\n");
    40.     changeHeight(root);
    41.     show_tree(root);/*二叉树的显示，不要求掌握*/
    42.     printf("\n交换左右子树后的二叉树：\n");
    43.     exchange(root); /*交换二叉树的左右子树*/
    44.     show_tree(root);/*二叉树的显示，不要求掌握*/
    45.     printf("\n度为1结点数=%d", oneChild(root));
    46.     printf("\n身高高于1.67的结点数=%d", count(root, 1.67));
    47.     printf("\n树的深度=%d", deep(root));
    48.  
    49.     return 0;
    50. }
    51. /*前序遍历*/
    52. void preOrder(BiNode* T)
    53. {
    54.     if (T)
    55.     {
    56.         printf("%d %.2f %d\n", T->data.xh, T->data.sg, T->data.sex); /*打印结点*/
    57.         preOrder(T->left);
    58.         preOrder(T->right);
    59.     }
    60. }
    61.  
    62. /*每位同学的身高增加0.1*/
    63. void changeHeight(BiNode* T)
    64. {
    65.     if (T)
    66.     {
    67.         T->data.sg += 0.1;
    68.         changeHeight(T->left);
    69.         changeHeight(T->right);
    70.     }
    71.  
    72. }
    73. /*二叉树左右子树交换*/
    74. void exchange(BiNode* T)
    75. {
    76.     BiNode* tmp;
    77.     if (T)
    78.     {
    79.         BiTree tmp = T->left;
    80.         T->left = T->right;
    81.         T->right = tmp;
    82.         exchange(T->left);
    83.         exchange(T->right);
    84.     }
    85. }
    86.  
    87. /*求度为1结点数*/
    88. int oneChild(BiNode* T)
    89. {
    90.  
    91.     if (!T)
    92.     {
    93.         return 0;
    94.     }
    95.         
    96.     else if ((T->left == NULL && T->right != NULL) || (T->left != NULL && T->right == NULL))
    97.     {
    98.         return oneChild(T->left) + oneChild(T->right) + 1;
    99.     }
    100.         
    101.     else
    102.     {
    103.         return oneChild(T->left) + oneChild(T->right);
    104.     }
    105.         
    106. }
    107.  
    108. /*求身高高于 sg变量的结点数，并返回*/
    109. int count(BiNode* T, float sg)
    110. {
    111.  
    112.     if (!T)
    113.     {
    114.         return 0;
    115.     }
    116.     else
    117.     {
    118.         if (T->data.sg > sg)
    119.         {
    120.             return count(T->left, sg) + count(T->right, sg) + 1;
    121.         }            
    122.         else
    123.         {
    124.             return count(T->left, sg) + count(T->right, sg);
    125.         }            
    126.     }
    127. }
    128.  
    129. /*求二叉树深度*/
    130. int deep(BiNode* T)
    131. {
    132.     if (!T)
    133.     {
    134.         return 0;
    135.     }
    136.     else
    137.     {
    138.         int left = deep(T->left);
    139.         int right = deep(T->right);
    140.         return (left >= right ? left : right) + 1;
    141.  
    142.     }   
    143.  
    144. }

  • 相关阅读:
    [附源码]Python计算机毕业设计Django家庭医生签约服务管理系统
    python一行命令搭建web服务，实现内网共享文件
    Docker项目部署
    【开题报告】基于微信小程序的高校党支部党务管理的系统设计与实现
    算法设计与分析100例子（C语言版）
    基于分水岭分割算法的CT图像智能诊断研究-含Matlab代码
    英特尔 Linux Vulkan 驱动程序的首席开发人员离职；JDK 18 功能集被冻结，进入 Rampdown 第一阶段；Ubuntu 禁用 os-prober | 开源日报
    Mac文件搜索工具HoudahSpot 6.4.1中文版
    银行人总结5个影响系统性能的因素，怕是很多人都会忽略
    海丝一号-中国-2020
  • 原文地址：https://blog.csdn.net/laocooon/article/details/127780706