Бинарное дерево

Создание бинарного дерева.
Рассмотрим рекурсивный алгоритм создания бинарного дерева с заранее заданным количеством узлов n. Данный алгоритм позволяет создать симметричное бинарное дерево с минимальной, для заданного количества узлов, глубиной. На каждом шагу рекурсии количество узлов в левом и правом поддереве определяется по формулам: nleft = n / 2; nright = n-nleft-1.
Рекурсивный алгоритм создания бинарного дерева (функция CreateTree (...)).
1. Проверить условие остановки рекурсии: количество узлов равна нулю. В этом случае указатель на узел также нужно установить NULL (* pNode = NULL, * pNode - указатель на текущий узел).
2. Иначе: создать новый узел дерева: (* pNode = new Node; ).
3. Заполнить информационное поле нового узла: ((* pNode) -> data = data; ).
4. Установить указатели нового узла на левое и правое поддерево как NULL: ((* pNode) -> left = (* pNode) -> right = NULL; ).
5. Рекурсивно создать левое поддерево данного узла с количеством узлов (n_left = n / 2).
6. Рекурсивно создать правое поддерево данного узла с количеством узлов (n_right = n - n_left - 1).
Замечания.
Функция, реализующая данный алгоритм должна содержать как параметры указатель на левое / правое поддерево и количество узлов в левом / правом поддереве. Начальными значениями этих параметров есть указатель на корень дерева и общее количество узлов в нем.
Отображение бинарного дерева.
Рассмотрим теперь рекурсивный алгоритм отображения только что созданного бинарного дерева. Поддерево уровня L выводится так: сначала рекурсивно отображается левое поддерево, затем корень поддерева уровня L, перед которым нужно вывести L пробелов, затем отображается правое поддерево.
Рекурсивный алгоритм отображения дерева (функция ShowTree (...)).
Пока не достигнуто листьев (pNode! = NULL):
1. Вывести левое поддерево.
2. Вывести (в цикле) L пробелов и данные узла L-го уровня (pNode> data; ) /
3 Вывести правое поддерево.
Замечания.
Функция, реализующая данный алгоритм должна содержать как параметры указатель на левое / правое поддерево и номер уровня (если рассматривается L-й уровень, то функция рекурсивно вызывается для уровня L + 1). Начальными значениями этих параметров есть указатель на корень дерева и нулевой уровень.
Обход дерева.
Задача обхода дерева заключается в однократном посещении всех узлов дерева. С другой стороны эту задачу можно рассматривать как задания порядке (упорядочение) на множестве вершин дерева. Существует три рекурсивных алгоритмы обхода дерева: обход в прямом порядке (сверху вниз) обход в обратном порядке (снизу вверх) обход во внутреннем порядке (слева направо).
Рекурсивный алгоритм обхода дерева в прямом порядке (функция PrefixOrder (...)).
Пока не достигнуто листьев (pNode! = NULL):
1. Обработать данные (вывести на экран) в узле;
2. Осуществить (рекурсивно) обход левого поддерева;
3. Осуществить (рекурсивно) обход правого поддерева;
Рекурсивный алгоритм обхода дерева в обратном порядке (функция PostfixOrder (...)).
Пока не достигнуто листьев (pNode! = NULL):
1. Осуществить (рекурсивно) обход левого поддерева;
2. Осуществить (рекурсивно) обход правого поддерева;
3. Обработать данные (вывести на экран) в узле;
Рекурсивный алгоритм обхода дерева во внутреннем порядке (функция InfixOrder (...)).
Пока не достигнуто листьев (pNode! = NULL):
1. Осуществить (рекурсивно) обход левого поддерева;
2. Обработать данные (вывести на экран) в узле;
3. Осуществить (рекурсивно) обход правого поддерева;
Замечания.
Одним из применений обхода деревьев является построение различных форм записи выражений (арифметических, логических и т.д.). В частности запись, полученный при обходе в прямом порядке называется префиксным или польским, запись, полученный при обходе в обратном порядке - Постфиксная или обратным польским, а запись, полученный при обходе во внутреннем порядке - инфиксное.