在C语言中返回整数数组的前序树遍历函数

Question

我尝试编写一个函数，它返回一个整数数组，其中包含按前序排列的二叉树的节点值，即节点值必须出现在其左右子节点的值之前。

>

如果root为NULL，则返回NULL

对于每个节点，左孩子在右孩子之前

例如

int *a = preorder(bt1);
for (i=0; i<3; i++)
    printf("%d ", a[i]);
>2_1_3_

这是我的工作，但它不起作用，我的代码中哪里有问题？

int* preorder(TreeNode *root) {
    int *a = malloc(sizeof(int)*50);
    int i=0;

    if(root == NULL)
        return NULL;
    else {
        if(root != NULL) {
            a[i] = root->val;
            i++;
            preorder(root->left);
            preorder(root->right);
            return a;
        }
    }
}

Answer 1

使用preorder（）的所需函数签名，解决方案是不可能的。因此，您需要一个用于root==NULL情况的帮助函数和一个遍历函数，该函数指向数组中的当前位置。它还返回一个指向数组中下一个空闲槽的指针。解决方案可能如下所示：

#include <stdio.h>
#include <malloc.h>

struct TreeNode {
    int val;
    struct TreeNode* left, * right;
};

int tree_size(/*struct TreeNode* tree*/) { return 7; }

int* preorder_(struct TreeNode* tn, int* v) {
    *v++ = tn->val;
    if (tn->left) v = preorder_(tn->left, v);
    if (tn->right) v = preorder_(tn->right, v);

    return v;
}

int* preorder(struct TreeNode* tn) {
    if (tn) {
        int* v = malloc(tree_size(/*tn*/) * sizeof(int));
        preorder_(tn, v);
        return v;
    } else {
        return NULL;
    }
}

int main(void) {
    //    4
    //  2   5
    // 1 3 6 7
    struct TreeNode
        left = {2, &{1}, &{3]}, 
        right = {5, &{6}, &{7}}, 
        root = {4, &left, &right};
    int *v, i;

    v = preorder(&root);
    for (i = 0; i < tree_size(/*tn*/); i++) {
        printf("%d ", v[i]); // 4 2 1 3 5 6 7
    }
    free(v);

    return 0;
}

现场演示

Answer 2

在该函数的每次递归调用中，您将分配：

int*a=malloc（sizeof（int）*50）；

您需要为数组分配一次空间，然后使用同一个数组。使用i=0也是一样的。你需要使用一个计数器。

您可能希望在main函数中创建数组，然后将数组作为函数参数传递。或者您可以使用全局数组，并以这种方式访问它。计数器变量也是如此。

注意：我在你们的例子中看不到内存分配的意义。如果您确定树的节点数不会超过数组大小，那么最好使用静态数组。

Answer 3

代码中有两个问题：

1. 您必须为结果分配一次数组。调用预订单之前

一个示例是以下代码：

int *a = malloc(sizeof(int)*50);
int inx = 0;
preorder(bt1, a, &inx);



void preorder(TreeNode *root, int* a, int* inx) {
    if(root == NULL)
        return;
    else {
        if(root != NULL) {
            a[*inx] = root->val;
            *inx = *inx + 1;
            preorder(root->left, a, inx);
            preorder(root->right, a, inx);
        }
    }
}