Лекция 6 Тема: Способы представления деревьев в памяти компьютера. Последовательное размещение элементов на базе вектора. Связанное размещение элементов на базе указателей. Основные операции, выполняемые над деревьями. Обход дерева
Download 18.66 Kb.
|
1 2
Bog'liqЛекция 6 (1)
- Bu sahifa navigatsiya:
- Последовательное размещение элементов дерева на базе вектора
Лекция 6 Тема: Способы представления деревьев в памяти компьютера. Последовательное размещение элементов на базе вектора. Связанное размещение элементов на базе указателей. Основные операции, выполняемые над деревьями. Обход дерева. Деревья могут быть представлены в памяти компьютера разными способами. Рассмотрим некоторые из них: Массивы: Для представления дерева можно использовать одномерный массив, в котором каждый элемент соответствует узлу дерева. Индекс элемента соответствует порядковому номеру узла, а значение элемента - содержимому узла. Например, если у нас есть дерево с узлами "A", "B", "C", "D", "E", "F", то оно может быть представлено следующим образом: [A, B, C, D, E, F] Структуры: Для представления дерева можно использовать структуру, в которой каждый узел имеет поля для хранения ссылок на его дочерние узлы и значения. Например: struct Node { int value; Node* left; Node* right; } Списки: Для представления дерева можно использовать связанные списки, в которых каждый узел имеет ссылку на следующий и предыдущий узлы на том же уровне, а также ссылку на первый дочерний узел. Например: struct Node { int value; Node* first_child; Node* next_sibling; Node* prev_sibling; }; Рекурсивные структуры: Для представления дерева можно использовать рекурсивные структуры, в которых каждый узел содержит ссылки на его дочерние узлы, которые также являются экземплярами этой же структуры. Например: struct Node { int value; vector }; Каждый из этих способов имеет свои преимущества и недостатки, и выбор определенного способа зависит от конкретной задачи, которую необходимо решить. Последовательное размещение элементов дерева на базе вектора - это способ организации хранения данных в памяти компьютера, при котором элементы дерева размещаются последовательно в памяти вектора. Для этого используется так называемое "обход дерева в глубину" (Depth-First Traversal), при котором сначала обрабатывается левое поддерево, затем корень, а затем правое поддерево. Для хранения элементов дерева в векторе можно использовать следующий алгоритм: Обойти дерево в глубину, начиная с корня, и добавлять каждый узел в вектор в порядке его обхода. При этом каждый узел добавляется только после добавления всех его потомков. Если дерево является не полным, то в векторе будут присутствовать пустые элементы, соответствующие отсутствующим узлам дерева. Для доступа к узлам дерева по индексу можно использовать следующее соответствие: для узла с индексом i его левый потомок находится в индексе 2i+1, а правый потомок - в индексе 2i+2. Для определения размера вектора, содержащего элементы дерева, можно использовать формулу: размер = 2^(глубина дерева) - 1. Пример кода для хранения элементов дерева в векторе: #include struct Node { int value; Node* left; Node* right; }; std::vector std::vector if (root == nullptr) { return v; } std::vector 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; } Download 18.66 Kb. Do'stlaringiz bilan baham: |
1 2
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling