C 中的递归，内部有一个数组和一个索引

Question

我正在尝试做一个接收假定 BST 根的函数，我想知道有问题的树是否是 BST。

问题是，我正在用递归来旅行树，我想做的是，将树的所有值都放在一个数组中。我搜索了如何将BST放入数组(AddtoArray)，但是我在stackoverflow和其他网站上找到的答案并没有解决我的问题。(我有赛格错误)。

这是我到目前为止得到的：

#include<stdio.h>
#include<stdlib.h>
struct node{
int key;
struct node *left, *right;
};
struct node *newNode(int item){
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
struct node* insert(struct node* node, int key){
if(node == NULL) return newNode(key);
if(key < node->key)
node->left  = insert(node->left, key);
else if(key >= node->key)
node->right = insert(node->right, key);
return node;
}
void check(struct node *root, int *array, int i){
if(root != NULL){
check(root->left, array, i);
array[i++] = root->key;
//I tried to put i++, ++i in every place of this function (trying table test) and I realized it was too difficult to realize what to do here, I've found some functions returning an integer, the "i" in question, but they didn't work out for me.
check(root->right, array, i);
}
}
int main(){
int *array;
int array_length = sizeof(array)/sizeof(array[0]);
int i = 0;

array = (int*)malloc(array_length*sizeof(int));
struct node *root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 20);
check(root, array, i);
printf("PRINTING ARRAY TO SEE IF THE BST IS IN ARRAY:n");
for(i = 0; i < array_length; i++){
printf("VALUE: %d ", array[i]);
}
free(array);
return 0;
}

我想在不使用全局变量的情况下解决这个问题。我该怎么做？

Answer 1

我在您的check代码及其用法中看到两个问题(没有分析其他函数)：

首先，您的malloc无法按预期工作，因为无论您的 BST 大小如何，sizeof(array)/sizeof(array[0])都会始终提供相同的(小)值，可能是1或2。

因此，您宁愿引入一个获取节点数的函数，并将其用作数组的长度：

int array_length = getNrOfNodes(root); // function to be coded
int *array = malloc(array_length*sizeof(int));

其次，将按值i的整数值传递给递归函数。由于它是按值传递的，因此任何i++将仅对相应的函数调用实例生效，而不会影响调用堆栈上的其他函数调用实例。因此，树的完整左侧部分(更改i之前的键)很可能会写入array[0].

我建议在调用堆栈上的函数实例之间共享数组索引。这可以通过传递指向某些i的指针来实现，而不是传递i-s 值。我会介绍一个完成这项工作的内部版本，因为该函数的用户不需要知道辅助变量i：

void writeToArray_internal(struct node *root, int *array, int *i){
if(root != NULL){
writeToArray_internal(root->left, array, i);
array[*i] = root->key;
(*i)++;
writeToArray_internal(root->right, array, i);
}
}
void writeToArray(struct node *root, int *array) {
int i=0;
writeToArray_internal(root, array, &i);
}

Answer 2

这里这一行

int array_length = sizeof(array)/sizeof(array[0]);

是错误的。这仅适用于纯数组，因为sizeof返回数量 表达式/变量的字节数。您的变量array是一个指针，因此sizeof array返回指针的大小，在哪里 指针是指针，你总是会得到相同的大小。

除了试图在知道如何之前获取"数组"的元素数量 您拥有的许多节点毫无意义，因为您需要的元素数量array取决于节点的数量，因此 您已经编写了一个函数来返回节点数，然后您可以为array分配空间。

另请注意，您的check函数也不正确。变量i为 每个check调用的本地，因此您将覆盖 数组，因为第n次迭代的i++仅i影响n-迭代，n-1- th迭代看不到该更改，因此 覆盖第n次迭代的值。

您还需要将i作为指针传递：

void check(struct node *root, int *array, size_t *i, size_t maxlen) {
if(root != NULL){
check(root->left, array, i, maxlen);
if(*i < maxlen)  // checking that you don't step out of bounds
array[(*i)++] = root->key;
check(root->right, array, i, maxlen);
}
}

你这样称呼它：

size_t i  = 0;
size_t nodes_number = get_number_of_nodes(root); // you have to write this function
int *array = malloc(nodes_number * sizeof *array);
if(array == NULL)
{
// error handling
// do not continue
}
check(root, array, &i, nodes_number);