Понятно, что если количество детей каждой вершины ограничивается некоторой константой k, то такое дерево можно реализовать подобно двоичному. Таким образом, для каждой вершины мы вводим поля child1, child2, …, childk для хранения указателей на соответствующих детей вместо полей left и right. Однако, если количество детей k заранее неизвестно, то вы не сможете «угадать», сколько полей (или массивов при представлении дерева массивами) необходимо ввести.
Проблемы возникают даже тогда, когда вам точно известно максимальное количество детей каждой вершины. Основным недостатком данного метода является явный перерасход памяти, так как количество детей не обязательно обязано быть равным k. Чаще всего оно много меньше заданной константы, что приводит к расходованию памяти впустую.
Что же можно сделать? Рассмотрим, как же можно использовать структуру двоичных деревьев для представления деревьев с произвольным ветвлением. Суть метода проста: будем использовать три дополнительных поля – p (родитель), left-child (левый ребенок) и right-sibling (правый сосед). При этом в поле left-child хранится указатель на левого ребенка, а в поле right-sibling – указатель на правого соседа (вершину, которая является ребенком того же родителя, следующим непосредственно за данной).
Рассмотрим более подробно основанную на этой идее схему хранения деревьев с произвольным ветвлением. Она называется «левый ребенок – правый сосед» (left-child, right-sibling representation). Как и раньше, каждой вершине сопоставлен указатель p на родителя. Кроме того, имеются два поля:
· left-child указывает на левого ребенка вершины x;
· right-sibling указывает на следующего по старшинству брата вершины x.
При left-child = 0 вершина детей не имеет; если же вершина x является крайним правым ребенком своего родителя, right-sibling = 0.
Перечисленные выше методы представления деревьев не универсальны. Способ представления зависит от специфики задачи и меняется от задачи к задаче. Так, существуют деревья, в которых нужно идти от листьев к вершине, поэтому указатели на детей не нужны. Если же требуется хранить полное двоичное дерево (например, при реализации кучи), можно использовать один массив, в котором номера родителя и детей получаются делением и умножением на 2 соответственно.
1. Реализуйте на C++ контейнерный класс (шаблонный или для заданного типа), инкапсулирующий функциональность двоичного дерева поиска, используя любой способ представления этого дерева: с помощью полей-указателей на узлы или с использованием массивов.
2. Покажите, что высота двоичного дерева с n вершинами не менее log n.
3. Напишите нерекурсивный алгоритм, печатающий ключи в двоичном дереве поиска в неубывающем порядке.
4. Докажите правильность алгоритма поиска следующего элемента.
Т. Кормен, Ч. Лейзерсон, Р. Ривест [2001], Алгоритмы. Построение и анализ, МЦНМО, М., 92 – 100, 207 – 213, 236 – 246
А. Шень, Программирование. Теоремы и задачи, http://tower.kture/
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.