2. Двоичные деревья
Особенно важную роль играют упорядоченные деревья второй степени. Их называют двоичными или бинарными деревьями. Определим двоичное дерево как конечное множество элементов – узлов, которое или пусто, или состоит из корня и двух непересекающихся двоичных деревьев, называемых левым и правым поддеревьями данного корня. Заметим, что двоичное дерево не является частным случаем дерева, хотя эти два понятия связаны между собой. Основные отличия между ними: 1) Дерево никогда не бывает пустым, т.е. имеет, по меньшей мере, один узел, а двоичное дерево может быть пустым. 2) Двоичное дерево — упорядоченное дерево, т.е. делается различие между левым и правым поддеревом, даже в том случае, когда узел имеет лишь одного потомка. В графическом изображении дерева (рисунок 4) “наклон” ветвей важен. Реализация таких рекурсивных структур, как двоичные деревья, приводит к использованию ссылок (указателей). Ссылки на пустые деревья будут обозначаться nil. Из определения двоичных деревьев следует естественный способ их описания ( и представления в компьютере ) : для этого достаточно иметь две связи L и R в каждом узле и переменную связи T, которая является указателем на это дерево. Если дерево пусто, то T = nil ; в противном случае T — адрес корня этого дерева, а L и R — указатели соответственно на левое и правое поддеревья этого корня. На языке Паскаль узлы бинарного дерева описываются как записи с одним или несколькими информационными полями и двумя полями – указателями. Если Elem — тип информационной части узлов дерева, то компоненты дерева ( узел и ссылка на узел ) имеют такие типы: type Tree = ^Node; < указатель на узел >Node = record < узел дерева >
Inf : Elem;
L, R : Tree end; Таким образом, дерево на рисунке 4 б) можно представить так, как на рисунке 5. Далее будем иметь дело только с двоичными деревьями, поэтому термин “дерево” будет означать двоичное дерево.
3. Основные операции с двоичными деревьями
3.1. Обход дерева Наиболее распространенная задача обработки древовидных структур – выполнение некоторой определенной операции над каждым элементом дерева. При этом происходит “посещение” всех вершин, т.е. обход дерева. При обходе каждый узел проходится, по меньшей мере, один раз, а, вообще говоря, три раза. Полное прохождение дерева дает линейную расстановку узлов. Если, обходя дерево, обрабатывать вершины при первой встрече, то ( см. рис. 4 б) ) получим последовательность A, B, D, E, C, F ; если при второй встрече, то получим D, B, E, A, C, F ; если при третьей встрече, то получим D, E, B, F, C, A. Эти три способа обхода называются соответственно – обходом сверху вниз (в прямом порядке, префиксным обходом, preorder); – обходом слева направо (в обратном порядке, инфиксным обходом, inorder); – обходом снизу вверх (в концевом порядке, постфиксным обходом, postorder или endorder). Способы прохождения деревьев определяются рекурсивно. Если дерево пусто, то никаких действий не выполняется, в противном случае обход выполняется в три этапа
| Префиксный обход | Инфиксный обход |
| Обработать узел | Пройти левое поддерево |
| Пройти левое поддерево | Обработать узел |
| Пройти правое поддерево | Пройти правое поддерево |
Постфиксный обход Пройти левое поддерево Пройти правое поддерево Обработать узел Обход слева направо (инфиксный обход) часто используется при сортировке (см. раздел 4 ). Префиксный и постфиксный способы обхода дерева играют важную роль при анализе текстов на языках программирования. Все три метода легко представляются как рекурсивные процедуры. Пример 3.1. Префиксный обход дерева : procedure PreOrder(T : Tree); begin if T <> nil then begin < операция обработки узла дерева , например, writeln( T^.inf );> PreOrder (T^.L); PreOrder (T^.R) end end; PreOrder > Пример 3.2. Инфиксный обход дерева : procedure InOrder(T : Tree); begin if T <> nil then begin InOrder (T^.L); < операция обработки узла дерева , например, writeln( T^.inf );> InOrder (T^.R) end end; Пример 3.3. Постфиксный обход дерева : procedure PostOrder(T : Tree); begin if T <> nil then begin PostOrder (T^.L); PostOrder (T^.R) < операция обработки узла дерева , например, writeln( T^.inf );> end end; PostOrder > Замечание. Ссылка T передается как параметр — значение, т.е. в процедуре используется ее локальная копия. При реализации нерекурсивных процедур обхода дерева обычно используют вспомогательный стек и операции работы с ним: – очистить стек (создать пустой стек); – проверить, является ли стек пустым; – добавить в стек элемент; – извлечь элемент из стека. В стеке запоминаются ссылки на вершины (поддеревья), обработка которых временно откладывается. Пример 3.4. Описать нерекурсивную процедуру префиксного обхода дерева. Описание вспомогательного стека : type Stack = ^Rec; Rec = record
Источник
Дерево
Дерево – структура данных, представляющая собой древовидную структуру в виде набора связанных узлов.
Бинарное дерево — это конечное множество элементов, которое либо пусто, либо содержит элемент ( корень ), связанный с двумя различными бинарными деревьями, называемыми левым и правым поддеревьями . Каждый элемент бинарного дерева называется узлом . Связи между узлами дерева называются его ветвями .
Способ представления бинарного дерева:
Корень дерева расположен на уровне с минимальным значением.
Узел D , который находится непосредственно под узлом B , называется потомком B . Если D находится на уровне i , то B – на уровне i-1 . Узел B называется предком D .
Максимальный уровень какого-либо элемента дерева называется его глубиной или высотой .
Если элемент не имеет потомков, он называется листом или терминальным узлом дерева.
Остальные элементы – внутренние узлы (узлы ветвления).
Число потомков внутреннего узла называется его степенью . Максимальная степень всех узлов есть степень дерева.
Число ветвей, которое нужно пройти от корня к узлу x , называется длиной пути к x . Корень имеет длину пути равную 0 ; узел на уровне i имеет длину пути равную i .
Бинарное дерево применяется в тех случаях, когда в каждой точке вычислительного процесса должно быть принято одно из двух возможных решений.
Имеется много задач, которые можно выполнять на дереве.
Распространенная задача — выполнение заданной операции p с каждым элементом дерева. Здесь p рассматривается как параметр более общей задачи посещения всех узлов или задачи обхода дерева.
Если рассматривать задачу как единый последовательный процесс, то отдельные узлы посещаются в определенном порядке и могут считаться расположенными линейно.
Способы обхода дерева
Пусть имеем дерево, где A — корень, B и C — левое и правое поддеревья.
Существует три способа обхода дерева:
- Обход дерева сверху вниз (в прямом порядке): A, B, C — префиксная форма.
- Обход дерева в симметричном порядке (слева направо): B, A, C — инфиксная форма.
- Обход дерева в обратном порядке (снизу вверх): B, C, A — постфиксная форма.
Реализация дерева
Узел дерева можно описать как структуру:
struct tnode <
int field; // поле данных
struct tnode *left; // левый потомок
struct tnode *right; // правый потомок
>;
При этом обход дерева в префиксной форме будет иметь вид
void treeprint(tnode *tree) <
if (tree!= NULL ) < //Пока не встретится пустой узел
cout field; //Отображаем корень дерева
treeprint(tree->left); //Рекурсивная функция для левого поддерева
treeprint(tree->right); //Рекурсивная функция для правого поддерева
>
>
Обход дерева в инфиксной форме будет иметь вид
void treeprint(tnode *tree) <
if (tree!= NULL ) < //Пока не встретится пустой узел
treeprint(tree->left); //Рекурсивная функция для левого поддерева
cout field; //Отображаем корень дерева
treeprint(tree->right); //Рекурсивная функция для правого поддерева
>
>
Обход дерева в постфиксной форме будет иметь вид
void treeprint(tnode *tree) <
if (tree!= NULL ) < //Пока не встретится пустой узел
treeprint(tree->left); //Рекурсивная функция для левого поддерева
treeprint(tree->right); //Рекурсивная функция для правого поддерева
cout field; //Отображаем корень дерева
>
>
Бинарное (двоичное) дерево поиска – это бинарное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):
- оба поддерева – левое и правое, являются двоичными деревьями поиска;
- у всех узлов левого поддерева произвольного узла X значения ключей данных меньше, чем значение ключа данных самого узла X ;
- у всех узлов правого поддерева произвольного узла X значения ключей данных не меньше, чем значение ключа данных узла X .
Данные в каждом узле должны обладать ключами, на которых определена операция сравнения меньше.
Как правило, информация, представляющая каждый узел, является записью, а не единственным полем данных.
Для составления бинарного дерева поиска рассмотрим функцию добавления узла в дерево.
Добавление узлов в дерево
struct tnode * addnode( int x, tnode *tree) <
if (tree == NULL ) < // Если дерева нет, то формируем корень
tree = new tnode; // память под узел
tree->field = x; // поле данных
tree->left = NULL ;
tree->right = NULL ; // ветви инициализируем пустотой
> else if (x < tree->field) // условие добавление левого потомка
tree->left = addnode(x,tree->left);
else // условие добавление правого потомка
tree->right = addnode(x,tree->right);
return (tree);
>
Удаление поддерева
void freemem(tnode *tree) <
if (tree!= NULL ) <
freemem(tree->left);
freemem(tree->right);
delete tree;
>
>
Пример Написать программу, подсчитывающую частоту встречаемости слов входного потока.
Поскольку список слов заранее не известен, мы не можем предварительно упорядочить его. Неразумно пользоваться линейным поиском каждого полученного слова, чтобы определять, встречалось оно ранее или нет, т.к. в этом случае программа работает слишком медленно.
Один из способов — постоянно поддерживать упорядоченность уже полученных слов, помещая каждое новое слово в такое место, чтобы не нарушалась имеющаяся упорядоченность. Воспользуемся бинарным деревом.
В дереве каждый узел содержит:
- указатель на текст слова;
- счетчик числа встречаемости;
- указатель на левого потомка;
- указатель на правого потомка.
Рассмотрим выполнение программы на примере фразы
now is the time for all good men to come to the aid of their party
При этом дерево будет иметь следующий вид
#include
#include
#include
#include
//#include
#define MAX WORD 100
struct tnode < // узел дерева
char * word; // указатель на строку (слово)
int count; // число вхождений
struct tnode* left; // левый потомок
struct tnode* right; // правый потомок
>;
// Функция добавления узла к дереву
struct tnode* addtree( struct tnode* p, char * w) int cond;
if (p == NULL ) p = ( struct tnode*)malloc( sizeof ( struct tnode));
p->word = _strdup(w);
p->count = 1;
p->left = p->right = NULL ;
>
else if ((cond = strcmp(w, p->word)) == 0)
p->count++;
else if (cond < 0)
p->left = addtree(p->left, w);
else
p->right = addtree(p->right, w);
return p;
>
// Функция удаления поддерева
void freemem(tnode* tree) if (tree != NULL ) freemem(tree->left);
freemem(tree->right);
free(tree->word);
free(tree);
>
>
// Функция вывода дерева
void treeprint( struct tnode* p) if (p != NULL ) treeprint(p->left);
printf( «%d %s\n» , p->count, p->word);
treeprint(p->right);
>
>
int main() struct tnode* root;
char word[MAX WORD ];
root = NULL ;
do scanf_s( «%s» , word, MAX WORD );
if (isalpha(word[0]))
root = addtree(root, word);
> while (word[0] != ‘0’ ); // условие выхода – ввод символа ‘0’
treeprint(root);
freemem(root);
getchar();
getchar();
return 0;
>
Результат выполнения
Комментариев к записи: 19
Источник