如何让两个连续的递归函数交替执行每一层递归？

Question

以下是我正在学习的编程课程的作业：

下面是我目前编写的代码。我已经调整它以包含数组中的整数，而不需要从另一个文件中读取它们，以便您轻松使用。下面我将解释为什么它没有成功创建二叉树，然后是我的问题。这是代码：

/* A program that should use integers in an array to make binary trees
   using the integers, then prints the integers from the tree inorder.
   By John
*/

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

typedef struct NODE
{
    int data;
    struct NODE *left;
    struct NODE *right;
} NODE;

typedef NODE *BTREE;

//allocate memory for the node
BTREE create_node(BTREE t)
{
    t = (BTREE)malloc(sizeof(NODE));
    return t;
}
  
//initialize the node
BTREE init_node(int number, BTREE p1, BTREE p2)
{
    BTREE t = NULL;
    t = create_node(t);
    t->data = number;
    if (p1->data <= t->data)
    {
        t->left = p1;
    }
    else if (p1->data > t->data)
    {
        t->right = p1;
    }
    if (p2->data <= t->data)
    {
        t->left = p2;
    }
    else if (p2->data > t->data)
    {
        t->right = p2;
    }
    return t;
}

//create the tree from the integers stored in the array
BTREE create_tree(int num_array[], int i, int size)
{
    if (i >= size)
    {
        return NULL;
    }
    else
    {
        return (init_node(num_array[i],
                          create_tree(num_array, 2*i + 1, size),
                          create_tree(num_array, 2*i + 2, size)));
    }
}

//printing the integers stored in the trees inorder
void print_inorder(BTREE t)
{
    if (t != NULL)
    {
        print_inorder(t->left);
        printf("%d  :", t->data);
        print_inorder(t->right);
    }
}

int main(void)
{
    BTREE t = NULL;
    int data[] = { 9, 11, 4, 5 };   //pointer to integers array
    int i = 0;           //represents indexes of the integers array
    int number = 0;      //number of integers to be read into array
    
    t = create_tree(data, i, number);
    print_inorder(t);
    
    free(t);
        
    return 0;
}

我得到一个分段错误，因为我有一个错误的（悬空？）指针，据我所知（如果我错了请纠正我）。当最终调用 create_tree 函数 returned 的 init_node 时，传递给 init_node 函数的 i 值为 == 3 ，这指的是我的 num_array 中的最后一个整数。因此，在 init_node 函数中，if(p1 -> data <= t -> data) 是一个无效语句，因为 p1 本身不存在，因为它需要一个从 num_array 中获取的 int，但我已经达到了在尝试创建 p1 之前 num_array 结束，因此 p1 是一个坏的/悬挂指针。

我的问题出在 create_tree 函数的 return 值中：

BTREE create_tree(int num_array[], int i, int size)
{
    if (i >= size)
    {
        return NULL;
    }
    else
    {
        return (init_node(num_array[i],
                          create_tree(num_array, 2*i + 1, size),
                          create_tree(num_array, 2*i + 2, size)));
    }
}

这个要点：

     return (init_node(num_array[i],
                       create_tree(num_array, 2*i + 1, size),
                       create_tree(num_array, 2*i + 2, size)));

是创建NODE p1和NODE p2被init_node函数用来创建树，将p1赋给左指针，p2 指向右指针。 p1 应该包含一个整数，然后 p2 应该包含 num_array 中下一个索引处包含的整数。最终发生的事情是，当我们执行 create_tree(num_array, 2*i + 1, size) 时，它递归，并且随着递归 i 取值 0、1、3，然后 i 变为 == 7，因此 NULL 被 returned 到 create_tree 函数，i 值传递给 create_tree(num_array, 2*i + 2, size) 已经是 == 3，所以 create_tree 函数在这种情况下 returns NULL，并且 then init_node函数开始执行。

我在 returned init_node 函数中的 create_tree 递归想要的是使用 num_array 的索引 i == 0 处的整数在 create_tree(num_array, 2*i + 1, size) 中，然后在 create_tree(num_array, 2*i + 2, size) 中使用索引 i == 1 处的整数，并调用 init_node 函数来创建树，然后在第一个之间交替第二个 create_tree 函数调用继续使用 i == 2 和 i == 3 连续。 我如何修复我的代码以使其执行此操作？

(教授课程的教授实际上按照我的方式实现了代码，这意味着他按照我的方式编写了 create_tree 函数，只是他使用了包含字符 a 的字符数组, b, c, d, e 而不是一个包含int的int数组，不知何故他的程序执行正常，而我的没有，这也很混乱。 )

下面是我课程的一个片段，展示了我使用的大致相同的逻辑，教授在他的 init_node 和 create_tree 函数中使用了相同的逻辑。然后他运行编译后的程序，它工作得很好，我不明白他是如何工作的。

感谢大家的帮助！

Answer 1

我发现您的示例代码中存在两个主要缺陷。第一个可能仅在示例中，而不是您的原始版本：

int data[] = { 9, 11, 4, 5 };   //pointer to integers array
int i = 0;           //represents indexes of the integers array
int number = 0;      //number of integers to be read into array

t = create_tree(data, i, number);

number 变量需要设置为数组的大小，因此它的零值将阻止代码做太多事情。但真正的问题是 init_node() 函数。

在您教授的示例中，t->left 和 t-right 被 无条件地 设置为参数 p1 和 p2，这可能是 NULL。但是您的代码会执行一些条件测试，例如 if (p1->data ... 当 p1 可能是 NULL 时。 p2 也是如此。而且，它可能会使 t->left 和/或 t->right 未初始化。让我们重新编写代码，测试指针的有效性：

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

typedef struct NODE
{
    int data;
    struct NODE *left;
    struct NODE *right;
} NODE;

typedef NODE *BTREE;

BTREE create_node(void)
{
    BTREE t = malloc(sizeof(NODE));

    if (t == NULL)
    {
        perror("NODE can't be allocated!");
        exit(EXIT_FAILURE);
    }

    return t;
}

BTREE init_node(int number, BTREE p1, BTREE p2)
{
    BTREE t = create_node();
    t->data = number;
    t->left = NULL;
    t->right = NULL;

    if (p1 != NULL)
    {
        if (p1->data <= t->data)
        {
            t->left = p1;
        }
        else
        {
            t->right = p1;
        }
    }
    
    if (p2 != NULL)
    {
        if (p2->data <= t->data)
        {
            t->left = p2;
        }
        else
        {
            t->right = p2;
        }
    }

    return t;
}

BTREE create_tree(int num_array[], unsigned i, size_t size)
{
    if (i >= size)
    {
        return NULL;
    }

    return init_node(num_array[i], create_tree(num_array, 2*i + 1, size), create_tree(num_array, 2*i + 2, size));
}

void print_inorder(BTREE t)
{
    if (t != NULL)
    {
        printf("(");
        print_inorder(t->left);
        printf(" %d ", t->data);
        print_inorder(t->right);
        printf(")");
    }
}

int main(void)
{
    BTREE t = NULL;
    int data[] = { 9, 11, 4, 5 }; // pointer to integers array
    size_t number = sizeof(data)/sizeof(*data); // number of integers to be read into array

    t = create_tree(data, 0, number);
    print_inorder(t);
    printf("\n");

    return EXIT_SUCCESS;
}

如何让两个连续的递归函数交替执行每一层递归？

How do I make two consecutive recursive functions execute each level of recursion in alternation?

c

recursion

tree

binary-tree