Бинарные деревья
Бинарные деревья являются наиболее используемой разновидностью деревьев.
Согласно представлению деревьев в памяти ЭВМ каждый элемент будет записью, содержащей 4 поля. Значения этих полей будут соответственно ключ записи, ссылка на элемент влево-вниз, на элемент вправо-вниз и на текст записи.
При построении необходимо помнить, что левый сын имеет ключ меньший, чем у отца, а значение ключа правого сына больше значения ключа отца. Например, построим бинарное дерево из следующих элементов: 50, 46, 61, 48, 29, 55, 79. Оно имеет следующий вид:
Получили упорядоченное бинарное дерево с одинаковым числом уровней в левом и правом поддеревьях. Это - идеально сбалансированное дерево, то есть дерево, в котором левое и правое поддеревья имеют уровни, отличающиеся не более чем на единицу.
Для создания бинарного дерева надо создавать в памяти элементы типа (рис. 4.5):
Операция V = MakeTree(Key, Rec) - создает элемент (узел дерева) с двумя указателями и двумя полями (ключевым и информационным) .
Вид процедуры MakeTree:
| Псевдокод
p = getnode r(p) = rec k(p) = key v = p left(p) = nil right(p) = nil | Паскаль
New(p); p^.r := rec; p^.k := key; v := p; p^.left := nil; p^.right := nil; |
