Операции над бинарным деревом

Операции над бинарным деревом

Над бинарным деревом могут быть выполнены операции:

• обход узлов бинарного дерева в определенном порядке;
• добавление некоторого поддерева в дерево;
• исключение некоторого поддерева из дерева;
• примитивные операции над узлами дерева.

Обход (прохождение) дереваиспользуется для систематического последовательного просмотра узлов дерева. Эта операция может быть использована для контроля информации, хранящейся в древовидной структуре, а также как составная часть для выполнения других операций над деревом. Рекурсивная процедура обхода дерева включает в себя следующие шаги: 1) обработка (просмотр) корня дерева или поддерева; 2) обход левого поддерева обработанного корня; 3) обход правого поддерева обработанного корня; Различный порядок выполнения перечисленных выше шагов определяет три процедуры обхода бинарного дерева: 1) обход сверху вниз– сначала обрабатывается корень, затем обходится его левое, затем правое поддеревья (операцияUpDownRevision); 2) обход слева направо– сначала обходится левое поддерево корня, затем обрабатывается корень, затем обходится его правое поддерево (операцияLeftRightRevision); 3) обход снизу вверх– обходится левое поддерево корня, затем правое, затем обрабатывается корень (операцияDownUpRevision). При обходе каждого из приведённых ниже бинарных деревьев получим по три упорядоченные последовательности: (а)(б)обходдерево (а)дерево (б) сверху вниз ABDEGCFHI+a/bc–def(префиксная запись) слева направо DBGEACHFIa+b/cd–ef(инфиксная без скобок) снизу вверх DGEBHIFCAabc/+def–(постфиксная запись) Добавление некоторого поддерева в дерево. Для выполнения этой операции должны быть заданы: включаемое поддерево и узел исходного дерева, к которому поддерево подключается в качестве ветви. Поскольку бинарное дерево является упорядоченным, то должно быть указание на то, в качестве какой ветви (левой или правой) заданного узла должно быть подключено поддерево. Целесообразно разбить эту операцию на две: включение поддерева в качестве левой ветви заданного узла (AddLeft) и включение в качестве правой ветви заданного узла (AddRight). Ветви, в которые осуществляется включение, должны быть пустыми. Исключение некоторого поддерева из деревафактически представляет собой две операции: исключение поддерева из левой ветви заданного узла исходного дерева (DeleteLeft) и исключение поддерева из его правой ветви (DeleteRight). Операция возвращает адрес исключенного поддерева. Примитивные операциинад узлами бинарного дерева могут быть следующими.Addr(v) возвращает адрес узла со значениемv. Еслиp– указатель на узелNodeбинарного дерева, то операцияValue(p)возвращает значение узлаNode. ОперацииLeft(p),Right(p),Father(p),Brother(p)возвращают соответственно указатели на левого сына, правого сына, отца и брата узлаNode. ОперацииIsLeft(p)иIsRight(p)возвращают значение «истина», еслиNodeявляется соответственно левым илиправым сыном некоторого узла дерева, и значение «ложь» – в противном случае. Дополнительно могут быть определены следующие операции: Create– создание пустого дерева,Clear– удаление всех узлов дерева,WriteTo(f) – вывод дерева в файлfс помощью отступов,NodesQuantity– определение числа узлов дерева.

Для продолжения скачивания необходимо пройти капчу:

Источник

Дерево

Дерево – структура данных, представляющая собой древовидную структуру в виде набора связанных узлов.

Бинарное дерево — это конечное множество элементов, которое либо пусто, либо содержит элемент ( корень ), связанный с двумя различными бинарными деревьями, называемыми левым и правым поддеревьями . Каждый элемент бинарного дерева называется узлом . Связи между узлами дерева называются его ветвями .

Способ представления бинарного дерева:

Корень дерева расположен на уровне с минимальным значением.

Узел 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

Источник

Операции над бинарным деревом

Над бинарным деревом могут быть выполнены операции:

• обход узлов бинарного дерева в определенном порядке;
• добавление некоторого поддерева в дерево;
• исключение некоторого поддерева из дерева;
• примитивные операции над узлами дерева.

Обход (прохождение) дерева используется для систематического последовательного просмотра узлов дерева. Эта операция может быть использована для контроля информации, хранящейся в древовидной структуре, а также как составная часть для выполнения других операций над деревом. Рекурсивная процедура обхода дерева включает в себя следующие шаги: 1) обработка (просмотр) корня дерева или поддерева; 2) обход левого поддерева обработанного корня; 3) обход правого поддерева обработанного корня; Различный порядок выполнения перечисленных выше шагов определяет три процедуры обхода бинарного дерева: 1) обход сверху вниз – сначала обрабатывается корень, затем обходится его левое, затем правое поддеревья (операция UpDownRevision); 2) обход слева направо – сначала обходится левое поддерево корня, затем обрабатывается корень, затем обходится его правое поддерево (операция LeftRightRevision); 3) обход снизу вверх – обходится левое поддерево корня, затем правое, затем обрабатывается корень (операция DownUpRevision). При обходе каждого из приведённых ниже бинарных деревьев получим по три упорядоченные последовательности: (а)(б)обходдерево (а)дерево (б) сверху вниз ABDEGCFHI +a/bc–def (префиксная запись) слева направо DBGEACHFIa+b/cd–ef (инфиксная без скобок) снизу вверх DGEBHIFCAabc/+def– (постфиксная запись) Добавление некоторого поддерева в дерево. Для выполнения этой операции должны быть заданы: включаемое поддерево и узел исходного дерева, к которому поддерево подключается в качестве ветви. Поскольку бинарное дерево является упорядоченным, то должно быть указание на то, в качестве какой ветви (левой или правой) заданного узла должно быть подключено поддерево. Целесообразно разбить эту операцию на две: включение поддерева в качестве левой ветви заданного узла (AddLeft) и включение в качестве правой ветви заданного узла (AddRight). Ветви, в которые осуществляется включение, должны быть пустыми. Исключение некоторого поддерева из дерева фактически представляет собой две операции: исключение поддерева из левой ветви заданного узла исходного дерева (DeleteLeft) и исключение поддерева из его правой ветви (DeleteRight). Операция возвращает адрес исключенного поддерева. Примитивные операции над узлами бинарного дерева могут быть следующими. Addr(v) возвращает адрес узла со значением v. Если p – указатель на узел Node бинарного дерева, то операция Value(p) возвращает значение узла Node. Операции Left(p), Right(p), Father(p), Brother(p) возвращают соответственно указатели на левого сына, правого сына, отца и брата узла Node. Операции IsLeft(p) и IsRight(p) возвращают значение «истина», если Node является соответственно левым или правым сыном некоторого узла дерева, и значение «ложь» – в противном случае. Дополнительно могут быть определены следующие операции: Create – создание пустого дерева, Clear – удаление всех узлов дерева, WriteTo(f) – вывод дерева в файл f с помощью отступов, NodesQuantity – определение числа узлов дерева.

Для продолжения скачивания необходимо пройти капчу:

Источник