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

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

1. 
   Массивы: Для представления дерева можно использовать одномерный массив, в котором каждый элемент соответствует узлу дерева. Индекс элемента соответствует порядковому номеру узла, а значение элемента - содержимому узла. Например, если у нас есть дерево с узлами "A", "B", "C", "D", "E", "F", то оно может быть представлено следующим образом:
   

[A, B, C, D, E, F]

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

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

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

struct Node {
int value;
Node* first_child;
Node* next_sibling;
Node* prev_sibling;
};

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

struct Node {
int value;
vector children;
};

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

Последовательное размещение элементов дерева на базе вектора - это способ организации хранения данных в памяти компьютера, при котором элементы дерева размещаются последовательно в памяти вектора. Для этого используется так называемое "обход дерева в глубину" (Depth-First Traversal), при котором сначала обрабатывается левое поддерево, затем корень, а затем правое поддерево.
Для хранения элементов дерева в векторе можно использовать следующий алгоритм:

1. 
   Обойти дерево в глубину, начиная с корня, и добавлять каждый узел в вектор в порядке его обхода. При этом каждый узел добавляется только после добавления всех его потомков.
   
2. 
   Если дерево является не полным, то в векторе будут присутствовать пустые элементы, соответствующие отсутствующим узлам дерева.
   
3. 
   Для доступа к узлам дерева по индексу можно использовать следующее соответствие: для узла с индексом i его левый потомок находится в индексе 2i+1, а правый потомок - в индексе 2i+2.
   
4. 
   Для определения размера вектора, содержащего элементы дерева, можно использовать формулу: размер = 2^(глубина дерева) - 1.
   

Пример кода для хранения элементов дерева в векторе:
#include
struct Node {
int value;
Node* left;
Node* right;
};
std::vector treeToVector(Node* root) {
std::vector v;
if (root == nullptr) {
return v;
}
std::vector stack;
stack.push_back(root);
while (!stack.empty()) {
Node* node = stack.back();
stack.pop_back();
v.push_back(node->value);
if (node->right != nullptr) {
stack.push_back(node->right);
}
if (node->left != nullptr) {
stack.push_back(node->left);
}
}
return v;
}