Упорядоченный обход дерева AVL, сохранение значений в массиве - PullRequest
Новая
       8

Упорядоченный обход дерева AVL, сохранение значений в массиве

0 голосов
/ 19 мая 2018

Я пытаюсь перебрать порядок дерева AVL (от минимального значения до максимального значения) и сохранить значения в массиве.Как я могу сделать такую ​​вещь?Я застрял в этой рекурсии и не могу понять, как это сделать правильно, вот что у меня есть: 

// Called with node = root node of the AVL tree
// x is the length of the array
// y is 0 at the start
// array is the array I want to fill

void inorder(int* array,Tree_Node* node,int x,int y)
{
    if(!node)
    {
        return;
    }
    inorder(array, node->getLeft(), x, y);

    array[y] = GET_ID(node->getkey());
    y++;
    if (y == x)
    {
        return;
    }
    inorder(array, node->getRight(), x, y);
}

1 Ответ

0 голосов
/ 19 мая 2018

Большая проблема в том, что индексация вашего массива неверна.Рассмотрим обход в порядке произвольного узла.Вы пишете все под левым потомком, начиная с индекса y.Затем вы игнорируете то, что только что сделали, и записываете значение текущего узла в индекс y.Тогда, поскольку вы всегда увеличиваете y, вполне возможно, что y > x в точке, где вы проверяете y == x, и вы пишете за пределами.

Я бы настоятельно рекомендовал решить это с помощью std::vector (чья функция-член data() может использоваться как массив, если вам это нужно для дальнейшей обработки).Это также позволит вам избавиться от ограничения длины: 

void inorder(Tree_Node* node, std::vector<int>& vector)
{
    if (!node) return;
    inorder(node->getLeft(), vector);

    vector.push_back(GET_ID(node->getkey()));

    inorder(node->getRight(), vector);
}

Однако, если вам придется использовать массивы (потому что ручная реализация деревьев AVL часто делается в образовании, а некоторые преподаватели достаточно сумасшедшие, чтобы требовать, чтобывы не используете все доступные вам функции), вы все еще можете это исправить, возвращая текущий индекс массива из функции: 

int inorder(int* array, Tree_Node* node, int size, int y = 0)
{
    if (!node) return y;
    y = inorder(array, node->getLeft(), size, y);

    if (y >= size) return y; /* Check before you write! */
    array[y++] = GET_ID(node->getkey());

    return inorder(array, node->getRight(), size, y);
}
...