0

Доброго времени суток. Есть бинарное дерево поиска. Нужно его сбалансировать, но не получается из дерева сделать массив объектов. По-идее, должно быть как-то так, но почему-то не все элементы попадают в массив.

void GetMassive(int &n, tree_node * root, DataM *M)
{
    if (root!=NULL)
    {
        GetMassive(n,root->left,M);
        M[n++] = root->info;
        GetMassive(n,root->right,M);
    }
}
3
  • Мне кажется вместо while должен быть if
    – diralik
    21 мая 2017 в 20:24
  • А ещё желательно либо int n сделать глобальной переменной, либо заменить int n на int &n
    – diralik
    21 мая 2017 в 20:26
  • 1
    Вся проблема в этом и была. Передавать надо было через указатель..
    – TorSen
    21 мая 2017 в 20:42

1 ответ 1

2

В вашем коде есть две проблемы.

  1. while (root!=NULL). Если код зайдёт внутрь этого цикла, то он из него уже не выйдет, потому что значение переменной root не меняется внутри цикла. Нужно заменить while на if.
  2. Параметр функции int n. Рассмотрим самый первый вызов функции, n == 0. Далее выполняется строчка GetMassive(n,root->left,M);. Если левое поддерево не пусто, то первые несколько элементов массива M заполнятся. Но в самом первом вызове функции по прежнему n == 0. Поэтому элемент M[0] перезапишется. Нужно либо n сделать глобальной переменной, либо заменить int n на int &n.

Возможное решение:

#include <iostream>

typedef int DataM;

struct tree_node {
    DataM info;
    tree_node *left = nullptr;
    tree_node *right = nullptr;

    tree_node(DataM info) : info(info) {}
};

void GetMassive(tree_node *root, DataM *M, int &n) {
    if (root != nullptr) {
        GetMassive(root->left, M, n);
        M[n++] = root->info;
        GetMassive(root->right, M, n);
    }
}

void GetMassive(tree_node *root, DataM *M) {
    int n = 0;
    GetMassive(root, M, n);
}

int main() {
    tree_node *left = new tree_node(1);
    tree_node *right = new tree_node(4);
    tree_node *right_left = new tree_node(3);
    tree_node *right_right = new tree_node(5);
    tree_node *root = new tree_node(2);

    right->left = right_left;
    right->right = right_right;
    root->left = left;
    root->right = right;

    DataM array[5];
    GetMassive(root, array);
    for (int array_i : array) {
        std::cout << array_i << std::endl;
    }
    return 0;
}
1
  • 1
    Да, я по наводке выше исправил :) Спасибо.
    – TorSen
    21 мая 2017 в 20:43

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.