Study & Dev | Blog Archive | Структуры данных и алгоритмы. Теория. Деревья. Основные алгоритмы над деревьями

Структуры данных и алгоритмы. Теория. Деревья. Основные алгоритмы над деревьями

January 7, 2007

Дерево – это АТД (абстрактный тип данных) для хранения информационных элементов имеющих нелинейные отношения. За исключением элемента, который находится во главе дерева, каждый элемент имеет родителя, а также ноль или более дочерних элементов. Также говорят что дерево – это множество элементов, среди которых есть один выделенный который называется корнем, а остальные содержатся в N непересекающихся подмножествах, которые называются поддеревьями. Очевидно что дерево относится к классу динамических структур данных наряду с нам уже знакомыми стеком, очередями. С помощью дерева можно представить, например, следующую организационную структуру:

Наиболее известным классическим примером деревьев является генеалогическое дерево.

Также в качестве примера можно привести принятую в большинстве файловых систем организацию с помощью иерархически вложенных директорий и файлов. Наиболее ярко это проявляется в О.С. linux и unix, где файловую систему представляют в виде единого дерева, которое начинается с корневой директории обозначаемой “/”.

При дальнейшем обсуждении деревьев следует условиться о терминологии. Корень дерева (root) – первый его элемент (в приведенном выше изображении это “Средняя школа # 123”). Каждый элемент данных называют узлом (node), иногда листом (leaf). Фрагмент дерева называется поддеревом (subtree) или ветвью. Узел, не имеющий отходящих от него ветвей ли поддеревьев, называются терминальным или конечным узлом (terminal node). Высота дерева (height) – определяется количеством уровней, на которых располагаются его узлы. При работе с деревьями полезно изображать их на бумаге, однако при этом всегда следует помнить, что деревья – это метод логической организации информации в памяти компьютера, не физической.

Следует помнить, что большинство операций, которые выполняются над деревьями, являются рекурсивными, т.к. деревья имеют рекурсивную структуру – каждое дерево содержит множество поддеревьев.

О деревьях можно судить как об упорядоченных или не упорядоченных. Мы говорим, что дерево упорядочено, если каждому из элементов можно сопоставить порядковый номер: 1,2,3. На рисунках упорядоченные “братья-узлы” представляются слева направо.

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

В информатике наиболее часто используются именно двоичные деревья - это деревья, каждый узел которого содержит не более чем два подчиненных ему (дочерних элемента). Бинарное дерево считается правильным, если каждый узел не содержит одного или содержит два дочерних элемента. Таким образом – генеалогическое дерево – это правильно двоичное дерево. В бинарных деревьях дочерние узлы именуют “правый” и “левый”.

С помощью двоичного дерева можно легко представить арифметическое выражение с использованием бинарных операций.

Например, для выражения: (2*3)/(1+1)-(3*7) можно построить следующее дерево:

Задание: составьте бинарные деревья для следующих выражений:

1+3*5-(17*(21-5))
2*3*(2-6)*(7-4)*(1-5)
8*1*(5/7)*((1+2)/(3-7))

Деревья широко также применяются при создании экспертных систем и баз знаний. С помощью деревьев можно представлять деревья поиска решений, в которых переход от одного утверждения к другому есть спуск от корневого элемента (находящегося вверху дерева) к одному из конечных. В качестве еще одного примера можно привести изображение дерева игры в крестики-нолики, в данном дереве каждый узел дерева это состояние на поле в определенный момент времени.

Для каждого узла дерева можно определить понятие глубины. Допустим, V – узел дерева. Глубина узла выражается количество предков V, за исключением самого V. По определению глубина корня равна нулю.

Глубина определяется рекурсивно:

если узел –корень, то его глубина ноль;
в противном случае глубина узла V равна 1 + глубина его родителя V`.

Способы представления деревьев: Представление дерева с помощью массива

Когда мы начинаем переходить к вопросу практического использования дерева, то следует решить, каким именно образом нам следует хранить его элементы, так чтобы не потерять ранжиры. Как ни странно, но можно решить данную задачу, даже если использовать обычный массив. Рассмотрим пример подобного представления для двоичного дерева, это не нарушает общности рассуждений, если вы хотите работать с мульти-деревом, то в этой ситуации необходимо четко определиться с максимальным количеством прямых потомков для каждого из узлов, если такого постоянного значения определить нельзя, то представление с помощью массивов не возможно и вам следует использовать прием с динамически выделяемой памятью и даже некоторого синтеза дерева и списка. В каждом элементе списка будет храниться ссылка на каждого из потомков текущего узла V. Для представления с помощью массива мы каждому из элементов дерева дадим порядковый номер:

P(V) = 2*N - в случае если узел V находится слева от своего родительского узла V*.
P(V)= 2*N + 1 – а эта формула применима в той ситуации, когда узел V находится правее чем родительский.

В обоих формулах значение N – порядковый номер узла V*.

Очень важно, что если дерево не полное, то отсутствующим элементам назначаются номера и для них выделяется место в массиве, просто в ячейке с номером “8, 9, 13, 29” и других (согласно приведенному изображению дерева математического выражения) ничего не хранится.

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

В случае множественного дерева (каждый узел может иметь произвольное количество потомков) возможно, воспользоваться подобным объявлением:

```
struct MultiNode {
```
```
   DATA_TYPE data;
```
```
   MultiNode * parent; 
```
```
   LIST_OF_NODES children;
```
```
};
```

В данном примере DATA_TYPE – тип данных соответствующий хранимому в дереве, например, если у нас дерево математического выражения, то это может быть число или знак арифметической операции. Если дерево служит для хранения генеалогической информации – то в качестве типа каждого узла может быть строка с именем человека, или даже произвольная структура или класс CHuman, описывающий кого-то из предков. Обратите внимание на другое, в структуре присутствует ссылка на узел дерева который является родительским, в общем случае это не требуется, однако при решении многих задач поиска и модификации дерева позволяет их упростить, благодаря подобной ссылке мы можем перемещаться по дереву не только в направлении от корня к нижележащим элементам, но и в обратном порядке.

Под LIST_OF_NODES подразумевается некий контейнер способный хранить внутри себя достаточное количество ссылок на поддеревья. В случае если количество не велико и относительно стабильно, то можно воспользоваться обычным массивом. В случае, когда количество элементом может варьироваться в произвольном диапазоне, то рекомендуется применять один из ранее изученных контейнеров: очередь, дек. Если вы используете средства STL, то можно объявить ссылку на множество поддеревьев так:

```
Vector <MultiNode *> children;
```
```
List <MultiNode *> children;
```

В случае использования частного случая – бинарного дерева, объявление узла выглядит проще:

```
struct BinNode {
```
```
   DATA_TYPE data;
```
```
   BinNode * parent;
```
```
   BinNode * left , * right;
```
```
};
```

Алгоритмы формирования деревьев

До текущего момента все рассмотренные алгоритмы предполагали, что у нас есть построенное двоичное или мульти-дерево. Теперь мы рассмотрим схему формирования деревьев с упором именно на практические направления. Одним из важнейших направлений использования бинарных деревьев является оптимизация задач поиска. Когда мы рассматривали тему поиска, то из двух способов – линейных поиск (затраты порядка O(n)) и двоичного поиска (затраты порядка O(log n)) очевидным было применение именно второго подхода. Однако в этом случае нам было необходимо выполнить сортировку массива данных в противном случае алгоритм не работал. В случае использования двоичных деревьев можно создать такой алгоритм его формирования, что задача поиска в нем нужного элемента также будет составлять порядка O(log n).

Пример: предположим, что нашей программе на вход подается поток чисел (в общем случае не упорядоченный), если мы опишем узел дерева как

```
struct BinNode {
```
```
 int data;
```
```
 BinNode * left , * right;
```
```
};
```

И потребуем чтобы все узлы, находящиеся в правом поддереве были больше чем корневой элемент, а все узлы из левого поддерева были не более чем корневой элемент, то в таком случае для последовательности чисел: 6 1 3 7 2 9 4 5 2 будет построено следующее дерево:

Деревья, для которых выполняется вышеописанное соотношение, называются деревьями поиска. В таком дереве, для того чтобы найти нужный элемент на каждом шаге пути необходимо принимать решение о выборе направления в зависимости от того, как соотносятся искомый элемент X и значение текущего узла Vi. Если Vi >= X то в таком случае поиск должен идти именно в левом поддереве, в противном случае в правом. Следует отметить, что получившееся двоичное дерево и соответственно эффективность операций поиска сильно зависит от степени упорядоченности поступающих наборов чисел. В случае если эти значения уже отсортированы, например: 1, 2, 3, 4 то получающееся дерево вырождается и начинает напоминать обычный линейный список.

В идеальном случае дерево должно быть сбалансированным. Напомню, что сбалансированным деревом является то, где количество узлов в правом и левом поддеревьях отличаются не более чем на 1. для повышения скорости работы алгоритма поиска в бинарном дереве также используют прием буфера (барьера). В этом случае все ветви будут заканчиваться не ссылкой на NULL, а ссылкой на этот буферный элемент. То, что у нас получилось можно увидеть на картинке:

Пример1 - функция поиска в дереве без буферного элемента.

Пример2 - функция поиска в дереве с использованием буферного элемента.

BinNode * find (int data, BinNode * cur){

```
while (cur && cur->data != data)
```
```
if  ( cur->data <= data)
```
```
cur = cur->left;
```
```
else
```
```
cur = cur->right;
```
```
return cur;
```
```
}
```

BinNode * find (int data, BinNode * cur){

```
GlobalBuffer->data = data;
```
```
while (cur->data != data)
```
```
if ( data <= cur->data)
```
```
cur = cur->left;
```
```
else
```
```
cur = cur->right;
```
```
return cur;
```
```
}
```

Замечания к приведенным алгоритмам

В примере 2 предполагается наличие глобальной переменной GlobalBuffer, которая и является ссылкой на вспомогательный (фиктивный) барьерный элемент. Отметьте, что значение информационной компоненты data для этого буферного элемента перед началом цикла устанавливается в data, что позволяет упростить поиск за счет уменьшения количества операций сравнения. Часто начинающие программисты пытаются реализовать подобный поиск с помощью рекурсии, аргументируя, что раз структура данных рекурсивна то и поиск тоже должен быть таковым. Напоминаю, что настоятельно рекомендуется избегать применения рекурсии везде где это возможно из-за непроизводительных затрат на вызов функции.

Очевидно, что деревья будут вряд ли применяться в задачах, структуры данных которых сформированы и не изменяются на протяжении работы программы. Также очевидно, что на практике деревья должны будут расти и уменьшаться. Рассмотрим пример использования дерева для решения задачи частотного анализа.

Пример: предположим, что есть файл, содержащий некоторый объем текста. Для каждого из слов (как вариант, буквы) содержащегося в файле необходимо выполнить подсчет частоты его встречи. Простейшее решение, которое приходит в голову, это воспользоваться структурой данных типа ХЕШ (ассоциативный массив) в этом случае в качестве ключа будет использоваться само слово, в качестве его значения будет количество повторений. Разумеется, что хеш будет легко эмулировать с помощью двух массивов. В случае если файл содержит достаточно большое количество разных слов, то узким местом данного алгоритма будет поиск позиции, в которой встречается нужное слово. В случае если слова поступают в не отсортированном виде, что вполне ожидаемо, то мы должны будем просматривать в среднем половину от заполненного массива слов пока не найдем искомый. Можно воспользоваться, например, алгоритмом сортировки (здесь наиболее естественно применять метод вставки), мы же рассмотрим применение поискового дерева. Слова в нем будут располагаться в алфавитном порядке, т.е. все слова левого поддерева должны находиться в словаре раньше, чем корневой элемент, соответственно все слова правого поддерева должны находиться в словаре позже, чем корневой элемент (не забывайте, что такое соотношение должно выполняться для всех поддеревьев). Каждый раз, когда на вход программе будет поступать очередное слово будет выполняться поиск его схема идентична той, которая была приведена в таблице выше, если операция поиска была неудачна (функция из примера 1 вернула NULL, а функция из примера 2 вернула ссылку на сам буферный элемент), то необходимо в соответствующую позицию вставить новое слово, и его счетчик количества повторений инициализировать 1. После завершения формирования дерева его можно распечатать. Фрагмент кода решающего данную задачу приводится ниже.

```
#include "string.h"
```
```
#include "stdio.h"
```
```
#include "assert.h"
```
```
 
```
```
struct BinNode {
```
```
	char data [51]; // само слово
```

	int count; // количество повторений слова

```
	BinNode * left ,  * right;
```
```
};
```
```
 
```

void addNode (char * what , BinNode ** root){

```
	int z;
```

	while (*root && (z = strcmp((*root)->data, what)) !=0 )

		root =  (z < 0?&((*root)->left):&((*root)->right));

```
	if (* root)
```
```
		(*root)->count++;
```
```
	else
```
```
	{
```
```
		*root = new BinNode;
```
```
		strcpy( (*root)->data  , what);
```
```
		(*root)->count = 1;
```

		(*root)->left = (*root)->right = NULL;

```
	}
```
```
}
```
```
 
```
```
 
```

BinNode * rec_addNode (char * what, BinNode * curNode ){

```
	if (!curNode){
```
```
		curNode = new BinNode;
```
```
		strcpy(curNode->data , what);
```
```
		curNode->count = 1;
```

		curNode->left = curNode->right = NULL;

```
		return curNode;
```
```
	}
```

	int z = strcmp (curNode->data , what);

```
	if (!z)
```
```
		curNode->count++; 
```
```
	else{
```
```
		if (z < 0)
```

			curNode->left = rec_addNode (what , curNode->left);

```
		else
```

			curNode->right = rec_addNode (what , curNode->right);

```
 
```
```
	}
```
```
	return curNode;
```
```
}
```
```
 
```

void printTree (BinNode * root , int level){

```
	if (root){
```

		printf ("level=%d word=%s count=%d\n" ,level ,  root->data  , root->count );

```
		printTree (root->left  , level + 1);
```
```
		printTree (root->right  , level + 1);
```
```
	}
```
```
}
```
```
 
```
```
void main (void){
```
```
	BinNode * root = NULL;
```
```
	FILE * f = fopen ("dict.txt", "r");
```
```
	assert (f);
```
```
	char buf [101];
```
```
	while ( !feof(f)){
```
```
		 fgets (buf , 100 , f);
```

		char * ptrToken = strtok (buf , " ,-:.\n\t");

```
		while (ptrToken){
```
```
			 addNode (ptrToken , &root);
```

// здесь может быть вызвана как нерекурсивная так и рекурсивная версия функции добавления нового узла в дерево.

			 //root = rec_addNode (ptrToken , root);

			 ptrToken = strtok (NULL , " ,-:.\n\t");

```
		 }
```
```
 
```
```
	}
```
```
 
```
```
	printTree (root , 0);
```
```
}
```

В приведенном выше примере реализованы две версии функции для добавления нового слова в частотный словарь (нового узла в дерево) – одна из них не рекурсивная, вторая рекурсивна. Обратите внимание на то, каким именно образом в не рекурсивной версии обеспечивается модификация ссылки на узел (левой или правой) для родительского узла. В рекурсивной версии от использования двойной ссылки я отказался а, следовательно, был вынужден возвращать из функции ссылку на новое перестроенное дерево и присваивать его родительскому “left” или “right”.

Задание: в приведенном примере отсутствует код по удалению созданного дерева, освобождения занятой памяти. Добавьте его самостоятельно.

Подсказка: в терминах рекурсии операция удаления дерева формулируется практически идентично операции печати элементов. Что означает удалить дерево – сначала следует удалить левое поддерево, потом правое, и, наконец, сам корневой элемент. Когда вы это сделаете, то попробуйте найти также и не рекурсивное решение.

Задание: классической задачей также можно считать построения по заданному входному тексту дерева с перекрестными ссылками. Для каждого слова каждой строки текста необходимо определить информацию о том, в каких именно строках данное слово встречалось, а затем распечатать слова в алфавитном порядке с перечислением номеров строк. Подсказка в данном случае рекомендуется сочетать использование двоичного дерева из предыдущего примера, в каждом, из узлов которого будет храниться ссылка на другой вспомогательный контейнер для хранения номеров строк. Можно воспользоваться списком или деком из ранее рассмотренных тем. В случае если мы будем хранить именно номера строк, то можно пренебречь эффективностью решения задачи и применить фиксированный массив размером не более чем количество всех строк исходного текста. Однако более совершенным будет использование именно списка. Когда вы сделаете это задание, то попробуйте дальше развить пример и добавить необходимость работать с самими строками, а не их номерами, так можно создать глобальный массив с перечислением строк. А каждый элемент списка будет ссылкой на какой-нибудь из элементов массива строк.

Операции над деревьями. Проход дерева.

Методы обхода дерева будем рассматривать на примере двоичного дерева изображенного на следующем изображении (следует отметить, что выбор в качестве пример именно бинарного дерева ни коим образом не ограничивает общности наших рассуждений).

Проход дерева представляет собой систематическое посещение всех его узлов. Наиболее известна схема прямого и обратного прохода.

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

ПрямойПроход (УзелДерева * node){
  Обработка узла node;
  Цикл для всех поддеревьев node
    ПрямойПроход (node->getNextChild());
}

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

 A B C D F E G.

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

Для дерева описывающего выражение (2*3)/(1+1)-(3*7), строковым представлением будет следующая строка: ( - (/ (* 2 3) (+ 1 1)) (* 3 7)). В данном случае следует применять метод прямого прохода. Обратите внимание на то, что для каждой скобки вначале ее идет знак арифметической операции, а затем операнды, если эти операнды – числа, то они записываются, как есть, если же какой-то операнд представляет собой выражение, то снова рекурсивно применяется правило прямого обхода.

Следовательно с помощью псевдокода алгоритм PrintForm(УзелДереваT) можно записать так:

Если T не имеет поддеревьев, то его строковым представлением будет 
PrintForm = T->toString()
В противном случае PrintForm = “( ” + T.operation  + PrintForm(T.getChild (0)) + “ ” + … + PrintForm (T.getChild(N-1)) + “)”.

В данном примере предполагается существование некоторого метода toString() который и печатает значение информационной компоненты каждого из узлов.

Обратный проход

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

 C D B E G F A.

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

Пример: рассмотрим задачу печати всех узлов дерева, которые имеют нечетное количество подчиненных узлов. В данном случае рекурсивный алгоритм BackPrintNodes (УзелДерева T) будет выглядеть так:

```
int backPrintNodes (Node * current){
```
```
  if (!current->hasChildren())
```
```
     return 1;
```
```
  int sum = 0;
```

  for (Int i= 0; I < current->getCountChildren(); i++)

     sum+= backPrintNodes (current->getChildAtPosition(i));

```
  if (sum % 2 !=0 )
```

     printf (“element %s” , current->getStringPresentation() );

```
  return 1 + sum;
```
```
}
```

В приведенном фрагменте кода предполагается, что каждый узел дерева имеет ряд методов для доступа к поддеревьям.

 * hasChildren – метод возвращает логическую величину – признак того есть ли у текущего узла поддеревья.
 * getCountChildren – возвращается количество подчиненных узлов.
 * getChildAtPosition – получение поддерева по порядковому номеру.
 * getStringPresentation – метод который возвращает строку представляющую (описывающую) текущий узел.

Разумеется, что конкретный код реализации данных методов зависит от того какие именно задачи, какую предметную область представляет данное дерево. Однако обратите внимание на то, что сначала мы выполняем проход по всем поддеревьям накапливая количество всех подузлов которые есть у текущего элемента дерева.

В качестве еще одного пример обратного прохода можно привести определение в каком-либо из файловых менеджеров (far, windows commander, Norton commander) объема занимаемого некоторой директорией. Очевидно, что объем директории состоит из объема дискового пространства для хранения служебной информации непосредственно о директории, также объема занимаемого всеми файлами которые находятся в каталоге, и внимание, объема который занимают подкаталоги. Следовательно, мы снова вынуждены выполнить проход по всем подкаталогам (на всех уровнях вложенности) чтобы определить объем текущего каталога.

Иные способы прохода деревьев

Метод прямого и обратного прохода наиболее часто встречается, однако есть и иные способы, например проход по глубине.

Как вы уже знаете каждый узел дерева имеет глубину (расстояние между ним и корневым элементом). В методе прохода по глубине сначала выполняется проход по все узлам, имеющим глубину X, и только потом выполняется переход к узлам с глубиной X + 1.

Исключение элементов из дерева

В дереве T необходимо удалить узел V. К сожалению, задача удаления не столь проста как операция добавления нового узла. В зависимости от того, какое именно количество непосредственных потомков (детей) есть у узла V возможны следующие стратегии:

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

Если узел V не имеет потомков (терминальный узел) то надо просто освободить занимаемую им память, а родительской ссылке на V присвоить значение NULL.
Если узел V имеет только одного потомка, (например V->left != NULL, а V->right==NULL) в таком случае мы после освобождения ресурсов памяти занимаемых V должны будем родительской ссылке на него присвоить ссылку на потомка V.
V имеет двух потомков. В этом случае удаляемый элемент следует заменить на либо самый правый

void helperDelete (BinNode ** cur, BinNode ** deleted){

```
     if ((*cur)->right)	
```

	 helperDelete (&(*cur)->right , deleted);

```
     else {
```
```
	(*deleted)->count = (*cur)->count;
```

	strcpy ( (*deleted)->data  , (*cur)->data);

```
	BinNode * tmp = *cur;
```
```
	*cur =  (*cur)->left; 
```
```
	delete tmp;
```
```
     }
```
```
}
```
```
 
```

void delElt (char * what , BinNode ** root){

```
	if (! (*root)) return;
```
```
	int z = strcmp( (*root)->data , what);
```
```
	if (! z){
```

		if ((*root)->left == NULL && (*root)->right == NULL){

```
			delete *root;
```
```
			*root = NULL;
```
```
			return;
```
```
		}
```

		if ((*root)->left && (!(*root)->right)){

```
			BinNode * tmp = * root;
```
```
			*root = (*root)->left;
```
```
			delete tmp;
```
```
			return;
```
```
		}
```

		if ((*root)->right && (!(*root)->left)){

```
			BinNode * tmp = * root;
```
```
			*root = (*root)->right;
```
```
			delete tmp;
```
```
			return;
```
```
		}
```
```
		helperDelete (&(*root)->left , root);
```
```
	}
```
```
	else{
```
```
		if (z < 0)
```
```
			delElt (what , &(*root)->left);
```
```
		else
```
```
			delElt (what , &(*root)->right);
```
```
	}
```
```
}
```

Вспомогательная функция “helperDelete” выполняет спуск вдоль левого поддерева удаляемого элемента все время вправо до тех пор, пока не будет найден элемент, который не имеет правого, обозначим его как “R”, тогда выполняется копирования его значения в узел для удаляемого элемента, а на самом деле удаляется физически (освобождается память) именно элемент R. Если элемент R имеет левое поддерево, то для него выполняется код аналогичный общей схеме удаления для узла, имеющего одного потомка.

Задания по теме деревья

1) Пусть T – бинарное дерево с количеством узлов N. Предположим, что некоторый узел данного дерева V будет называться романским, если количество потомков в его левой ветви отличается от количества потомков правой ветви максимум на 5. Необходимо разработать метод с линейными затратами времени, который найдет все такие узлы дерева V* которые сами не являются романскими, но при этом все его потомки являются таковыми.

2) Необходимо разработать код приложения, который выполняет прямой проход по дереву, не использую методы рекурсии.

3) Длина пути дерева T вычисляется как сумма глубин всех узлов T. Необходимо разработать метод, который с линейными затратами времени найдет длину дерева T.

4) Напишите программу ввода и отображения генеалогического дерева в виде бинарного дерева. При выводе желательно придерживаться следующей схемы отображения, количество отступов перед выводом каждого имени должно быть равно глубине соответствующего узла:

Иванов Петр
	Иванова Мария (мама Иванова Петра)
		Сидорова Татьяна (бабушка Иванова Петра, мама Ивановой Марии)
		Сидоров Яков (дедушка Иванова Петра, отец Ивановой Марии)
	Иванов Игорь (отец Иванова Петра)
		Иванова Елена(вторая бабушка Иванова Петра)
		Иванов Анатолий (второй дедушка Иванова Петра)

5) Реализуйте бинарное дерево, используя двунаправленную очередь (подсказка: это задание является развитием способа представления дерева в виде массива, но при этом мы не храним пустые (неиспользуемые элементы дерева). Можно использовать в качестве узла дерева структуру из двух полей: информация об узле а также его порядковый номер).

6) Васе Тапкину дали задачу создать поисковую систему “super-google”. Данная система ищет числа. В качестве известных данных выступает множество чисел A[1], A[2], ., A[k] (1<=k<=1000, 1<=A[i]<=10E6 , все A[i] - различные целые числа). На вход приложению должно поступать число X, система должна ответить на вопрос: «содержится ли среди чисел A[i] заданное значение». Вася Тапкин решил, что оптимальным решением поставленной задачи будет использование двоичных деревьев поиска.

На рисунке показаны различные двоичные деревья для набора ключей 1, 3, 7, 11, из них деревья б) и в) - двоичные деревья поиска. Корни деревьев изображены сверху.

Число	1	2	3	4	5	6	7	8	9	10	11
Стоимость	2	3	3	3	3	3	1	2	2	2	2

В сумме стоимость данного двоичного дерева составляет сумму стоимостей поиска каждого из ключей от 1 до n в этом дереве, т.е. 26.

Вася Тапкин хочет построить для своей поисковой системы двоичное дерево поиска минимальной стоимости. Необходимо разработать алгоритм, который по введенным числам n, k, A[1], ., A[k] определить минимальную стоимость C двоичного дерева поиска для набора ключей A[1], A[2], ., A[k] и диапазона поиска от 1 до n.

7) Необходимо создать класс MgenTree описывающий генеалогическое мульти-дерево. Пример изображения подобного дерева приводится ниже. Класс дерева должен содержать методы для добавления новых узлов, удаления существующих и трех видов прохода с распечаткой элементов. Не забудьте также про освобождение памяти в деструкторе данного класса.

Categories: Структуры данных и алгоритмы

Study & DevО программировании и не только