Почему я не могу получить обход порядка двоичного дерева из следующего кода?

Question

Я пытаюсь выполнить обход порядка бинарного дерева поиска и вернуть конечный результат в многомерный массив. например. если root узел равен 2, а узлы на уровне 1 равны 1,4, то он должен вернуть [[2], [1,4]] как returnColumnSizes из кода. Я новичок в структурах данных и не имею команды использовать функцию malloc. Любая помощь будет оценена. Спасибо:)

int height(struct TreeNode *h){
    if (h == NULL) return 0;
    int l = height(h->left);
    int r = height(h->right);
    if (l > r)
        return l+1;
    else
        return r+1;
}

int *ordercalc(struct TreeNode *root, int level){
    if (root == NULL) return NULL;
    int i = 0, arr[100];
    if (level == 1)
        arr[i++] = root->val;
    else if(level > 1){
        ordercalc(root->left, level-1);  //decrease the level one per call to print data when it
        ordercalc(root->right, level-1);  // reaches proper level
    }
    return arr;
}

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    if (*returnSize == 0) return NULL;
    **returnColumnSizes = (int **)malloc(*returnSize * sizeof(int *));
    for (int i=0;i<height(root)+1;i++){
        returnColumnSizes[i] = (int *)malloc(sizeof(int) * 10);
        returnColumnSizes[i] = ordercalc(root, i);
    }
    return returnColumnSizes;
}

Answer 1

height выглядит хорошо.

levelOrder выглядит хорошо, хотя i<height(root)+1; вычисляет высоту root снова и снова в l oop, даже если она не изменяется. Кроме того, malloc(sizeof(int) * 10); не кажется достаточно динамичным c для больших деревьев (мы вернемся к этому позже).

ordercalc необходимо пересмотреть. Для этой функции в кадре стека выделено arr[100];, затем

if (level == 1)
    arr[i++] = root->val;

и

return arr;

Я вижу, что вы пытаетесь заполнить уровни на основе высоты, которая равна правильная идея. Однако:

1. Возвращение выделенного стека массива - неопределенное поведение. Когда вызов возвращается, все данные в его кадре не могут быть доступны. Вам нужно будет malloc в куче и вернуть указатель, если вы хотите это сделать.
2. arr[i++] = root->val; помещает root в arr[0], но с этим массивом больше ничего не происходит, поэтому цель неясна.
3. Жесткое кодирование 100 для размера массива кажется ошибкой. Конечно, есть какое-то дерево с достаточно большим уровнем, чтобы переполнить этот буфер, предполагая, что вы намереваетесь заполнить его за пределами root. Когда вы переключаетесь на malloc, вам, вероятно, нужно планировать realloc.

Вместо того, чтобы возвращать результаты из этой функции, кажется, что передача указателя на предварительно выделенный Структура результата является самой простой.

Способ упростить управление перераспределением и размером - это подойти к проблеме с несколькими проходами. Вот план игры:

1. Получить высоту дерева.
2. Распределить массивы результата и размера столбца в соответствии с высотой дерева.
3. Выполнить второй обход и установить Длина столбцов результатов для каждого уровня.
4. Выделите каждый уровень в соответствии с размером, определенным на шаге 3.
5. Выполните последний проход для заполнения предварительно назначенных уровней результатов.

Вот код:

int height(struct TreeNode *root) {
    if (root) {
        int left = height(root->left);
        int right = height(root->right);
        return 1 + (left > right ? left : right);
    }

    return 0;
}

void set_col_lens(struct TreeNode *root, int *res_col_lens, int depth) {
    if (root) {
        res_col_lens[depth]++;
        set_col_lens(root->left, res_col_lens, depth + 1);
        set_col_lens(root->right, res_col_lens, depth + 1);
    }
}

void fill_levels(struct TreeNode *root, int **res, int *last_items, int level) {
    if (root) {
        int last_item = last_items[level]++;
        res[level][last_item] = root->val;
        fill_levels(root->left, res, last_items, level + 1);
        fill_levels(root->right, res, last_items, level + 1);
    }
}

int **level_order(struct TreeNode *root, int *res_len, int **res_col_lens) {
    if (!root) {
        *res_len = 0;
        return NULL;
    }

    *res_len = height(root);
    int **res = malloc(sizeof(*res) * (*res_len));
    *res_col_lens = calloc(*res_len, sizeof(**res_col_lens));
    int *last_items = calloc(*res_len, sizeof(*last_items));
    set_col_lens(root, *res_col_lens, 0);

    for (int i = 0; i < *res_len; i++) {
        res[i] = malloc(sizeof((*res)[i]) * (*res_col_lens)[i]);
    }

    fill_levels(root, res, last_items, 0);
    free(last_items);
    return res;
}

Одним из преимуществ этого является то, что проблема разбита на простые отдельные этапы.

Другой подход, который я считаю более естественным, заключается в использовании поставьте в очередь и выполните обход в ширину в одном кадре стека. Затем возникает проблема записи абстракции очереди в C, что не сложно, но требует некоторых усилий.