Алгоритм создания дерева бинарного поиска
Пусть заданы элементы с ключами: 14, 18, 6, 21, 1, 13, 15. После выполнения нижеприведенного алгоритма получится дерево, изображенное на рис.4.6. Если обойти полученное дерево слева направо, то получим упорядочивание: 1, 6, 13, 14, 15, 18, 21.
| Псевдокод
read (key, rec) tree = maketree(key rec) p = tree q = tree while not eof do read (key, rec) v = maketree(key, rec) while p <> nil do q = p if key < k(p) then p = left(p) else p = right(p) endif endwhile if key < k(q) then left(p) = v else right(p) = v endif if q=tree then ' только корень' endif return | Паскаль
read (key, rec); tree := maketree(key rec); p := tree; q := tree; while not eof do begin read (key, rec); v := maketree(key, rec); while p <> nil do begin q := p; if key < p^.k then p := p^.left else p := p^.right; end; if key < q^.k then p^.left := v else p^.right := v; end if q=tree then writeln(‘Только корень’); exit |
