ВУЗ:
Составители:
42
S2. [Поиск влево.] Если LTAG(Q) = ”+”, то Q ← LLINK(Q) и повто-
рить этот шаг; в противном случае закончить алгоритм. ■
Заметим, что в данном случае стек не требуется, как при решении
этой же задачи с помощью алгоритма Т.
Если в алгоритме S поменять L на R и R на L, перевернув тем самым
дерево так, что левые и правые поддеревья поменяются местами, то по-
лучим следующий алгоритм определения $Р по заданному Р.
Алгоритм S’. (Обратный (симметричный) предшественник в про-
шитом бинарном дереве.)
Если Р указывает на узел бинарного дерева, то этот алгоритм пере-
менной Q присваивает значение $Р.
S’1. [LLINK(P) − нить?] Q ← LLINK(P). Если LTAG(P) = ”−”, то за-
кончить алгоритм.
S’2. [Поиск вправо.] Если RTAG(Q) = ”+”, то Q ← RLINK(Q) и по-
вторить этот шаг; в противном случае закончить алгоритм. ■
Представление в памяти ЭВМ бинарного дерева (см. рис. 14) как
прошитого дерева может иметь вид связанного списка с головным узлом,
изображённого на рис. 19. Заметим, что особые нити, возникшие на
рис. 16 в «самом левом» и «самом правом» узлах этого дерева, здесь на-
правлены к головному узлу.
Рис. 19. Представление прошитого бинарного дерева в памяти ЭВМ
Следует отметить, что для выполнения алгоритма Т прохождения
дерева с пустыми связями требуется (15n + a + 3) единиц времени, а для
алгоритма прохождения прошитого дерева – (11n − a + 8) единиц, где n –
число узлов в дереве, а – число концевых правых связей.
Анализируя два рассмотренных подхода к прохождению бинарных
деревьев, можно сделать следующие выводы:
A + +
F + +
C + +
E − +
B + −
D − −
+ +
G − − H − − J − −
Страницы
- « первая
- ‹ предыдущая
- …
- 40
- 41
- 42
- 43
- 44
- …
- следующая ›
- последняя »
