женные оценки можно получить, прибегнув к прямолинейным индуктивным аргументам, подобным использованным в этом разделе. В последующих главах мы продолжим рассмотрение математических свойств деревьев по мере возникновения необходимости. Пока можно вернуться к теме алгоритмов.

Упражнения

t> 5.68 Сколько внешних узлов существует в Л/-арном дереве с n внутренними узлами? Используйте свой ответ для определения объема памяти, необходимого для представления такого дерева, если считать, что для каждой связи и каждого элемента требуется по одному слову памяти.

5.69 Приведите верхнее и нижнее граничные значения высоты Л/-арного дерева с n внутренними узлами.

о 5.70 Приведите верхнее и нижнее граничные значения длины внутреннего пути Л/-арного дерева с N внутренними узлами.

5.71 Приведите верхнее и нижнее граничные значения количества листьев в бинарном дереве с n узлами.

5.72 Покажите, что если листья внешних узлов в бинарном дереве различаются на константу, то высота составляет 0{\on).

о 5.73 Дерево Фибоначчи высотой п > 2 - это бинарное дерево с деревом Фибоначчи высотой п - \ ъ одном поддереве и дерево Фибоначчи высотой п - 2 - ъ другом. Дерево Фибоначчи высотой О - это единственный внешний узел, а дерево Фибоначчи высотой 1 - единственный внутренний узел с двумя внешними дочерними узлами (см. рис. 5.14). Выразите высоту и длину внешнего пути дерева Фибоначчи высотой п в виде функции n (количества узлов в дереве),

5.74 Дерево типа разделяй и властвуй , состоящее из n узлов, - это бинарное дерево с корнем, обозначенным n, деревом типа разделяй и властвуй , состоящим из Vn/ 2\ узлов, в одном поддереве и деревом типа разделяй и властвуй , состоящим из \ n/ 2 \ узлов, в другом. (Дерево типа разделяй и властвуй показано на рис. 5.6.) Нарисуйте дерево типа разделяй и властвуй с 11, 15, 16 и 23 узлами.

о 5.75 Докажите методом индукции, что длина внутреннего пути дерева типа разделяй и властвуй находится в пределах между n IgTV и IgTV + TV.

5.76 Дерево типа объединяй и властвуй , состоящее из 7V узлов, - это бинарное дерево с корнем, обозначенным 7V, деревом типа объединяй и властвуй , состоящим из [Л/2j узлов, в одном поддереве и Деревом типа объединяй и властвуй , состоящим из \ n/ 2] узлов, в другом (см. упражнение 5.18). Нарисуйте дерево типа объединяй и властвуй с 11, 15, 16 и 23 узлами.

5.77 Докажите методом индукции, что длина внутреннего пути дерева типа объединяй и властвуй находится в пределах между 7V IgTV и n IgTV + n.

5.78 Полное (complete) бинарное дерево - это дерево, в котором все уровни, кроме, возможно, последнего, который заполняется слева направо, заполнены, как проиллюстрировано на рис. 5.24. Докажите, что длина внутреннего пути полного дерева с n узлами лежит в пределах между 7V IgTV и 7V IgTV + n.

5.6 Обход дерева

д д д

РИСУНОК 5.24 ПОЛНЫЕ БИНАРНЫЕ ДЕРЕВЬЯ С СЕМЬЮ И ДЕСЯТЬЮ ВНУТРЕННИМИ УЗЛАМИ

Когда количество внешних узлов является степенью 2 (верхний рисунок), все внешние узлы в полном бинарном дереве располагаются на одном уровне. В противном случае (нижний рисунок) внешние узлы располагаются в двух уровнях при размещении внутренних узлов слева от внешних узлов предпоследнего уровня.

Прежде чем рассматривать алгоритмы, конструирующие бинарные деревья и деревья, рассмотрим алгоритмы для реализации наиболее общей функции обработки деревьев - обхода дерева; при наличии указателя на дерево требуется систематически обработать все узлы в дереве. В связном списке переход от одного узла к другому выполняется за счет отслеживания единственной связи; однако, в случае деревьев приходится принимать решения, поскольку может существовать несколько связей, по которым можно следовать.

Начнем рассмотрение с процесса для бинарных деревьев. В случае со связными списками имелись две основные возможности (см. программу 5.5): обработать узел, а затем следовать связи (в этом случае узлы посещались бы по порядку), или следовать связи, а затем обработать узел (в этом случае узлы посещались бы в обратном порядке). При работе с бинарными деревьями существуют две связи и, следовательно, три основных порядка возможного посещения узлов:

Прямой обход (сверху вниз), при котором мы посещаем узел, а затем левое и правое поддеревья

Поперечный обход (слева направо), при котором мы посещаем левое поддерево, затем узел, а затем правое поддерево

Обратный обход (снизу вверх), при котором мы посещаем левое и правое поддеревья, а затем узел.

Эти методы можно легко реализовать с помощью рекурсивной программы, как показано в программе 5.14, которая является непосредственным обобщением программы 5.5 обхода связного списка. Для реализации обходов в других порядках достаточно соответствующим образом переставить вызовы функций в программе 5.14. Порядок посещения узлов в примере дерева при использовании каждого из порядков обхода показан на рис. 5.26. На рис. 5.25 приведена последовательность вызовов функций, которые выполняются при вызове программы 5.14 применительно к примеру дерева из рис. 5.26,

Программа 5.14 Рекурсивный обход дерева

Эта рекурсивная функция принимает в качестве аргумента ссылку на дерево и вызывает функцию visit для каждого из узлов дерева. В приведенном виде функция реализует прямой обход; если поместить обращение к visit между рекурсивными вызовами, получится поперечный обход; а если поместить обращение к visit после рекурсивных вызовов - то обратный обход.

void traverse(link h, void visit(link)) {

if (h = 0) return; visit(h);

traverse(h->l, visit); traverse(h->r, visit);

С этими же основными рекурсивными процессами, на которых основываются различные методы обхода дерева, мы уже встречались в рекурсивных программах типа разделяй и властвуй (см. рис. 5.8 и 5.11) и в арифметических выражениях. Например, выполнение прямого обхода соответствует рисованию вначале меток на линейке, а затем выполнению рекурсивных вызовов (см. рис. 5.11); выполнение поперечного обхода соответствует перемещению самого большого диска в решении задачи о ханойских башнях между рекурсивными вызовами, которые перемещают все остальные диски; выполнение обратного обхода соответствует вычислению постфиксных выражений и т.д. Эти соответствия позволяют немедленно заглянуть внутрь механизмов, лежащих в основе обхода дерева. Например, известно, что при поперечном обходе каждый второй узел является внешним, по той же причине, по какой при решении задачи о ханойских башнях каждое второе перемещение затрагивает маленький диск.

Полезно также рассмотреть нерекурсивные реализации, в которых используется явный стек. Для простоты мы начнем с рассмотрения абстрактного стека, содержащего элементы дерева, инициализированного деревом, которое требуется обойти. Затем мы войдем в цикл, в котором выталкивается и обрабатывается верхняя запись стека, и который продолжается, пока стек не опустеет. Если вытолкнутая запись является элементом, мы посещаем его; если вытолкнутая запись - дерево, мы выполняем последовательность операций выталкивания, которая зависит от требуемого порядка:

Для прямого обхода заталкивается правое поддерево, затем левое поддерево, а затем узел.

Для поперечного обхода заталкивается правое поддерево, затем узел, а затем левое поддерево.

Для обратного обхода заталкивается узел, затем правое поддерево, а затем левое поддерево.

Нулевые деревья в стек не заталкиваются. На рис. 5.27 показано содержимое стека при использовании каждого из этих трех методов для обхода примера дерева, приведенного на рис. 5.26. Методом индукции можно легко убедиться, что для любого бинарного дерева этот метод приводит к такому же результату, как и рекурсивный метод.

traverse Е visit Е traverse D visit D traverse В visit В traverse A visit A traverse * traverse ♦ traverse С visit С traverse * traverse ♦ traverse * traverse H visit H traverse F visit F traverse * traverse G visit G traverse ♦ traverse ♦ traverse *

РИСУНОК 5.25 ВЫЗОВЫ ФУНКЦИЙ ПРЯМОГО ОБХОДА

Эта последовательность вызовов функций определяет прямой обход для примера дерева, показанного на рис. 5.26.