设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › 数据结构与算法 › 求大佬看看
返回列表 发新帖
查看: 698|回复: 14

[已解决]求大佬看看

[复制链接]
ZXPoo
发表于 2022-12-23 14:07:51 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<stdio.h>
  3. #include<stdlib.h>

  5. typedef char bitreeElemType;
  6. typedef struct BiNode                                        //定义二叉链表
  7. {
  8.         bitreeElemType data;
  9.         struct BiNode* lchild, * rchild;
  10. }BiNode,*BiTree;

  12. int leaf = 0;

  14. BiTree creat(int n, char qian[], char zhong[]);                //先序中序恢复二叉树
  15. void pre_traverse_Bitree(BiTree T);                        //先序遍历
  16. void in_traverse_Bitree(BiTree T);                        //中序遍历
  17. void post_traverse_Bitree(BiTree T);                //后序遍历
  18. int Gethight_Bitree(BiTree T);                                //求高度
  19. int Getleaf_Bitree(BiTree T);                                //求叶子数

  21. BiTree creat(int n, char qian[], char zhong[])
  22. {
  23.         int i;
  24.         BiTree root;
  25.         if (n == 0)
  26.         {
  27.                 return NULL;
  28.         }
  29.         root = (BiTree)malloc(sizeof(BiNode));
  30.         root->data = qian[0];//根节点一定是先序排列的第一个
  31.         for (i = 0; i < n; i++)
  32.         {
  33.                 if (zhong[i] == qian[0])//找到中序序列中与根节点相等的位置
  34.                 {
  35.                         break;
  36.                 }
  37.         }
  38.         root->lchild = creat(i, qian + 1, zhong);//逐步遍历
  39.         root->rchild = creat(n - i - 1, qian + 1 + i, zhong + 1 + i);
  40.         return root;
  41. }

  43. void pre_traverse_Bitree(BiTree T)
  44. {
  45.         if (!T)
  46.                 return;
  47.         printf("%c", T->data);
  48.         pre_traverse_Bitree(T->lchild);
  49.         pre_traverse_Bitree(T->rchild);
  50. }

  52. void in_traverse_Bitree(BiTree T)
  53. {
  54.         if (!T)
  55.                 return;
  56.         in_traverse_Bitree(T->lchild);
  57.         printf("%c", T->data);
  58.         in_traverse_Bitree(T->rchild);
  59. }

  61. void post_traverse_Bitree(BiTree T)
  62. {
  63.         if (!T)
  64.                 return;
  65.         post_traverse_Bitree(T->lchild);
  66.         post_traverse_Bitree(T->rchild);
  67.         printf("%c", T->data);
  68. }

  70. int Gethight_Bitree(BiTree T)
  71. {
  72.         if (!T)
  73.                 return 0;
  74.         return Gethight_Bitree(T->lchild) > Gethight_Bitree(T->rchild) ? Gethight_Bitree(T->lchild) + 1
  75.                                                                                                                                    : Gethight_Bitree(T->rchild) + 1;
  76. }

  78. int Getleaf_Bitree(BiTree T)
  79. {
  80.         if (!T)
  81.                 return 0;
  82.         if (T->lchild == NULL && T->rchild == NULL)
  83.                 return ++leaf;
  84.         Getleaf_Bitree(T->lchild);
  85.         Getleaf_Bitree(T->rchild);
  86. }


  89. int main()
  90. {
  91.         int n;
  92.         printf("请输入节点数\n");
  93.         scanf("%d", &n);
  94.         char qian[100], zhong[100];
  95.         printf("请输入先序\n");
  96.         for(int i=0;i<n;i++)
  97.         {
  98.                 scanf("%c",&qian[i]);
  99.         }
  100.         printf("请输入中序\n");
  101.                 for(int i=0;i<n;i++)
  102.         {
  103.                 scanf("%c",&zhong[i]);
  104.         }
  105.         BiTree T;
  106.         T = creat(n,qian,zhong);
  107.         printf("先序遍历为： \n");
  108.         pre_traverse_Bitree(T);
  109.         printf("该树高度为： %d\n", Gethight_Bitree(T));
  110.         printf("该树有%d个叶子\n", Getleaf_Bitree(T));

  112.         return 0;
  113. }
复制代码



先序中序恢复出来的二叉树怎么写才能成为其他函数的参数啊？我的运行结果到把中序敲上去就直接完了。问老师老师一点有用的都不说。求回复
最佳答案
月排行榜 / 总排行榜
人造人
2022-12-23 16:04:36
程序是调试出来的，要调试程序的说

  1. #include <stdio.h>
  2. #include <stdlib.h>

  4. typedef char bitreeElemType;
  5. typedef struct BiNode //定义二叉链表
  6. {
  7.     bitreeElemType data;
  8.     struct BiNode *lchild, *rchild;
  9. } BiNode, *BiTree;

  11. //int leaf = 0;

  13. BiTree creat(int n, char qian[], char zhong[]); //先序中序恢复二叉树
  14. void pre_traverse_Bitree(BiTree T);             //先序遍历
  15. void in_traverse_Bitree(BiTree T);              //中序遍历
  16. void post_traverse_Bitree(BiTree T);            //后序遍历
  17. int Gethight_Bitree(BiTree T);                  //求高度
  18. int Getleaf_Bitree(BiTree T);                   //求叶子数

  20. BiTree creat(int n, char qian[], char zhong[]) {
  21.     int i;
  22.     BiTree root;
  23.     if(n == 0) {
  24.         return NULL;
  25.     }
  26.     root = (BiTree)malloc(sizeof(BiNode));
  27.     root->data = qian[0]; //根节点一定是先序排列的第一个
  28.     for(i = 0; i < n; i++) {
  29.         if(zhong[i] == qian[0]) //找到中序序列中与根节点相等的位置
  30.         {
  31.             break;
  32.         }
  33.     }
  34.     root->lchild = creat(i, qian + 1, zhong); //逐步遍历
  35.     root->rchild = creat(n - i - 1, qian + 1 + i, zhong + 1 + i);
  36.     return root;
  37. }

  39. void pre_traverse_Bitree(BiTree T) {
  40.     if(!T)
  41.         return;
  42.     printf("%c", T->data);
  43.     pre_traverse_Bitree(T->lchild);
  44.     pre_traverse_Bitree(T->rchild);
  45. }

  47. void in_traverse_Bitree(BiTree T) {
  48.     if(!T)
  49.         return;
  50.     in_traverse_Bitree(T->lchild);
  51.     printf("%c", T->data);
  52.     in_traverse_Bitree(T->rchild);
  53. }

  55. void post_traverse_Bitree(BiTree T) {
  56.     if(!T)
  57.         return;
  58.     post_traverse_Bitree(T->lchild);
  59.     post_traverse_Bitree(T->rchild);
  60.     printf("%c", T->data);
  61. }

  63. int Gethight_Bitree(BiTree T) {
  64.     if(!T) return 0;
  65.     /*
  66.     return Gethight_Bitree(T->lchild) > Gethight_Bitree(T->rchild)
  67.                ? Gethight_Bitree(T->lchild) + 1
  68.                : Gethight_Bitree(T->rchild) + 1;
  69.    */
  70.     return (Gethight_Bitree(T->lchild) > Gethight_Bitree(T->rchild)
  71.            ? Gethight_Bitree(T->lchild)
  72.            : Gethight_Bitree(T->rchild)) + 1;
  73. }

  75. /*
  76. int Getleaf_Bitree(BiTree T) {
  77.     if(!T)
  78.         return 0;
  79.     if(T->lchild == NULL && T->rchild == NULL)
  80.         return ++leaf;
  81.     Getleaf_Bitree(T->lchild);
  82.     Getleaf_Bitree(T->rchild);

  84.     // return ???
  85. }
  86. */

  88. int Getleaf_Bitree(BiTree T) {
  89.     if(!T) return 0;
  90.     if(T->lchild == NULL && T->rchild == NULL) return 1;
  91.     return Getleaf_Bitree(T->lchild) + Getleaf_Bitree(T->rchild);
  92. }

  94. // 求你们了，释放一下内存吧
  95. // 知道windows为什么连一个月也运行不了吗？
  96. // 就是因为你们写程序，不释放内存
  97. void tree_free(BiTree T) {
  98.     if(!T) return;
  99.     tree_free(T->lchild);
  100.     tree_free(T->rchild);
  101.     free(T);
  102. }

  104. int main() {
  105.     int n;
  106.     printf("请输入节点数\n");
  107.     scanf("%d", &n);
  108.     char qian[100], zhong[100];
  109.     printf("请输入先序\n");




  114.     // *************************
  115.     getchar();  // '\n'
  116.     // *************************



  120.     for(int i = 0; i < n; i++) {
  121.         scanf("%c", &qian[i]);
  122.     }
  123.     printf("请输入中序\n");




  128.     // *************************
  129.     getchar();  // '\n'
  130.     // *************************



  134.     for(int i = 0; i < n; i++) {
  135.         scanf("%c", &zhong[i]);
  136.     }
  137.     BiTree T;
  138.     T = creat(n, qian, zhong);
  139.     printf("先序遍历为： \n");
  140.     pre_traverse_Bitree(T);
  141.     printf("该树高度为： %d\n", Gethight_Bitree(T));
  142.     printf("该树有%d个叶子\n", Getleaf_Bitree(T));

  144.     tree_free(T);

  146.     return 0;
  147. }
复制代码
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

人造人
发表于 2022-12-23 14:16:26 | 显示全部楼层
先序中序  恢复出来 的二叉树怎么写才能成为其他函数的参数啊？

恢复出来？什么意思？
恢复出来的二叉树？
怎么个恢复出来？

看不懂你的问题，重新组织一下语言，把你的问题说清楚
你的老师不理你，大概是因为他看不懂你在说什么吧
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

ZXPoo
 楼主| 发表于 2022-12-23 14:23:06 | 显示全部楼层
人造人 发表于 2022-12-23 14:16
先序中序  恢复出来 的二叉树怎么写才能成为其他函数的参数啊？

恢复出来？什么意思？

题目是让用先序和中序先把二叉树恢复出来，再进行遍历求叶子和高度这些操作。
我问的意思就是用先序和中序恢复出来的二叉树怎么进行遍历那些操作。
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

人造人
发表于 2022-12-23 14:39:34 | 显示全部楼层
ZXPoo 发表于 2022-12-23 14:23
题目是让用先序和中序先把二叉树恢复出来，再进行遍历求叶子和高度这些操作。
我问的意思就是用先序和中 ...

第108行不就是在遍历么？
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

ZXPoo
 楼主| 发表于 2022-12-23 14:41:05 | 显示全部楼层
人造人 发表于 2022-12-23 14:39
第108行不就是在遍历么？

但是运行窗口运行到把中序输入进去就结束了。
不知道是哪没写对。
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

人造人
发表于 2022-12-23 16:04:36 | 显示全部楼层    本楼为最佳答案   
程序是调试出来的，要调试程序的说

  1. #include <stdio.h>
  2. #include <stdlib.h>

  4. typedef char bitreeElemType;
  5. typedef struct BiNode //定义二叉链表
  6. {
  7.     bitreeElemType data;
  8.     struct BiNode *lchild, *rchild;
  9. } BiNode, *BiTree;

  11. //int leaf = 0;

  13. BiTree creat(int n, char qian[], char zhong[]); //先序中序恢复二叉树
  14. void pre_traverse_Bitree(BiTree T);             //先序遍历
  15. void in_traverse_Bitree(BiTree T);              //中序遍历
  16. void post_traverse_Bitree(BiTree T);            //后序遍历
  17. int Gethight_Bitree(BiTree T);                  //求高度
  18. int Getleaf_Bitree(BiTree T);                   //求叶子数

  20. BiTree creat(int n, char qian[], char zhong[]) {
  21.     int i;
  22.     BiTree root;
  23.     if(n == 0) {
  24.         return NULL;
  25.     }
  26.     root = (BiTree)malloc(sizeof(BiNode));
  27.     root->data = qian[0]; //根节点一定是先序排列的第一个
  28.     for(i = 0; i < n; i++) {
  29.         if(zhong[i] == qian[0]) //找到中序序列中与根节点相等的位置
  30.         {
  31.             break;
  32.         }
  33.     }
  34.     root->lchild = creat(i, qian + 1, zhong); //逐步遍历
  35.     root->rchild = creat(n - i - 1, qian + 1 + i, zhong + 1 + i);
  36.     return root;
  37. }

  39. void pre_traverse_Bitree(BiTree T) {
  40.     if(!T)
  41.         return;
  42.     printf("%c", T->data);
  43.     pre_traverse_Bitree(T->lchild);
  44.     pre_traverse_Bitree(T->rchild);
  45. }

  47. void in_traverse_Bitree(BiTree T) {
  48.     if(!T)
  49.         return;
  50.     in_traverse_Bitree(T->lchild);
  51.     printf("%c", T->data);
  52.     in_traverse_Bitree(T->rchild);
  53. }

  55. void post_traverse_Bitree(BiTree T) {
  56.     if(!T)
  57.         return;
  58.     post_traverse_Bitree(T->lchild);
  59.     post_traverse_Bitree(T->rchild);
  60.     printf("%c", T->data);
  61. }

  63. int Gethight_Bitree(BiTree T) {
  64.     if(!T) return 0;
  65.     /*
  66.     return Gethight_Bitree(T->lchild) > Gethight_Bitree(T->rchild)
  67.                ? Gethight_Bitree(T->lchild) + 1
  68.                : Gethight_Bitree(T->rchild) + 1;
  69.    */
  70.     return (Gethight_Bitree(T->lchild) > Gethight_Bitree(T->rchild)
  71.            ? Gethight_Bitree(T->lchild)
  72.            : Gethight_Bitree(T->rchild)) + 1;
  73. }

  75. /*
  76. int Getleaf_Bitree(BiTree T) {
  77.     if(!T)
  78.         return 0;
  79.     if(T->lchild == NULL && T->rchild == NULL)
  80.         return ++leaf;
  81.     Getleaf_Bitree(T->lchild);
  82.     Getleaf_Bitree(T->rchild);

  84.     // return ???
  85. }
  86. */

  88. int Getleaf_Bitree(BiTree T) {
  89.     if(!T) return 0;
  90.     if(T->lchild == NULL && T->rchild == NULL) return 1;
  91.     return Getleaf_Bitree(T->lchild) + Getleaf_Bitree(T->rchild);
  92. }

  94. // 求你们了，释放一下内存吧
  95. // 知道windows为什么连一个月也运行不了吗？
  96. // 就是因为你们写程序，不释放内存
  97. void tree_free(BiTree T) {
  98.     if(!T) return;
  99.     tree_free(T->lchild);
  100.     tree_free(T->rchild);
  101.     free(T);
  102. }

  104. int main() {
  105.     int n;
  106.     printf("请输入节点数\n");
  107.     scanf("%d", &n);
  108.     char qian[100], zhong[100];
  109.     printf("请输入先序\n");




  114.     // *************************
  115.     getchar();  // '\n'
  116.     // *************************



  120.     for(int i = 0; i < n; i++) {
  121.         scanf("%c", &qian[i]);
  122.     }
  123.     printf("请输入中序\n");




  128.     // *************************
  129.     getchar();  // '\n'
  130.     // *************************



  134.     for(int i = 0; i < n; i++) {
  135.         scanf("%c", &zhong[i]);
  136.     }
  137.     BiTree T;
  138.     T = creat(n, qian, zhong);
  139.     printf("先序遍历为： \n");
  140.     pre_traverse_Bitree(T);
  141.     printf("该树高度为： %d\n", Gethight_Bitree(T));
  142.     printf("该树有%d个叶子\n", Getleaf_Bitree(T));

  144.     tree_free(T);

  146.     return 0;
  147. }
复制代码
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

人造人
发表于 2022-12-23 16:08:12 | 显示全部楼层
参考
https://www.jianshu.com/p/2943a21d2a99
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

ZXPoo
 楼主| 发表于 2022-12-23 16:28:45 | 显示全部楼层
人造人 发表于 2022-12-23 16:04
程序是调试出来的，要调试程序的说

所以之前运行失败是内存的原因吗？
那个tree_free函数是释放内存的吗
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

人造人
发表于 2022-12-23 16:32:38 | 显示全部楼层
ZXPoo 发表于 2022-12-23 16:28
所以之前运行失败是内存的原因吗？
那个tree_free函数是释放内存的吗

还有其他问题，你看代码
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

ZXPoo
 楼主| 发表于 2022-12-23 16:37:03 | 显示全部楼层
人造人 发表于 2022-12-23 16:32
还有其他问题，你看代码

求叶子和高度写错了
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

人造人
发表于 2022-12-23 16:38:37 | 显示全部楼层
ZXPoo 发表于 2022-12-23 16:37
求叶子和高度写错了

什么？
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

人造人
发表于 2022-12-23 16:40:39 | 显示全部楼层
ZXPoo 发表于 2022-12-23 16:37
求叶子和高度写错了

你指的是，你发现了你写的代码中，这两个地方的错误
还是说，我给你改的代码中，这两个地方改错了

说话说清楚
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

ZXPoo
 楼主| 发表于 2022-12-23 16:40:42 | 显示全部楼层
人造人 发表于 2022-12-23 16:38
什么？

求叶子和高度的代码我写错了
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

人造人
发表于 2022-12-23 16:40:58 | 显示全部楼层
ZXPoo 发表于 2022-12-23 16:40
求叶子和高度的代码我写错了

嗯
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

ZXPoo
 楼主| 发表于 2022-12-23 16:43:05 | 显示全部楼层
人造人 发表于 2022-12-23 16:40
嗯

感谢
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-4-23 23:41

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表