Дерево – структура данных, представляющая собой древовидную структуру в виде набора связанных узлов.
Бинарное дерево — это конечное множество элементов, которое либо пусто, либо содержит элемент (корень), связанный с двумя различными бинарными деревьями, называемыми левым и правым поддеревьями. Каждый элемент бинарного дерева называется узлом. Связи между узлами дерева называются его ветвями.
Способ представления бинарного дерева:
- A - корень дерева
- В - корень левого поддерева
- С - корень правого поддерева
Корень дерева расположен на уровне с минимальным значением.
Узел 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 - постфиксная форма.
Реализация дерева
Узел дерева можно описать как структуру:
2
3
4
5
int field; // поле данных
struct tnode *left; // левый потомок
struct tnode *right; // правый потомок
};
При этом обход дерева в префиксной форме будет иметь вид
2
3
4
5
6
7
if (tree!=NULL) { //Пока не встретится пустой узел
cout << tree->field; //Отображаем корень дерева
treeprint(tree->left); //Рекурсивная функция для левого поддерева
treeprint(tree->right); //Рекурсивная функция для правого поддерева
}
}
Обход дерева в инфиксной форме будет иметь вид
2
3
4
5
6
7
if (tree!=NULL) { //Пока не встретится пустой узел
treeprint(tree->left); //Рекурсивная функция для левого поддерева
cout << tree->field; //Отображаем корень дерева
treeprint(tree->right); //Рекурсивная функция для правого поддерева
}
}
Обход дерева в постфиксной форме будет иметь вид
2
3
4
5
6
7
if (tree!=NULL) { //Пока не встретится пустой узел
treeprint(tree->left); //Рекурсивная функция для левого поддерева
treeprint(tree->right); //Рекурсивная функция для правого поддерева
cout << tree->field; //Отображаем корень дерева
}
}
Бинарное (двоичное) дерево поиска – это бинарное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):
- оба поддерева – левое и правое, являются двоичными деревьями поиска;
- у всех узлов левого поддерева произвольного узла X значения ключей данных меньше, чем значение ключа данных самого узла X;
- у всех узлов правого поддерева произвольного узла X значения ключей данных не меньше, чем значение ключа данных узла X.
Данные в каждом узле должны обладать ключами, на которых определена операция сравнения меньше.
Как правило, информация, представляющая каждый узел, является записью, а не единственным полем данных.
Для составления бинарного дерева поиска рассмотрим функцию добавления узла в дерево.
Добавление узлов в дерево
2
3
4
5
6
7
8
9
10
11
12
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);
}
Удаление поддерева
2
3
4
5
6
7
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
При этом дерево будет иметь следующий вид
Пример реализации
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
//#include <cstddef>
#define MAXWORD 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[MAXWORD];
root = NULL;
do {
scanf_s("%s", word, MAXWORD);
if (isalpha(word[0]))
root = addtree(root, word);
} while (word[0] != '0'); // условие выхода – ввод символа '0'
treeprint(root);
freemem(root);
getchar();
getchar();
return 0;
}
Результат выполнения
Здравствуйте, подскажите пожалуйста, если у каждого элемента есть ключ, который является строкой, а не числом и содержит в себе информацию тоже в виде строки, как мы понимаем, где правое, а где левое поддерево
и как в примере
now is the time for all good men to come to the aid of their party
было определено, где правое, а где левое поддерево
Строки тоже можно сортировать по возрастанию, то есть по алфавиту
Добрый день. Можете, пожалуйста, подсказать как удалить ветвь со всеми ее потомками? (я ввожу ключ и если он совпадает с одной из ветвей дерева, то удаляется эта ветвь и ее потомки)
Функция удаления поддерева именно это и делает.
если есть возможность можете, пожалуйста, указать на мои ошибки?
Не доходит как связать задаваемый мною ключ с функцией (все время получаются ошибки)
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
int info;
Tree* Left, *Right;
int *keyfordel;
} *Root; // Root – указатель на корень
void delforkey(Tree*);
void delbykey(Tree* Root) { // Ф-ция удаления из дерева ветви с вершиной по ключу
if (Root != NULL) {
delforkey(Root->Left);
delforkey(Root->Right);
free(Root->keyfordel);
free(Root);
}
}
void main() {
struct Tree *Root; int key;
while (1)
{
switch (menu())
{
case 1: …
break;
case 2: …
break;
case 3: …
break;
case 4: …
break;
case 5: …
break;
case 6:
printf("удалить из дерева ветвь с вершиной: ");
scanf_s("%d", &key);
delbykey(Root);
break;
case 7: Del_All(Root);
return;
}
}
}
*в остальных кейсах меню находятся рабочие функции для дерева (создание, вывод, удаление одного элемента, поиск и др)
1. Как называется функция? delfoekey() или delbykey()?
2. Каким образом введённое значение ключа key в case 6 попадает в функцию? Туда идёт корень.
3. В структуре keyfordel — это указатель, и я не вижу выделения памяти под него. Возможно, оно осуществляется при добавлении элемента, просто функция здесь не показана.
Извините, можете, пожалуйста, объяснить как по вводимому мной в main ключу удалить поддерево?
Я попыталась поправить код (1 исправила, 3 тоже, но со вторым проблемы: не знаю как корректно впихнуть key в функцию delbykey)
Сравнить введённый ключ с ключом узла, и если они совпали, то удалить поддерево с корнем в этом узле.
Здравствуйте, а как делать обход дерева в ширину, то есть печатать дерево уровнями, сначала корень, потом его потомки, и тд.
Префиксный обход
В 17 строчке почему именно sizeof(struct tnode)?:
2
/*17*/ p = (struct tnode*)malloc(sizeof(struct tnode));
Память выделяется для структуры, и указывается ее размер
Не совсем понятно, на каком этапе происходит освобождение памяти, выделенной в процедуре p->word = strdup(w)?
Спасибо за замечание, поправила код
Приветствую.
А не подскажите в какой программе такие деревья можно нарисовать
Программа Trees.exe позволяет визуально создавать бинарные деревья, сохранять их и работать с ними.
Скачать можно тут:
https://soft.softodrom.ru/ap/Trees-Portable-p19987
или
http://fish1821.narod.ru/Programs.html
нет там такой проги!
Напишите статью не про бинарные деревья. Например про структуру в которой удобно хранить файловую систему.
Для большей "чистоты" можно было бы функцию удаления дерева сделать возвращающей значение — "симметрично" функции добавления элемента:
2
3
4
/* Весь основной код */
return NULL;
}
Это чтобы после выполнения алгоритма получить "чистый" root, равный NULL, а не бросать его неопределенным. С одной стороны, это вроде как лишнее, но если посмотреть с точки зрения логики использования — на вход алгоритма пришел root, равный NULL, и на выходе было бы полезно иметь такой же root, равный NULL. При этом его повторное использование становится органичным.