Двоичное дерево

Cтраница 3

В завершенном двоичном дереве удаленными вершинами часто являются крайние правые кониевке вершины. [31]

В обычном двоичном дереве поиска каждая вершина содержит указатели на двух своих сыновей. Мы преобразуем такое дерево в неоднородное дерево поиска с указателями, заменив указатели у ряда вершин. У всех вершин левого пути1) указатель на левого сына будет теперь указывать на родителя, а у всех вершин правого пути указатель на правого сына будет указывать на родителя. [32]

Полным называется двоичное дерево с корнем, у которого все вершины ( за исключением листьев) имеют по два сына. [33]

Лемма 3.1. Двоичное дерево высоты h содержит не более Ч листьев. [34]

Номера узлов двоичного дерева, соответствующие внутреннему порядку, обладают тем свойством, что номера узлов в левом поддереве для v меньше и, а в правом поддереве больше и. Таким образом, чтобы найти узел с номером w, надо сравнить w с корнем г. Если w r, то искомый узел найден. [35]

Каждый узел двоичного дерева имеет не больше двух узлов-отростков. Если у узла действительно два отростка, они называются левым и правым отростками. Такие отростки в двоичных деревьях не являются взаимозаменяемыми. На рис. 8.11 показаны три различных двоичных дерева: деревья, показанные на рис. 8.11 ( б) и рис. 8.11 ( в), считаются разными. [36]

Удаление из двоичного дерева) В этом упражнении мы обсудим удаление элементов из дерева двоичного поиска. Алгоритм удаления не является таким простым, как алгоритм вставки. При удалении элемента могут быть три случая: элемент находится в концевом узле дерева ( не имеет узлов-потомков); элемент находится в узле, в которого есть один узел-потомок; элемент находится в узле, у которого имеется два узла-потомка. [37]

Послойный обход двоичного дерева) Программа, приведенная на рис. 15.16, демонстрирует три рекурсивных способа обхода двоичного дерева: последовательный обход, обход в ширину и обратный обход. В этом упражнении представлен послойный обход двоичного дерева, при котором значения узлов печатаются от уровня к уровню, начиная с корневого узла. Значения в узлах печатаются по уровням дерева слева направо. Алгоритм послойного обхода не является рекурсивным алгоритмом. Он использует объект очереди для управления процессом вывода узлов на печать. [38]

Обход узлов двоичного дерева, построенный с использованием следующего рекурсивного алгоритма: просмотр в обратном порядке вершин левого поддерева с. [39]

Оптимальная расстановка. [40]

Структура центрированного двоичного дерева может быть наложена на список так, как показана на рис. 6.4. Это упорядоченный список чисел от единицы до тридцати одного. Для этого дерева так же, как для дерева из главы 4, выполнено соглашение о том, что левый преемник узла содержит меньшую величину, а правый преемник - большую. Корневой узел этого дерева содержит медиану списка. Поскольку медиана должна располагаться в центре списка, корневой узел должен располагаться в центре поля памяти, отведенного под список. [41]

Поиск по двоичному дереву для 100 терминалов требует 100 проходов по дереву. [42]

Поиск по двоичному дереву становится неудобным также тогда, когда по каким-либо соображениям необходимо, чтобы элементы индек са были упорядочены по ключам. [43]

Описанная выше структура двоичного дерева позволяет существенно сократить при поиске перебор записей, но определенный перебор все же остается. Представляется весьма заманчивым без перебора сразу вычислять по ключу / С указатель местоположения соответствующей записи. M будем размещать ключевые записи, состоящие из двух элементов: ключа и ссылки на текстовую запись. Массив S разбивается на пары соседних элементов S [ i ], Sli l ], предназначаемые для ключевых записей. [44]

Рассмотрим определение прохождения двоичного дерева во внутреннем порядке, данное в разд. При создании алгоритма, который присваивает узлам номера в соответствии с внутренним порядком, хорошо было бы отразить в нем определение прохождения во внутреннем порядке. Один из таких алгоритмов приведен ниже. Заметим, что он рекурсивно обращается к себе для нумерации поддерева. [45]

Страницы: 1 2 3 4