Деревья бывают бинарные и

Определение и свойства деревьев.

Деревом называется произвольный связный граф без циклов. Деревья обладают следующими свойствами:

любые две вершины соединены единственной простои цепью

количество ребер на единицу меньше количества вершин

при удалении любого ребра дерево становится не связным графом

при добавлении к дереву любого ребра в дереве появляется ровно один простой цикл.

Фактически дерево можно получить из любого связного графа

Утверждение: любой связный граф содержит остовный подграф который является деревом. Этот подграф называется остовыным деревом.

Специальные виды деревьев

1 Корневые деревья

Определение: Корневое дерево — ориентированное дерево, которое удовлетворяет условиям:

a) Имеется ровно один узел в который не входит не одно

В каждый узел кроме корня входит ровно одно ребро

Из корня имеется путь к любому ребру.

Если имеется путь от вершины vl к вершине v2, тогда вершина vl предок вершины v2, а вершина v2 потомок вершины vl.

Вершина которая не имеет потомков называется концевой вершиной или листом. Не концевую вершину называют внутренней. Если V₁ и V₂ дуга корневого дерева, то V₁— отец, a V₂— сын

Глубина дерева — длина пути из корня. Узлы находящиеся на одной глубине называются ярусами дерева.

Для задания корневого дерева можно использовать те же способы, что и для любого графа. На практике для представления деревьев используется канонический способ: для каждого узла хранится указатель на отца.

2 Бинарные деревья

Определение: Бинарное дерево — корневое дерево у каждой вершины которого не более двух сыновей.

В таком дереве любой произвольный узел имеет левого и правого сына. Поддерево корнем которого является левый сын называется левым поддеревом. Поддерево корнем которого является правый сын называется правым поддеревом.

Имеется два способа представления бинарных деревьев:

1. Представление в виде двух массивов: первый массив- левые сыновья, второй — правые.

2. Представление в виде списковой структуры tree_ ptr Tree_mode — запись имеющая структуру:

Element- тип узла; Left: tree_ ptr; Right: tree_ ptr;

3 Полные бинарные деревья

Определение: Полное бинарное дерево — бинарное дерево для которого выполняются условия:

a) Заполнение дерева осуществляется от корня к листьям по уровням.

b) Заполнение уровней осуществляется слева направо.

Полные бинарные деревья представляются в виде одномерного массива: первый элемент массива — корень дерева. Для любого i-того узла элемент с индексом (2i) — левый сын, элемент с индексом (2i+l)- правый сын. Отец узла j — (j/2).

4 Бинарные поисковые деревья

Определение: Бинарное поисковое дерево — дерево поиска,

Все ключи в левом поддереве меньше ключа узла V

В правом поддереве все ключи больше, чем ключ V

В дереве нет одинаковых ключей.

5 Сбалансированные деревья

Определение: Дерево называется идеально сбалансированным, если оно является бинарным поисковым деревом и число вершин его левых и правых поддеревьев отличается не более, чем на единицу.

Определение: Дерево называется сбалансированным, если оно бинарное поисковое и высоты двух поддеревьев в каждой из вершин отличаются не более, чем на единицу.

6 Способы обхода узлов в бинарных деревьях

Большинство алгоритмов при работе с деревьями посещают каждый узел в некотором порядке.

Существует три наиболее распространенных способа обхода деревьев:

1. Прямой порядок: корень посещается раньше, чем поддеревья

Порядок обхода: корень — левое поддерево — правое поддерево.

Процедура организуется рекурсивно.

2. Обратный порядок (снизу вверх): корень посещается после поддеревьев.

Порядок обхода: левое поддерево — правое поддерево- корень.

3. Внутренний порядок (слева направо )

Порядок обхода: левое поддерево – корень — правое поддерево.

7 Представление множеств с помощью деревьев

Базовыми операциями над множествами являются:

определение принадлежности элемента множества.

объединение не пересекающихся множеств.

Каждое множество будем представлять в виде корневого дерева. Корень дерева можно использовать для хранения имени множества. Дерево будем представлять в каноническом виде.

Чтобы определить, к какому множеству принадлежит некоторый элемент — находим этот элемент и определяем корень множества, к которому он принадлежит. Этот корень — есть имя искомого множества.

Объединение непересекающихся множеств можем реали­зовать тремя способами:

Источник

Дерево

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

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

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

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

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

Источник