Бинарное дерево С++
Бинарное дерево (binary tree) - это упорядоченная древовидная динамическая структура. Каждый элемент (узел) дерева имеет не более двух элементов следующих за ним (потомков) и не более одного предыдущего (родителя). Организация данных с помощью бинарных деревьев часто позволяет значительно сократить время поиска нужного элемента. Поиск элемента в линейных структурах данных обычно осуществляется путем последовательного перебора всех элементов, присутствующих в данной структуре. Поиск по дереву не требует перебора всех элементов, поэтому занимает значительно меньше времени. Максимальное число шагов при поиске по дереву равно высоте данного дерева, т.е. количеству уровней в иерархической структуре дерева.
При работе с деревьями обычно используются рекурсивные алгоритмы. Использование рекурсивных функций менее эффективно, поскольку многократный вызов функции расходует системные ресурсы. Тем не менее, в данном случае использование рекурсивных функций является оправданным, поскольку нерекурсивные функции для работы с деревьями гораздо сложнее и для написания, и для восприятия кода программы.
- Самый главный принцип бинарного дерева заключается в том, что для каждого узла выполняется правило: в левой ветке содержатся только те ключи, которые имеют значения, меньшие, чем значение данного узла. В правой же ветке содержатся ключи, имеющие значения, большие, чем значение данного узла.
- Каждый узел может иметь два, одного или ни одного потомка.
- Лист - узел, не имеющий потомков.
- Узел является родительским для своих потомков и дочерним для своего предка.
- Левый потомок - дочерний узел слева от текущего узла.
- Правый потомок - дочерний узел справа от текущего узла.
- Корень - основной узел, не имеющий родителей.
- Каждый узел состоит из четырех частей:
- Значение.
- Указатель на родителя.
- Указатель на левого потомка.
- Указатель на правого потомка.
Читайте также:
Крупнейшая в Европе школа английского языка
Промокоды, акции и подарки, чтобы Ваше обучение было не только интересным, но и выгодным. Закажите пробный урок уже сейчас!
skyeng.ru
Онлайн школа английского языка
Английский по скайпу от 680р за урок, без заучивания правил. Эффективно! Удобно! Выгодно! Начните обучение прямо сейчас.
melene.ru
Школа английского языка по Skype
Персональные занятия по разумным ценам. Бесплатные ресурсы для студентов: разговорные клубы, блог, вебинары, книги, тест на определение уровня английского. Пробный урок бесплатно!
englex.ru