Комментарии к изображению дерева. Терминология.
- Самый главный принцип бинарного дерева заключается в том, что для каждого узла выполняется правило: в левой ветке содержатся только те ключи, которые имеют значения, меньшие, чем значение данного узла. В правой же ветке содержатся ключи, имеющие значения, большие, чем значение данного узла.
- Каждый узел может иметь два, одного или ни одного потомка.
- Лист - узел, не имеющий потомков.
- Узел является родительским для своих потомков и дочерним для своего предка.
- Левый потомок - дочерний узел слева от текущего узла.
- Правый потомок - дочерний узел справа от текущего узла.
- Корень - основной узел, не имеющий родителей.
- Каждый узел состоит из четырех частей:
- Значение.
- Указатель на родителя.
- Указатель на левого потомка.
- Указатель на правого потомка.
Примечание:Бинарное дерево является рекурсивной структурой, поскольку каждое его поддерево само является бинарным деревом и, следовательно, каждый его узел в свою очередь является корнем самостоятельного дерева.
Организация работы с деревом.
При работе с деревьями обычно используются рекурсивные алгоритмы. Использование рекурсивных функций менее эффективно, поскольку многократный вызов функции расходует системные ресурсы. Тем не менее, в данном случае использование рекурсивных функций является оправданным, поскольку нерекурсивные функции для работы с деревьями гораздо сложнее и для написания, и для восприятия кода программы. Здесь мы приведем схематичные алгоритмы работы с деревом. А, осмысленный, практический пример смотрите в следующем разделе урока. Вот некоторые значения, которые мы будем использовать в схемах:
- x - вершина бинарного дерева
- left[x] - левое поддерево
- right[x] - правое поддерево
- key[x] - ключ
- p[x] - родитель вершины
Обход всего дерева.
Печать(x)
Начало
- если x не равен NULL
- тогда Печать(left[x])
- напечатать key[x]
- Печать(right[x])
Конец
Поиск значения.
Поиск(x,k)
Начало
- Пока x не равен NULL и k не равно key[x]
- Начало
- если k меньше key[x]
- тогда x равно left[x]
- иначе x равно right[x]
- Конец
- Вернуть x
Конец
Нахождение минимума и максимума.
Минимум(x)
Начало
- Пока left[x] не равен NULL
- Начало
- x=left[x]
- Конец
- Вернуть x
Конец
Максимум(x)
Начало
- Пока right[x] не равен NULL
- Начало
- x=right[x]
- Конец
- Вернуть x
Конец
©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.