Нужны ли структуры в двоичных деревьях поиска

Question

Я просмотрел код BST и увидел, что каждый узел представляет собой структуру.Это необходимо?

Answer 1

int flat_tree[ 1000 ][ 3 ];
    // for each tree node, value is stored in element [id][0]
                        // id of left_child stored in element [id][1]
                        // id of right_child stored in element [id][2]

…

Я не собираюсь идти дальше с этим.

Вообще говоря, structс/classes используются для любого типа связанной структуры данных.Также, как правило, любая функция системы типов может быть отключена или проигнорирована, и вы можете делать все (выделение кучи и т. д.) в одном массиве. intЭто очень болезненно.

Answer 2

Нет, это может быть класс.Он не может быть примитивом, поскольку ему необходимо хранить значение, а также указывать на дочерние элементы.

Ну, я должен сказать, что вы также можете представить свой BST в виде массива, где левый и правый дочерние элементы узла в позиции i находятся на позициях 2 * i + 1 и 2 * i + 2, соответственно.Но тогда вам придется беспокоиться об изменении размера, и вам понадобится специальное значение для представления нуля, а операции удаления станут довольно сложными.Я не рекомендую этот подход как нечто иное, кроме академического упражнения.

Answer 3

Это не обязательно.
Но поскольку данные, содержащиеся в узле, вместе с двумя ссылками образуют логический объект, они обычно объединяются в структуру.Чтобы стало проще писать функции, которые принимают узел в качестве аргумента или возвращают узел.

Answer 4

Нет, не строго говоря.Во времена FORTRAN люди использовали параллельные массивы или двумерные массивы.

В разделе Тони Хоара «Структурное программирование» Даля, Дейкстры и Хоара говорилось о структурировании данных и типах записей.

Answer 5

Вы можете сделать проще, чем параллельные массивы, если ваша полезная нагрузка допускает контрольное значение:вы можете использовать неявное дерево (то есть вообще не заморачиваться со ссылками).

payload_type a[tree_size];

Просто длинный плоский массив, содержащий только значения полезной нагрузки, с позицией в массиве, кодирующей структуру ссылок:

• a[0] является корнем
• a[1] это корень->слева
• a[2] это root->право
• a[3] это root->left->left
• a[4] это корень->слева->справа
• ...

Для узла в позиции i перейдите к 2*i+1 слева и 2*i+2 справа.

Вы инициализируете его всеми контрольными значениями и начинаете добавлять что-то...