Представление двоичных деревьев посредством указателей

Вопрос 19) Представление бинарных деревьев.

Бинарные деревья достаточно просто могут быть представлены в виде списков или массивов. Списочное представление бинарных деревьев основано на элементах, соответствующих узлам дерева. Каждый элемент имеет поле данных и два поля указателей. Один указатель используется для связывания элемента с правым потомком, а другой – с левым. Листья имеют пустые указатели потомков. При таком способе представления дерева обязательно следует сохранять указатель на узел, являющийся корнем дерева.

Можно заметить, что такой способ представления имеет сходство с простыми линейными списками. И это сходство не случайно. На самом деле рассмотренный способ представления бинарного дерева является разновидностью мультисписка, образованного комбинацией множества линейных списков. Каждый линейный список объединяет узлы, входящие в путь от корня дерева к одному из листьев.

указатель правого указатель правого

Приведем пример программы, которая осуществляет создание и редактирование бинарного дерева, представленного в виде списковой структуры

procedure node_search (pnt_s:pointer; var current_s:pointer);

if not not (pnt_n^.name=s) then

procedure node_list (pnt_s:pointer);

if pnt_n^.left <> nil then node_list (pnt_n^.left);

if pnt_n^.right <> nil then node_list (pnt_n^.right);

procedure node_dispose (pnt_s:pointer);

writeln(‘текущий узел -‘,current^.name);

writeln(‘1-присвоить имя левому потомоку’);

writeln(‘2-присвоить имя правому потомку’);

writeln(‘3-сделать узел текущим’);

writeln(‘4-вывести список всех узлов’);

writeln(‘5-удалить потомков текущего узла’);

if current^.left= nil then new(pnt)

if current^.right= nil then new(pnt)

node_search (pnt_s, current_s);

if current_s <> nil then current:=current_s;

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

Если число уровней дерева в процессе обработки не будет существенно изменяться, то такой способ представления полного бинарного дерева будет значительно более экономичным, чем любая списковая структура.

Однако далеко не все бинарные деревья являются полными. Для неполных бинарных деревьев применяют следующий способ представления. Бинарное дерево дополняется до полного дерева, вершины последовательно нумеруются. В массив заносятся только те вершины, которые были в исходном неполном дереве. При таком представлении элемент массива выделяется независимо от того, будет ли он содержать узел исходного дерева. Следовательно, необходимо отметить неиспользуемые элементы массива. Это можно сделать занесением специального значения в соответствующие элементы массива. В результате структура дерева переносится в одномерный массив. Адрес любой вершины в массиве вычисляется как

где k-номер уровня вершины, i- номер на уровне k в полном бинарном дереве. Адрес корня будет равен единице. Для любой вершины можно вычислить адреса левого и правого потомков

Главным недостатком рассмотренного способа представления бинарного дерева является то, что структура данных является статической. Размер массива выбирается исходя из максимально возможного количества уровней бинарного дерева. Причем чем менее полным является дерево, тем менее рационально используется память.

Источник

30. Бинарные деревья.

Существуют m-арные деревья, т.е. такие деревья у которых полустепень исхода каждой вершины меньше или равна m (где m может быть равно 0,1,2,3 и т.д.). Если полустепень исхода каждой вершины в точности равна либо m, либо нулю, то такое дерево называется ПОЛНЫМ m-АРНЫМ ДЕРЕВОМ.

При m=2 такие деревья называются соответственно БИНАРНЫМИ, или ПОЛНЫМИ БИНАРНЫМИ.

На рисунке 6.12(a) изображено бинарное дерево, 6.12(b)- полное бинарное дерево, а на 6.12(c) показаны все четыре возможных расположения сыновей некоторой вершины бинарного дерева.

Рис. 6.13. Изображения бинарных деревьев

В позиционном бинарном дереве каждая вершина представлена единственным образом посредством строки символов над алфавитом , при этом корень характеризуется пустой строкой. Любой сын вершины «u» характеризуется строкой, префикс (начальная часть) которой является строкой, характеризующей «u». Примером бинарного дерева является фамильное дерево с отцом и матерью человека в качестве его потомков. Еще один пример — это арифметическое выражение с двухместными операциями, где каждая операция представляет собой ветвящийся узел с операндами в качестве поддеревьев.

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

Правило построения бинарного дерева из любого дерева:

• 1. В каждом узле оставить только ветвь к старшему сыну (вертикальное соединение);
• 2. Соединить горизонтальными ребрами всех братьев одного отца;
• 3. Таким образом перестроить дерево по правилу:
  • левый сын — вершина, расположенная под данной;
  • правый сын — вершина, расположенная справа от данной (т.е. на одном ярусе с ней).
• 4. Развернуть дерево таким образом, чтобы все вертикальные ветви отображали левых сыновей, а горизонтальные — правых.

В результате преобразования любого дерева в бинарное получается дерево в виде левого поддерева, подвешенного к корневой вершине. В процессе преобразования правый указатель каждого узла бинарного дерева будет указывать на соседа по уровню. Если такового нет, то правый указатель NIL. Левый указатель будет указывать на вершину следующего уровня. Если таковой нет, то указатель устанавливается на NIL. Рис.6.14. Исходное деревоРис.6.15 Промежуточный результат перестройки дереваРис. 6.16. Представление дерева в виде бинарного Описанный выше метод представления произвольных упорядоченных деревьев посредством бинарных деревьев можно обобщить на представление произвольного упорядоченного леса. Правило построения бинарного дерева из леса: корни всех поддеревьев леса соединить горизонтальными связями. В полученном дереве узлы в данном примере будут располагаться на трех уровнях. Далее перестраивать по ранее рассмотренному плану: в начале поддерево с корнем А, затем В и затем Н. В результате преобразования упорядоченного леса в бинарное дерево получается полное бинарное дерево с левым и правым поддеревом. Машинное представление деревьев в памяти ЭВМ. Деревья можно представлять с помощью связных списков и массивов (или последовательных списков). Чаще всего используется связное представление деревьев, т.к. оно очень сильно напоминает логическое. Связное хранение состоит в том, что задается связь от отца к сыновьям. В бинарном дереве имеется два указателя, поэтому удобно узел представить в виде структуры:

LPTR

DATA

RPTR

где LPTR — указатель на левое поддерево, RPTR — указатель на правое поддерево, DATA — содержит информацию, связанную с вершиной.

Источник

9.3. Представление деревьев в эвм

Обсуждению представлений деревьев можно предпослать в точности те же рас­суждения, что были предпосланы обсуждению представлений графов (см. раз­дел 7.4). Кроме того, следует подчеркнуть, что задача представления деревьев в программе встречается гораздо чаще, чем задача представления графов общего вида, а потому методы ее решения оказывают еще большее влияние на практику программирования.

9.3.1. Представление свободных, ориентированных и упорядоченных деревьев

Всякое свободное дерево можно ориентировать, назначив один из узлов корнем. Всякое ордерево можно произвольно упорядочить. Всякое упорядоченное дерево можно представить бинарным деревом, проведя правую связь к старшему брату, а левую — к младшему сыну.

На рис. 9.10 приведены диаграммы упорядоченного и соответствующего ему би­нарного деревьев.

Рис. 9.10. Упорядоченное и бинарное деревья

Таким образом, достаточно рассмотреть представление в ЭВМ бинарных де­ревьев.

Из данного представления следует, что множество бинарных деревьев взаимнооднозначно соответствует множеству упорядоченных лесов упорядоченных деревьев.

9.3.2. Представление бинарных деревьев

Обозначим через n(р) объем памяти, занимаемой представлением бинарного де­рева, где р — число узлов. Наиболее часто используются следующие представле­ния бинарных деревьев.

1. Списочные структуры: каждый узел представляется записью типа N, содержащей два поля (l и r) с указателями на левый и правый узлы и еще одно поле i для хранения указателя на информацию об узле. Дерево представля­ется указателем на корень. Тип N обычно определяется следующим образом: N = record i : info; l, r : N end record. Для этого представления n(р) = Зр.

1. Упакованные массивы: все узлы располагаются в массиве, так что все узлы поддерева данного узла располагаются вслед за этим узлом. Вместе с каждым узлом хранится индекс узла, который является последним узлом поддерева данного узла. Дерево Т обычно определяется следующим образом:

1. Польская запись: аналогично, но вместо связей фиксируется «размеченная степень» каждого узла (например, 0 означает, что это лист, 1 — есть левая связь, но нет правой, 2 — есть правая связь, но нет левой, 3 — есть обе связи). Дерево Т определяется следующим образом:

9.3.3. Обходы бинарных деревьев

Большинство алгоритмов работы с деревьями основаны на обходах. Возможны следующие основные обходы бинарных деревьев: Прямой (левый) обход: попасть в корень, обойти левое поддерево, обойти правое поддерево. Обратный (симметричный) обход: обойти левое поддерево, попасть в корень, обойти правое поддерево. Концевой (правый) обход: обойти левое поддерево, обойти правое поддерево, попасть в корень. Кроме трех основных, возможны еще три соответствующих обхода, отличающих­ся порядком рассмотрения левых и правых поддеревьев. Этим исчерпываются обходы, если в представлении фиксированы только связи «отец-сын». ЗАМЕЧАНИЕ Если кроме связей «отец-сын» в представлении есть другие связи, то возможны и другие (более эффективные) обходы. «Деревья», в которых пустые поля l и r в структуре N используются для хранения дополнительных связей, называются прошитыми деревьями. Пример Концевой обход дерева выражения а+ b с дает обратную польскую запись этого выражения: abc. ОТСТУПЛЕНИЕ Польская запись выражений (прямая или обратная) применяется в некоторых языках программирования непосредственно и используется в качестве внутреннего представле­ния программ во многих трансляторах и интерпретаторах. Причина заключается в том, что такая форма записи допускает очень эффективную интерпретацию (вычисление зна­чения) выражений. Например, значение выражения в обратной польской записи может быть вычислено при однократном просмотре выражения слева направо с использованием одного стека. В таких языках, как Forth и PostScript, обратная польская запись исполь­зуется как основная.

Источник