Структуры и алгоритмы обработки данных


Краткая теория - часть 2


1. В каждом узле дерева отсекают все ветви, кроме крайних левых, соответствующих старшим сыновьям;

2. Соединяют горизонтальными линиями сыновей одного родителя (узла);

2.   Старшим сыном в каждом узле полученной структуры будет узел под обрабатываемым узлом.

 

 

 

Построение бинарных деревьев

Согласно представлению деревьев в памяти ЭВМ каждый элемент (узел бинарного дерева) будет записью, содержащей четыре поля. Значением этих полей будут соответственно ключ записи, ссылка на элемент влево-вниз, на элемент вправо-вниз и на текст записи.

При построении необходимо помнить, что левый сын имеет ключ меньше чем отец (родитель). Значение ключа правого сына больше значения ключа отца.

Например, узлы дерева имеют значения 6, 21, 48, 49, 52, 86, 101.

Бинарное дерево будет иметь вид:

 

 

Получили упорядоченное бинарное дерево с минимальным числом уровней.

Идеально сбалансированное дерево - это дерево, в котором левое и правое поддеревья имеют уровни, отличающиеся не больше, чем на единицу.

 




- Начало -  - Назад -  - Вперед -



Книжный магазин