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

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › C\C++交流 › 关于递归函数二叉树的问题求大佬进来看看
返回列表 发新帖
查看: 1776|回复: 6

[已解决]关于递归函数二叉树的问题求大佬进来看看

[复制链接]
壳970527
发表于 2022-12-13 13:54:59 | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 壳970527 于 2022-12-13 14:06 编辑
  1. #include <stdio.h>
  2. #include <stdlib.h>


  5. typedef struct _nd{
  6.         int num;
  7.         struct _nd *left;
  8.         struct  _nd *right;
  9. } NODE;

  11. void mbtree(NODE *p1, int num);

  13. int main(void)
  14. {
  15.         int data[] = {3, 6, 9, 1, 10, 7};
  16.         int i;
  17.         NODE *root, *top;
  18.         int dsize;

  20.         dsize = sizeof(data)/sizeof(int);

  22.         for (i = 0; i < dsize; i++) {
  23.                 printf("%d ", data[i]);
  24.         }
  25.         printf("\n");
  26.         root = (NODE *) malloc(sizeof(NODE));
  27.         if(root == NULL) {
  28.                 printf("can not allocate memory\n");
  29.                 exit(-1);
  30.         }
  31.         root->num = data[0];
  32.         root->left = NULL;
  33.         root->right = NULL;
  34.         top = root;
  35.         printf("root: %d\n", root->num);
  36.         for(i = 1; i < dsize; i++) {
  37.                 printf("i= %d :", i);
  38.                 mbtree(top, data[i]);
  39.         }
  40.         return 0;
  41. }

  43. /* 未完成プログラム */
  44. void mbtree(NODE *p1, int num)
  45. {
  46.         NODE *p2;
  47.         p2 = (NODE *)malloc(sizeof(NODE));
  48.         if(p2 == NULL) {
  49.                 printf("can not allocate memory for mbree\n");
  50.                 exit(-1);
  51.         }
  52.         p2->num = /*ここを完成させよ */;
  53.         p2->left = NULL;
  54.         p2->right = /*ここを完成させよ */;

  56.         /* 値の大小によって左右に振り分ける */
  57.         if (p1->num < num) {    /* 主ノードより大きいとき */
  58.         /* 右がNULLならそこに新たなノードをぶら下げる */
  59.                 if (p1->right == NULL) {
  60.                         p1->right = /*ここを完成させよ */;
  61.                         printf(/*ここを完成させよ */);
  62.                 }
  63.                 else /* NULLでなければ右側のノードに移動 */
  64.                         mbtree(/*ここを完成させよ */);
  65.         } else {
  66.         /* 左がNULLならそこに新たなノードをぶら下げる */
  67.                 /*ここを完成させよ */
  68.         }
  69. }
复制代码

3 6 9 1 10 7
root: 3
i= 1 :(p)3 (r)6
i= 2 :(p)6 (r)9
i= 3 :(p)3 (l)1
i= 4 :(p)9 (r)10
i= 5 :(p)9 (l)7
这是这道题最后输出的内容，我搞不懂p2 = (NODE *)malloc(sizeof(NODE))这个究竟是什么意思，还有就是应该如何把这个函数填完
r的意思是右边，l的意思是左边
最佳答案
月排行榜 / 总排行榜
jhq999
2022-12-13 18:12:12
本帖最后由 jhq999 于 2022-12-13 18:14 编辑
  1. #include <stdio.h>
  2. #include <stdlib.h>


  5. typedef struct _nd
  6. {
  7.     int num;
  8.     struct _nd *left;
  9.     struct  _nd *right;
  10. } NODE;

  12. void mbtree(NODE *p1, int num);

  14. int main(void)
  15. {
  16.     int data[] = {3, 6, 9, 1, 10, 7};
  17.     int i;
  18.     NODE *root, *top;
  19.     int dsize;

  21.     dsize = sizeof(data)/sizeof(int);

  23.     for (i = 0; i < dsize; i++)
  24.     {
  25.         printf("%d ", data[i]);
  26.     }
  27.     printf("\n");
  28.     root = (NODE *) malloc(sizeof(NODE));
  29.     if(root == NULL)
  30.     {
  31.         printf("can not allocate memory\n");
  32.         exit(-1);
  33.     }
  34.     root->num = data[0];
  35.     root->left = NULL;
  36.     root->right = NULL;
  37.     top = root;
  38.     printf("root: %d\n", root->num);
  39.     for(i = 1; i < dsize; i++)
  40.     {
  41.         printf("i= %d :", i);
  42.         mbtree(top, data[i]);
  43.     }
  44.     return 0;
  45. }

  47. /* 未完成プログラム */
  48. void mbtree(NODE *p1, int num)
  49. {


  52.     /* 値の大小によって左右に振り分ける */
  53.     if (p1->num < num)      /* 主ノードより大きいとき */
  54.     {
  55.         /* 右がNULLならそこに新たなノードをぶら下げる */
  56.         if (p1->right == NULL)
  57.         {
  58.             NODE *p2;
  59.             p2 = (NODE *)malloc(sizeof(NODE));
  60.             if(p2 == NULL)
  61.             {
  62.                 printf("can not allocate memory for mbree\n");
  63.                 exit(-1);
  64.             }
  65.             p2->num = num;
  66.             p2->left = NULL;
  67.             p2->right = NULL;
  68.             p1->right = p2;
  69.              printf("%d's right is %d\n",p1->num,num);
  70.         }
  71.         else /* NULLでなければ右側のノードに移動 */
  72.             mbtree(p1->right,num);
  73.     }
  74.     else
  75.     {
  76.         if (p1->left == NULL)
  77.         {
  78.             NODE *p2;
  79.             p2 = (NODE *)malloc(sizeof(NODE));
  80.             if(p2 == NULL)
  81.             {
  82.                 printf("can not allocate memory for mbree\n");
  83.                 exit(-1);
  84.             }
  85.             p2->num = num;
  86.             p2->left = NULL;
  87.             p2->right = NULL;
  88.             p1->left = p2;
  89.             printf("%d's left is %d\n",p1->num,num);
  90.         }
  91.         else /* NULLでなければ右側のノードに移動 */
  92.             mbtree(p1->left,num);
  93.     }
  94. }
复制代码
  1. 3 6 9 1 10 7
  2. root: 3
  3. i= 1 :3's right is 6
  4. i= 2 :6's right is 9
  5. i= 3 :3's left is 1
  6. i= 4 :9's right is 10
  7. i= 5 :9's left is 7

  9. Process returned 0 (0x0)   execution time : 0.290 s
  10. Press any key to continue.
复制代码
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

壳970527
 楼主| 发表于 2022-12-13 15:07:48 | 显示全部楼层
  1. void mbtree(NODE *p1, int num)
  2. {
  3.         NODE *p2;
  4.         p2 = (NODE *)malloc(sizeof(NODE));
  5.         if(p2 == NULL) {
  6.                 printf("can not allocate memory for mbree\n");
  7.                 exit(-1);
  8.         }
  9.         p2->num = num;
  10.         p2->left = NULL;
  11.         p2->right = NULL;
  12.         if (p1->num < num) {
  13.                 if (p1->right == NULL) {
  14.                         p1->right = num;
  15.                         printf("(p)%d (r)%d\n",p1->num,num);
  16.                 }
  17.                 else
  18.                         mbtree(p1->right,num);
  19.         }
  20.         else {
  21.                 if (p1->right == NULL) {
  22.                         p1->left = num;
  23.                         printf("(p)%d (l)%d\n",p1->num,num);
  24.                 }
  25.                 else
  26.                         mbtree(p1->left,num);
  27.         }
  28. }
复制代码

这是我写出来的这个函数，但是不知道为什么只能算到
3 6 9 1 10 7
root: 3
i= 1 :(p)3 (r)6
然后就出错了，请大佬帮忙看看哪里出问题了
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

壳970527
 楼主| 发表于 2022-12-13 15:11:59 | 显示全部楼层
这道题的思路是，先从3开始查找下一个数，
3之后是6，6比3大，那么放在3的右边，然后下一个数字是9，9比3大，但是3的右边有数了，需要到6这一层，就递归，然后6这一层比6大，放到6的右边，
再到1，1比3小，3的左边没有，放在3的左边，
再到10，10比3大，可是3的右边有6，到6这一层，比6大，6的右边有9，所以再到9的这一层，比9大，9的右边是null放9的右边，是这样的思路
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

jhq999
发表于 2022-12-13 17:54:57 | 显示全部楼层
壳970527 发表于 2022-12-13 15:11
这道题的思路是，先从3开始查找下一个数，
3之后是6，6比3大，那么放在3的右边，然后下一个数字是9，9比3 ...
  1. p1->right = num;////编译能通过吗？
复制代码
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

jhq999
发表于 2022-12-13 18:12:12 | 显示全部楼层    本楼为最佳答案   
本帖最后由 jhq999 于 2022-12-13 18:14 编辑
  1. #include <stdio.h>
  2. #include <stdlib.h>


  5. typedef struct _nd
  6. {
  7.     int num;
  8.     struct _nd *left;
  9.     struct  _nd *right;
  10. } NODE;

  12. void mbtree(NODE *p1, int num);

  14. int main(void)
  15. {
  16.     int data[] = {3, 6, 9, 1, 10, 7};
  17.     int i;
  18.     NODE *root, *top;
  19.     int dsize;

  21.     dsize = sizeof(data)/sizeof(int);

  23.     for (i = 0; i < dsize; i++)
  24.     {
  25.         printf("%d ", data[i]);
  26.     }
  27.     printf("\n");
  28.     root = (NODE *) malloc(sizeof(NODE));
  29.     if(root == NULL)
  30.     {
  31.         printf("can not allocate memory\n");
  32.         exit(-1);
  33.     }
  34.     root->num = data[0];
  35.     root->left = NULL;
  36.     root->right = NULL;
  37.     top = root;
  38.     printf("root: %d\n", root->num);
  39.     for(i = 1; i < dsize; i++)
  40.     {
  41.         printf("i= %d :", i);
  42.         mbtree(top, data[i]);
  43.     }
  44.     return 0;
  45. }

  47. /* 未完成プログラム */
  48. void mbtree(NODE *p1, int num)
  49. {


  52.     /* 値の大小によって左右に振り分ける */
  53.     if (p1->num < num)      /* 主ノードより大きいとき */
  54.     {
  55.         /* 右がNULLならそこに新たなノードをぶら下げる */
  56.         if (p1->right == NULL)
  57.         {
  58.             NODE *p2;
  59.             p2 = (NODE *)malloc(sizeof(NODE));
  60.             if(p2 == NULL)
  61.             {
  62.                 printf("can not allocate memory for mbree\n");
  63.                 exit(-1);
  64.             }
  65.             p2->num = num;
  66.             p2->left = NULL;
  67.             p2->right = NULL;
  68.             p1->right = p2;
  69.              printf("%d's right is %d\n",p1->num,num);
  70.         }
  71.         else /* NULLでなければ右側のノードに移動 */
  72.             mbtree(p1->right,num);
  73.     }
  74.     else
  75.     {
  76.         if (p1->left == NULL)
  77.         {
  78.             NODE *p2;
  79.             p2 = (NODE *)malloc(sizeof(NODE));
  80.             if(p2 == NULL)
  81.             {
  82.                 printf("can not allocate memory for mbree\n");
  83.                 exit(-1);
  84.             }
  85.             p2->num = num;
  86.             p2->left = NULL;
  87.             p2->right = NULL;
  88.             p1->left = p2;
  89.             printf("%d's left is %d\n",p1->num,num);
  90.         }
  91.         else /* NULLでなければ右側のノードに移動 */
  92.             mbtree(p1->left,num);
  93.     }
  94. }
复制代码
  1. 3 6 9 1 10 7
  2. root: 3
  3. i= 1 :3's right is 6
  4. i= 2 :6's right is 9
  5. i= 3 :3's left is 1
  6. i= 4 :9's right is 10
  7. i= 5 :9's left is 7

  9. Process returned 0 (0x0)   execution time : 0.290 s
  10. Press any key to continue.
复制代码
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

壳970527
 楼主| 发表于 2022-12-14 00:17:47 | 显示全部楼层
jhq999 发表于 2022-12-13 18:12

牛逼呀大佬！！
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

jhq999
发表于 2022-12-14 00:41:10 | 显示全部楼层
壳970527 发表于 2022-12-14 00:17
牛逼呀大佬！！

别着急，学完树你就明白了
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

本版积分规则

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

GMT+8, 2024-5-19 13:18

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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