Балансировка бинарного дерева поиска

902

24 мая 2017, 08:10

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

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

Answer 1

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

while (root!=NULL). Если код зайдёт внутрь этого цикла, то он из него уже не выйдет, потому что значение переменной root не меняется внутри цикла. Нужно заменить while на if.
Параметр функции 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;
}