Формирование дерева
- В начале дерево пусто.
- Первую запись с ключом k1 считаем корнем дерева. Ссылки на соседние вершины – nil.
- Если ключ следующей записи k2 меньше k1, то этой записи поставим в соответствие левую вершину, иначе – правую. Ссылки на соседние вершины – nil.
- Для размещения следующих вершин сравниваем ключ kn с k1. В зависимости от сравнения идем вправо или влево, далее производим сравнение и выбираем направление до тех пор, пока не найдем подходящую вершину, к которой можно присоединить новую.
Пример: записи имеют следующие ключи 7, 4, 10, 1, 6, 8, 2
Procedure vstavka(var p: ss; k: integer);
Begin
If p = nil then
Begin
New(p); p^.key:=k; p^.left:=nil; p^.right:=nil;
End
Else
If k < p^.key then vstavka(p^.left, k);
If k > p^.key then vstavka(p^.right, k);
End;