Здавалка
Главная | Обратная связь

Комментарии к изображению дерева. Терминология.



  1. Самый главный принцип бинарного дерева заключается в том, что для каждого узла выполняется правило: в левой ветке содержатся только те ключи, которые имеют значения, меньшие, чем значение данного узла. В правой же ветке содержатся ключи, имеющие значения, большие, чем значение данного узла.
  2. Каждый узел может иметь два, одного или ни одного потомка.
  3. Лист - узел, не имеющий потомков.
  4. Узел является родительским для своих потомков и дочерним для своего предка.
  5. Левый потомок - дочерний узел слева от текущего узла.
  6. Правый потомок - дочерний узел справа от текущего узла.
  7. Корень - основной узел, не имеющий родителей.
  8. Каждый узел состоит из четырех частей:
    • Значение.
    • Указатель на родителя.
    • Указатель на левого потомка.
    • Указатель на правого потомка.

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

Организация работы с деревом.

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

  • x - вершина бинарного дерева
  • left[x] - левое поддерево
  • right[x] - правое поддерево
  • key[x] - ключ
  • p[x] - родитель вершины

Обход всего дерева.

Печать(x)

Начало

  1. если x не равен NULL
  2. тогда Печать(left[x])
  3. напечатать key[x]
  4. Печать(right[x])

Конец

Поиск значения.

Поиск(x,k)

Начало

  1. Пока x не равен NULL и k не равно key[x]
  2. Начало
  3. если k меньше key[x]
  4. тогда x равно left[x]
  5. иначе x равно right[x]
  6. Конец
  7. Вернуть x

Конец

Нахождение минимума и максимума.

Минимум(x)

Начало

  1. Пока left[x] не равен NULL
  2. Начало
  3. x=left[x]
  4. Конец
  5. Вернуть x

Конец

Максимум(x)

Начало

  1. Пока right[x] не равен NULL
  2. Начало
  3. x=right[x]
  4. Конец
  5. Вернуть x

Конец







©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.