returns C中整数数组的预序树遍历函数

Question

我尝试编写一个函数，其中 return 一个包含二叉树节点值的整数数组，它是一个节点值，必须出现在其左右子节点的值之前。

如果 root 为 NULL，return NULL
for every node left child comes before right child

例如；

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
您必须将 i 保留在 preorder 之外，以允许它在调用之间更改

一个例子是下面的代码：

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);
        }
    }
}

Answer 2

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

int *a = malloc(sizeof(int)*50);

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

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

注意：我在您的示例中没有看到内存分配点。如果您确定树不会超过 ARRAY SIZE 个节点，则最好使用静态数组。

Answer 3

使用 preorder() 的所需函数签名无法解决。因此，您需要一个用于 root == NULL 情况的辅助函数和一个指向数组中当前位置的指针的遍历函数。它还 returns 指向数组中下一个空闲槽的指针。解决方案可能如下所示：

#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;
}

Live Demo

returns C中整数数组的预序树遍历函数

Preorder tree traversal function which returns an array of integers in C

c

binary-tree