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

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

1. 
   Определить структуру узла дерева, которая должна содержать данные узла и указатели на его потомков.
   
2. 
   Создать корневой узел дерева, содержащий указатель на корень дерева.
   
3. 
   Для каждого узла дерева создать объект структуры, содержащей данные узла и указатели на его потомков. При создании объекта можно задать начальные значения указателей на NULL.
   
4. 
   Установить указатели на потомков для каждого узла дерева. Для этого можно использовать следующий алгоритм:
   

1. 
   Для каждого узла дерева установить указатель на его левого потомка.
   
2. 
   Если узел имеет левого потомка, то установить указатель на родительский узел.
   
3. 
   Для каждого узла дерева установить указатель на его правого потомка.
   
4. 
   Если узел имеет правого потомка, то установить указатель на родительский узел.
   
5. 
   Для доступа к узлам дерева можно использовать указатели на узлы.
   
6. 
   При удалении узла из дерева необходимо освободить память, выделенную для этого узла.
   

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

1. 
   Прямой обход (pre-order traversal) - при прямом обходе сначала посещается корень дерева, затем левое поддерево и затем правое поддерево. Прямой обход используется для создания копии дерева, вычисления выражений в дереве, преобразования выражений в постфиксную нотацию и т.д.
   

2. 
   Симметричный обход (in-order traversal) - при симметричном обходе сначала посещается левое поддерево, затем корень дерева и затем правое поддерево. Симметричный обход используется для сортировки элементов в дереве, поиска элемента в отсортированном дереве и т.д.
   

3. 
   Обратный обход (post-order traversal) - при обратном обходе сначала посещается левое поддерево, затем правое поддерево и затем корень дерева. Обратный обход используется для вычисления выражений в постфиксной нотации, удаления дерева и т.д.
   

Пример кода для прямого обхода дерева: C++

#include

using namespace std;

struct TreeNode {

int val;
TreeNode* left;
TreeNode* right;

TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

};

void preorderTraversal(TreeNode* root) {

if (!root) {
return;
}
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}

int main() {

/*
1
/ \
2 3
/ \
4 5
*/
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->right->left = new TreeNode(4);
root->right->right = new TreeNode(5);

cout << "Preorder traversal: ";

preorderTraversal(root);

return 0;

}
Этот код создает бинарное дерево и выполняет прямой обход, начиная с корня дерева. Результатом работы программы будет:
Preorder traversal: 1 2 3 4 5