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

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

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

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

x

本帖最后由壳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[i]);
        }
        printf("\n");
        root = (NODE *) malloc(sizeof(NODE));
        if(root == NULL) {
                printf("can not allocate memory\n");
                exit(-1);
        }
        root->num = data[0];
        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[i]);
        }
        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的意思是左边

最佳答案

月排行榜 / 总排行榜

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[i]);
    }
    printf("\n");
    root = (NODE *) malloc(sizeof(NODE));
    if(root == NULL)
    {
        printf("can not allocate memory\n");
        exit(-1);
    }
    root->num = data[0];
    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[i]);
    }
    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-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 给出，感谢 jhq999 的回答。

单击隐藏图章

本帖最后由 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[i]);
    }
    printf("\n");
    root = (NODE *) malloc(sizeof(NODE));
    if(root == NULL)
    {
        printf("can not allocate memory\n");
        exit(-1);
    }
    root->num = data[0];
    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[i]);
    }
    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
牛逼呀大佬！！

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

账号		自动登录	找回密码
密码			立即注册