История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Топ:
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
История развития методов оптимизации: теорема Куна-Таккера, метод Лагранжа, роль выпуклости в оптимизации...
Интересное:
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Искусственное повышение поверхности территории: Варианты искусственного повышения поверхности территории необходимо выбирать на основе анализа следующих характеристик защищаемой территории...
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Дисциплины:
2017-06-12 | 701 |
5.00
из
|
Заказать работу |
|
|
Бинарное (двоичное) дерево (binary tree) - это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значение данного узла.
Бинарное дерево является рекурсивной структурой, поскольку каждое его поддерево само является бинарным деревом и, следовательно, каждый его узел в свою очередь является корнем дерева.
Узел дерева, не имеющий потомков, называется листом.
Схематичное изображение бинарного дерева
Бинарное дерево может представлять собой пустое множество.
Бинарное дерево может выродиться в список
Построение бинарного дерева
Реализация бинарного дерева: При реализации дерева с помощью динамических переменных каждый элемент дерева, помимо информационной части, содержит два указателя: на левое и правое поддеревья этого элемента. Переменная ссылочного типа fRoot указывает на корневой узел дерева. Если какой-либо узел дерева не имеет левого или правого поддерева, то соответствующий указатель этого узла содержит значение nil.
Сначала мы должны определить структуру для создания корня и узлов дерева:
template<class T>
struct TNode {
T value;
TNode *pleft, *pright;
//constructor
TNode() {
pleft = pright = 0;
}};
Здесь поля pleft и pright - это указатели на потомков данного узла, а поле value предназначено для хранения информации.
Теперь мы можем написать рекурсивную функцию, которая будет вызываться при создании дерева:
template<class T>
void makeTree(TNode<T>** pp, T x) {
if(!(*pp)) {
TNode<T>* p = new TNode<T>();
p->value = x;
*pp = p;
}
else {
if((*pp)->value > x)
|
makeTree(&((*pp)->pleft), x);
else
makeTree(&((*pp)->pright), x);
}}
Эта функция добавляет элемент x к дереву, учитывая величину x. При этом создается новый узел дерева.
Обход дерева
Функция, выполняющая обход дерева, позволяет перебрать все элементы, содержащиеся в дереве.
В приведенной ниже реализации функция обхода дерева будет просто выводить на экран значение поля value каждого узла дерева (включая его корень):
template<class T>
void walkTree(TNode<T>* p) {
if(p) {
walkTree(p->pleft);
cout << p->value << ' ';
walkTree(p->pright);
}}
При работе с деревьями обычно используются рекурсивные алгоритмы. Использование рекурсивных функций менее эффективно, поскольку многократный вызов функции расходует системные ресурсы. Тем не менее, в данном случае использование рекурсивных функций является оправданным, поскольку нерекурсивные функции для работы с деревьями гораздо сложнее и для написания, и для восприятия кода программы.
Например, нерекурсивная функция для обхода дерева может выглядеть так:
template<class T>
void walkNotRec(TNode<T>* tree) {
if (tree) {
TNode<T> temp;
TNode<T>* ptemp = &temp;
TNode<T>* p = ptemp, *c = tree, *w;
while (c!= ptemp) {
cout << c->value;
w = c->pleft;
c->pleft = c->pright;
if(c == p)
c->pright = 0;
else
c->pright = p;
p = c;
if (w) c = w;
}
}}
Организация данных с помощью бинарных деревьев часто позволяет значительно сократить время поиска нужного элемента. Поиск элемента в линейных структурах данных обычно осуществляется путем последовательного перебора всех элементов, присутствующих в данной структуре. Поиск по дереву не требует перебора всех элементов, поэтому занимает значительно меньше времени. Максимальное число шагов при поиске по дереву равно высоте данного дерева, т.е. количеству уровней в иерархической структуре дерева.
|
|
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!