Структуры необходимы в бинарных деревьях поиска

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 s / class es используются для любого типа связанной структуры данных. Также обычно любая функция системы типов может быть побеждена или проигнорирована, и вы можете делать все (выделение кучи и т. Д.) В одном массиве int s очень болезненным образом.

Answer 2

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

Answer 3

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

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

Answer 4

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

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

Answer 5

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

payload_type a[tree_size];

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

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

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

Вы инициализируете его для всех часовых значений и начинаете добавлять вещи ...