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

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

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

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

/* 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 p1NODE p2init_node函数用来创建树,将p1赋给左指针,p2 指向右指针。 p1 应该包含一个整数,然后 p2 应该包含 num_array 中下一个索引处包含的整数。最终发生的事情是,当我们执行 create_tree(num_array, 2*i + 1, size) 时,它递归,并且随着递归 i 取值 013,然后 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 == 2i == 3 连续 我如何修复我的代码以使其执行此操作?

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

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

感谢大家的帮助!

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

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->leftt-right 无条件地 设置为参数 p1p2,这可能是 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;
}