Бинарные деревья. Процедуры, необходимые для работы с бинарными деревьями. Структура хранения бинарных деревьев, страница 2

 

a₁             a₂        a₃

Рисунок 10.4

a

 

            A               B

 

            1       2       3         4         5

 

                    a₁      a₂      a₃

Рисунок 10.5

                                  a

 

A

 

1                  B

 

2         3

 

a₁             a₂           4

 

a₃              5

Рисунок 10.6

Этап 1.

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

-  для каждой вершины все исходящие из нее ребра, кроме самого левого, заменяются на горизонтальные связи с соседней левой вершиной;

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

Этап 2.

Для каждой вершины дерева осуществляется выбор ее левого и правого сына по следующему правилу:

-  левым сыном является нижележащая вершина,

-  правым сыном является вершина расположенная непосредственно справа от данной на одном уровне с ней.

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

Структура хранения бинарных деревьев.

Хранение бинарного дерева в машинной памяти необходимо обеспечить с минимальной избыточностью. Ниже рассматриваются три варианта, в определенной степени отвечающие этому требованию:

-  связанная нелинейная структура,

-  хранение дерева в области свободных узлов,

-  хранение бинарного дерева в массиве с прямой адресацией вершин.

-   

Вариант 1.

Каждая вершина позиционного бинарного дерева представляется записью, включающей три части:

-  ссылка на левого сына вершины (ll),

-  информационная часть (info),

-  ссылка на правого сына (rl).

Пример структуры хранения для бинарного дерева с префиксным кодом {(01),(100),(101)} представлен на рис.10.7.

      ROOT

ll    info    rl

 

NULL   info   rl            ll   info   NULL

 

NULL info NULL      rl   info   ll

 

ll    info    rl          ll    info    rl

Рисунок 10.7

Вариант 2.

При использовании области свободных узлов для хранения бинарного дерева резервируется массив записей со структурой записи аналогичной выше. Отличие заключается в типе полей ll и rl, которые в этом случае должны быть целыми числами. Принцип использования области свободных узлов для хранения бинарного дерева аналогичен описанному выше методу для связанных списков. Рисунок 10.8 иллюстрирует представление дерева с использованием этого варианта структуры хранения.

	R1				ll	info	rl
				R1=2	5	Y	7
		X			1	X	4
					~	~	6
	Y		Z		0	Z	0
					0	Y1	0
Y1		Y2
					0	Y2	0

Рисунок 10.8

Вариант 3.

Полным бинарным деревом с  n уровнями называется дерево, в котором каждый узел уровня n-1 является листом, а каждый узел других уровней имеет непустые левые и правые поддеревья. Узлы такого бинарного дерева могут быть занумерованы так, чтобы номер, назначенный левому сыну, был равен удвоенному номеру, присвоенному его отцу, а номер присваиваемый его брату, на единицу больше. В этом случае нам не требуется связей между различными вершинами в форме указателей. Каждый узел с назначенным ему номером m является отцом сыновей с номерами 2m и 2m+1. Дерево с n уровнями в этом случае логично представить массивом записей info размером 2^n-1 элементов. Можно построить функцию адресации, отображающую префиксный код вершины на множество индексов от 1 до 2^n-1.

Можно распространить такое  представление на любые бинарные деревья путем расширения последних до полного бинарного дерева со специальными отметками для вершин, не входящих в исходное дерево. Пример представления дерева с использованием этой структуры хранения представлен на рис.10.9.

								info	P
		корень					1	Корень	1
							2	A1	1
	A1			B1			3	B1	1
							4	A2	1
A2					B2		5		0
							6		0
							7	B2	1

Рисунок 10.9

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