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


Download 18.66 Kb.
bet1/2
Sana18.06.2023
Hajmi18.66 Kb.
#1583585
TuriЛекция
  1   2
Bog'liq
Лекция 6 (1)


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

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

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

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

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

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

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

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

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;
}

Download 18.66 Kb.

Do'stlaringiz bilan baham:
  1   2




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling