**Дерево** - совокупность элементов, называемых узлами, один из которых определяется как корень, и родительских отношений, определяющих иерархическую структуру дерева.   Рекурсивное определение дерева:
1. Один узел является деревом, этот же узел является его корнем
2. **Путем** из узла $n_{1}$ в узел $n_{k}$ называется последовательность вершин $n_{1}$, $n_{2}$, $n_{3}$, $...$, $n_{k-1}$, $n_{k}$, где для всех $1\leq\ i<k$ узел $n_{i}$ является родительским для узла $n_{i+1}$. **Длиной пути** называется число, на 1 меньшее количества узлов, составляющих этот путь.
3. Если существует путь из узла $a$ в узел $b$, то $a$ - предок узла $b$, а $b$ - потомок узла $a$. Считается, что любой узел является предком и потомком самому себе. Таким образом, **корень дерева** - это узел, не имеющий никаких предков, кроме самого себя.
4. Узел, не имеющий других потомков, кроме самого себя, называется **листом**, или **терминальной вершиной** дерева.
5. **Высотой вершины** называется длина самого длинного пути от этой вершины до одного из листов дерева
6. **Глубина узла** - это длина пути от корня до этого узла.
7. Дерево, в котором нет ни одного узла, называется **нулевым деревом**.
  
**Пример дерева:**  
![Пример дерева](../Pictures/03_01.%20Пример%20дерева.png)  
Корень дерева: $A$  
Листья дерева: $E, F, J, K, H, I$  
Высота дерева: 3  
## Способы обхода деревьев
**Обход дерева** фактически является упорядочением его вершин по некоторому правилу. Наиболее часто встречаются 3 вида обхода деревьев: прямой, обратный и симметричный.  
Правила обхода:
- Если дерево $T$ является нулевым деревом, то в список обхода заносится нулевая запись
- Если дерево состоит из 1 узла (он же корень и лист), то в список обхода заносится этот узел
- Пусть $T$ - дерево с корнем $n$ и поддеревьями $T_{1}$, $T_{2}$, $...$, $T_{k}$:  
	 ![Дерево T](../Pictures/03_02.%20Дерево%20T.png)  
	 Тогда для различных способов обхода имеем:
	 1. При **прямом обходе** сначала посещается корень $n$, затем поддеревья $T_{1}$, $T_{2}$, $...$, $T_{k}$, также в прямом порядке ($A, B, E, F, C, G, J, K, D, H, I$)
	 2. При **обратном обходе** сначала в обратном порядке обходится поддерево $T_{1}$, затем $T_{2}$, $...$, $T_{k}$, последним обходится корень $n$ ($E, F, B, J, K, G, C, H, I, D, A$)
	 3. При **симметричном обходе** сначала в симметричном порядке обходится поддерево $T_{1}$, затем корень $n$, далее поддеревья $T_{2}$, $...$, $T_{k}$, также в симметричном порядке ($E, B, F, A, C, J, G, K, H, D, I$)
## Бинарные деревья
Отдельный интерес в теории алгоритмов вызывают деревья, у каждого узла которых не более 2 потомков. Такие деревья называются **бинарными** или **двоичными**.  
Бинарное дерево называется **сбалансированным**, если разность высот левого и правого поддеревьев у любого узла дерева по модулю не более единицы:  
![Сбалансированное бинарное дерево](../Pictures/03_03.%20Сбалансированное%20бинарное%20дерево.png)  
Если эта разность для любого узла равна 0, дерево **идеально сбалансированное**:  
![Идеально сбалансированное дерево](../Pictures/03_04.%20Идеально%20сбалансированное%20дерево.png)
## Способы представления бинарных деревьев
1. С помощью одномерного массива  
![Представление бинарного дерева с помощью одномерного массива](../Pictures/03_05.%20Представление%20бинарного%20дерева%20с%20помощью%20одномерного%20массива.png)
2. С помощью динамической структуры
```cpp
struct Node {
	int data;
	Node* left;
	Node* right;
};
```
![Представление бинарного дерева с помощью динамической структуры](../Pictures/03_06.%20Представление%20бинарного%20дерева%20с%20помощью%20динамической%20структуры.png)  
Реализация обходов дерева:
```cpp
#include <iostream>
using namespace std;

struct Node {
	int data;
	Node* left; 
	Node* right;
};

void add(int x, Node*& node) {
	if (node == NULL) {
		node = new Node;
		node->data = x;
		node->left = NULL;
		node->right = NULL;
	}
}

void printTree(Node* node) {
	if (node != NULL) {
		//cout << node->data << " "; //прямой обход
		printTree(node->left);
		//cout << node->data << " "; //симметричный обход
		printTree(node->right);
		//cout << node->data << " "; //обратный обход
	}
}

int main() {
	Node* root = NULL;
	add(33, root);
	add(2, root->left);
	add(46, root->right);
	add(13, root->left->left);
	add(27, root->left->right);
	add(666, root->left->left->right);
	printTree(root);
	cout << endl;
	system("pause");
	return 0;
}
```
## Дерево Хаффмана
КОЛОКОЛ  
О - 3 раза  
К - 2 раза  
Л - 2 раза  
Фано:  
О - 0 | К, Л - 1  
К - 10 | Л - 11  

| К | О | Л | О | К | О | Л |
| ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| 10 | 0 | 11 | 0 | 10 | 0 | 11 |
  
Дерево Хаффмана:  
![Дерево Хаффмана](../Pictures/03_07.%20Дерево%20Хаффмана.png)  
Будем строить бинарное дерево с использованием динамических структур данных. Узел будет содержать частоту (по факту вероятность) вхождения символа, сам символ, а также указатели на левое поддерево, правое поддерево и родительский узел. Помимо структуры объявим 2 одномерных массива размером 256 элементов. В массиве **trees** изначально будем хранить указатели на узлы с отдельными символами. По мере построения дерева будем объединять эти символы в деревья, указатели на корни также будем хранить в этом массиве, и так до тех пор, пока не останется данного дерева.

![Реализация дерева Хаффмана с помощью массива](../Pictures/03_08.%20Реализация%20дерева%20Хаффмана%20с%20помощью%20массива.png)  

В массиве **symlbols** - указатели на каждый символ, чтобы, используя их, двигаясь к родительским узлам, быстро найти код символа.  
В переменной **size** будем хранить реальное количество символов

```cpp
#include <iostream>
using namespace std;

class HaffmanTree {
private:
	struct Node {
		double p;
		char c;
		Node* left;
		Node* right;
		Node* parent;
	};

	Node* trees[256];
	Node* symbols[256];
	int size;

public:
	HaffmanTree(int col) {
		size = col;
	}

	void MakeTree(int col) {
		if (col > 1) {
			double minp1 = 1;
			int n1 = 0;
			for (int i = 0; i < size; i++) //ищем первый минимум
				if (trees[i] != NULL && trees[i]->p < minp1) {
					minp1 = trees[i]->p;
					n1 = i;
				}
			double minp2 = 1;
			int n2 = 0;
			for (int i = 0; i < size; i++) //ищем второй минимум
				if (trees[i] != NULL && trees[i]->p < minp2 && i != n1) {
					minp2 = trees[i]->p;
					n2 = i;
				}
			Node* tmp = new Node; //новое дерево
			tmp->left = trees[n1]; 
			tmp->right = trees[n2];
			trees[n1]->parent = tmp;
			trees[n2]->parent = tmp;
			tmp->p = trees[n1]->p + trees[n2]->p;
			tmp->parent = NULL;
			trees[n1] = tmp;
			trees[n2] = NULL;
			MakeTree(col - 1); //опять в лес по дрова...
		}
	}
	void ReadInfo() {
		for (int i = 0; i < size; i++) {
			trees[i] = new Node;
			symbols[i] = trees[i];
			cout << "Enter symbol: "; cin >> trees[i]->c;
			cout << "p="; cin >> trees[i]->p;
			trees[i]->left = NULL;
			trees[i]->right = NULL;
			trees[i]->parent = NULL;
		}
	}
	void ShowCodes() {
		if (size == 1)
			cout << symbols[0]->c << " - " << 0 << endl;
		else {
			Node* tmp;
			string code;
			for (int i = 0; i < size; i++) {
				tmp = symbols[i];
				code = "";
				while (tmp->parent != NULL) {
					if (tmp->parent->left == tmp)
						code = "0" + code;
					else code = "1" + code;
					tmp = tmp->parent;
				}
				cout << symbols[i]->c << " - " << code << endl;
			}
		}
	}
};

int main() {
	int col = 5;
	HaffmanTree ht(col);
	cout << endl;
	ht.ReadInfo();
	ht.MakeTree(col);
	ht.ShowCodes();
	cout << endl;
	system("pause");
	return 0;
}
```