关于递归函数二叉树的问题求大佬进来看看,C\C++交流,技术交流,鱼C论坛

壳970527 发表于 2022-12-13 13:54:59

关于递归函数二叉树的问题求大佬进来看看

本帖最后由壳970527 于 2022-12-13 14:06 编辑

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

typedef struct _nd{
   int num;
   struct _nd *left;
   struct_nd *right;
} NODE;

void mbtree(NODE *p1, int num);

int main(void)
{
   int data[] = {3, 6, 9, 1, 10, 7};
   int i;
   NODE *root, *top;
   int dsize;

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

   for (i = 0; i < dsize; i++) {
            printf("%d ", data);
   }
   printf("\n");
   root = (NODE *) malloc(sizeof(NODE));
   if(root == NULL) {
            printf("can not allocate memory\n");
            exit(-1);
   }
   root->num = data;
   root->left = NULL;
   root->right = NULL;
   top = root;
   printf("root: %d\n", root->num);
   for(i = 1; i < dsize; i++) {
            printf("i= %d :", i);
            mbtree(top, data);
   }
   return 0;
}

/* 未完成プログラム */
void mbtree(NODE *p1, int num)
{
   NODE *p2;
   p2 = (NODE *)malloc(sizeof(NODE));
   if(p2 == NULL) {
            printf("can not allocate memory for mbree\n");
            exit(-1);
   }
   p2->num = /*ここを完成させよ */;
   p2->left = NULL;
   p2->right = /*ここを完成させよ */;

   /* 値の大小によって左右に振り分ける */
   if (p1->num < num) { /* 主ノードより大きいとき */
   /* 右がNULLならそこに新たなノードをぶら下げる */
            if (p1->right == NULL) {
                     p1->right = /*ここを完成させよ */;
                     printf(/*ここを完成させよ */);
            }
            else /* NULLでなければ右側のノードに移動 */
                     mbtree(/*ここを完成させよ */);
   } else {
   /* 左がNULLならそこに新たなノードをぶら下げる */
            /*ここを完成させよ */
   }
}

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的意思是左边

壳970527 发表于 2022-12-13 15:07:48

void mbtree(NODE *p1, int num)
{
   NODE *p2;
   p2 = (NODE *)malloc(sizeof(NODE));
   if(p2 == NULL) {
            printf("can not allocate memory for mbree\n");
            exit(-1);
   }
   p2->num = num;
   p2->left = NULL;
   p2->right = NULL;
   if (p1->num < num) {
            if (p1->right == NULL) {
                     p1->right = num;
                     printf("(p)%d (r)%d\n",p1->num,num);
            }
            else
                     mbtree(p1->right,num);
   }
   else {
            if (p1->right == NULL) {
                     p1->left = num;
                     printf("(p)%d (l)%d\n",p1->num,num);
            }
            else
                     mbtree(p1->left,num);
   }
}

这是我写出来的这个函数，但是不知道为什么只能算到
3 6 9 1 10 7
root: 3
i= 1 :(p)3 (r)6
然后就出错了，请大佬帮忙看看哪里出问题了

壳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的右边，是这样的思路

jhq999 发表于 2022-12-13 17:54:57

壳970527 发表于 2022-12-13 15:11
这道题的思路是，先从3开始查找下一个数，
3之后是6，6比3大，那么放在3的右边，然后下一个数字是9，9比3 ...

p1->right = num;////编译能通过吗？

jhq999 发表于 2022-12-13 18:12:12

本帖最后由 jhq999 于 2022-12-13 18:14 编辑

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

typedef struct _nd
{
int num;
struct _nd *left;
struct_nd *right;
} NODE;

void mbtree(NODE *p1, int num);

int main(void)
{
int data[] = {3, 6, 9, 1, 10, 7};
int i;
NODE *root, *top;
int dsize;

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

for (i = 0; i < dsize; i++)
{
   printf("%d ", data);
}
printf("\n");
root = (NODE *) malloc(sizeof(NODE));
if(root == NULL)
{
   printf("can not allocate memory\n");
   exit(-1);
}
root->num = data;
root->left = NULL;
root->right = NULL;
top = root;
printf("root: %d\n", root->num);
for(i = 1; i < dsize; i++)
{
   printf("i= %d :", i);
   mbtree(top, data);
}
return 0;
}

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

/* 値の大小によって左右に振り分ける */
if (p1->num < num)    /* 主ノードより大きいとき */
{
   /* 右がNULLならそこに新たなノードをぶら下げる */
   if (p1->right == NULL)
   {
         NODE *p2;
         p2 = (NODE *)malloc(sizeof(NODE));
         if(p2 == NULL)
         {
            printf("can not allocate memory for mbree\n");
            exit(-1);
         }
         p2->num = num;
         p2->left = NULL;
         p2->right = NULL;
         p1->right = p2;
         printf("%d's right is %d\n",p1->num,num);
   }
   else /* NULLでなければ右側のノードに移動 */
         mbtree(p1->right,num);
}
else
{
   if (p1->left == NULL)
   {
         NODE *p2;
         p2 = (NODE *)malloc(sizeof(NODE));
         if(p2 == NULL)
         {
            printf("can not allocate memory for mbree\n");
            exit(-1);
         }
         p2->num = num;
         p2->left = NULL;
         p2->right = NULL;
         p1->left = p2;
         printf("%d's left is %d\n",p1->num,num);
   }
   else /* NULLでなければ右側のノードに移動 */
         mbtree(p1->left,num);
}
}

3 6 9 1 10 7
root: 3
i= 1 :3's right is 6
i= 2 :6's right is 9
i= 3 :3's left is 1
i= 4 :9's right is 10
i= 5 :9's left is 7

Process returned 0 (0x0) execution time : 0.290 s
Press any key to continue.

壳970527 发表于 2022-12-14 00:17:47

jhq999 发表于 2022-12-13 18:12

牛逼呀大佬！！

jhq999 发表于 2022-12-14 00:41:10

壳970527 发表于 2022-12-14 00:17
牛逼呀大佬！！

别着急，学完树你就明白了

页: [1]

鱼C论坛's Archiver

关于递归函数二叉树的问题求大佬进来看看