Перевод дерева в бинарное

Представление любого дерева, леса бинарными деревьями.

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

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

· 1. В каждом узле оставить только ветвь к старшему сыну (вертикальное соединение);

· 2. Соединить горизонтальными ребрами всех братьев одного отца;

· 3. Таким образом перестроить дерево по правилу:

o левый сын — вершина, расположенная под данной;

o правый сын — вершина, расположенная справа от данной (т.е. на одном ярусе с ней).

· 4. Развернуть дерево таким образом, чтобы все вертикальные ветви отображали левых сыновей, а горизонтальные — правых.

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

В процессе преобразования правый указатель каждого узла бинарного дерева будет указывать на соседа по уровню. Если такового нет, то правый указатель NIL. Левый указатель будет указывать на вершину следующего уровня. Если таковой нет, то указатель устанавливается на NIL.

Рис.6.14. Исходное дерево

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

Рис. 6.16. Представление дерева в виде бинарного

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

Правило построения бинарного дерева из леса: корни всех поддеревьев леса соединить горизонтальными связями. В полученном дереве узлы в данном примере будут располагаться на трех уровнях. Далее перестраивать по ранее рассмотренному плану: в начале поддерево с корнем А, затем В и затем Н. В результате преобразования упорядоченного леса в бинарное дерево получается полное бинарное дерево с левым и правым поддеревом.

рис.6.17. Упорядоченный лес

Рис.6.18. Промежуточный результат перестройки леса

Рис. 6.19. Представление леса в виде 2-го дерева

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

Машинное представление деревьев в памяти ЭВМ.

Деревья можно представлять с помощью связных списков и массивов (или последовательных списков).

Чаще всего используется связное представление деревьев, т.к. оно очень сильно напоминает логическое. Связное хранение состоит в том, что задается связь от отца к сыновьям. В бинарном дереве имеется два указателя, поэтому удобно узел представить в виде структуры:

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

Рассмотрим машинное представление бинарного дерева, изображенного на рис. 6.20.

Рис. 6.20. Логическое представление дерева

Рис. 6.21. Машинное связное представление дерева представленного на рис.6.20

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

Выбор метода последовательного представления деревьев определяется также набором тех операций, которые должны быть выполнены над древовидными структурами. (Пример статистической древовидной структуры — пирамидальный метод сортировки). Простейший метод представления дерева в виде последовательной структуры заключается во введении вектора FATHER, задающего отбор для всех его вершин. Этот метод можно использовать также для представления леса. Недостаток метода — он не отображает упорядочения вершин дерева. Если в предыдущем примере поменять местами вершины 9 и 10, последовательное представление останется тем же.

Рис. 6.22. Диаграммы дерева: а) исходное б) перестройка в бинарное

Последовательное представление дерева, логическая диаграмма которого дана на рис. 6.22, задается следующим образом:

i 1 2 3 4 5 6 7 8 9 10 FATHER [i] 0 1 1 1 2 3 3 7 4 4,

где ветви определяются как

Вершины 2,3,4 являются сыновьями вершины 1, вершина 5 — сыном вершины 2, вершины 6,7 — сыновьями вершины 3, вершина 8 имеет отца вершина 7 и вершины 9 и 10 — сыновья вершины 4.

Числовые поля данных используются здесь, чтобы упростить представление дерева. Корневая вершина не имеет отца, поэтому вместо отца для нее задается нулевое значение.

Общее правило: если T обозначает индекс корневой вершины дерева, то FATHER[T] = 0.

Другой метод последовательного представления деревьев заключается в использовании физической смежности элементов машинной памяти вместо одного из полей LPTR или RPTR, например, способ опускания полей, т.е. чтобы вершины появлялись в нисходящем порядке. Дерево (рис.6.22б), можно описать как:

Рис. 6.23. Последовательное представление дерева методом опускания полей

где RPTR,DATA и TAG представляют векторы. В данном методе указатель LPTR не требуется, т.к. если бы он не был пуст, то указывал бы на вершину, стоящую непосредственно справа от данной. Вектор TAG — бинарный вектор, в котором единицы отмечают концевые вершины исходного дерева. При таком представлении имеются значительные потери памяти, т.к. свыше половины указателей RPTR оказываются пустыми. Эти пустые места можно использовать путем установки указателя RPTR каждой данной вершины на вершину, которая следует непосредственно за поддеревом, расположенном под ней. В таком представлении поле RPTR переименовывается в RANGE:

Рис. 6.24. Последовательное представление дерева с размещением вершин в возрастающем порядке

В этом случае поле TAG не требуется поскольку концевой узел определяется условием RANGE(P) = P + 1.

Третий метод состоит в представлении дерева общего вида на основе его восходящего обхода. Такое представление состоит из двух векторов: один вектор описывает все вершины дерева в восходящей последовательности, а второй — задает полустепени исхода этих вершин (см. рис.6.25). Восходящий метод представления удобен для вычисления функцией, заданных на определенных вершинах дерева (например, использование таких функций для генерации объектного кода по обратной польской записи некоторого выражения).

Рис. 6.25. Последовательное представление дерева на основе восходящего обхода

В заключении приведем два важных понятия.

Подобие бинарных деревьев — два дерева подобны, если они имеют одинаковую структуру (форму).

Эквивалентные бинарные деревья — два дерева эквивалентные, если они подобны, и если соответствующие вершины у них содержат одинаковую информацию.

Источник

Русские Блоги

Преобразование общего дерева и двоичного дерева, леса и бинарного дерева

Преобразование общего дерева и двоичного дерева, леса и бинарного дерева

Общее дерево переводится в бинарное дерево

По словам ребенка ребенка — метод хранения брата, конкретные шаги:

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

2. Стирание: Только соединение между каждым узлом только связь между левым ребенком, стирает связь между точками изменений и другими детьми. Можно понять, что есть только один ребенок указатель на каждый узел, пусть он указует на первый ребенок.

3. Поворот: Реформа пунктирная линии достичь 45 ° от горизонтального направления, а также в правильном направление препятствий. Сплошная линия в исходном дереве остается косой. Это образует дерево два-вилки.

Бинарное дерево сводится к общему дереву

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

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

2. Стирание: Стереть все двойники в исходном двоичном дереве стертого с проводкой правого ребенка. Право ребенка здесь, по существу, братья в исходном дереве, и вытерла линия отношения между братьями.

3. Организация: Изменить ломаную линию на сплошную линию, а также организовать узел.

Перевод лесов в бинарное дерево

Этапы превращения лесов в бинарном дереве, являются:
1. Превращение в каждой subtroduction в лесу в соответствующее двоичное дерево, образуют лес рядом bifuries.

2. В соответствии с порядком деревьев в лесу, bifurcous дерево последовательно используется в качестве правого дерева в bifurcous корневого узла, так что весь лес генерируется на велосипеде.

3. Корневой узел первого дерева является корневым узлом генерируемого двоичного дерева.

Два бинарное дерево сводится к лесу

Этапы бинарного дерева, которое преобразуется лесов:

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

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

Эта часть процесса трансформации демонстрирует себя попробовать!

Источник

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 — содержит информацию, связанную с вершиной.

Источник