Я решил освоить язык программирования C/C и для практики решил написать программу, которая строит бинарное дерево на основе заданной последовательности чисел. Я поделил свой опыт на несколько шагов.Шаг 1⁚ Создание структуры для узла дерева
Для начала, я создал структуру, которая будет представлять узел дерева. В этой структуре будет храниться значение узла, а также указатели на его левый и правый дочерние узлы. Вот как выглядит определение этой структуры⁚
cpp
struct Node {
int data;
Node* left;
Node* right;
};
Шаг 2⁚ Построение бинарного дерева
Далее, я начал писать функцию для построения бинарного дерева. Для этого я принял на вход массив чисел и их количество. Сначала я создал корневой узел и задал ему значение первого элемента массива. Затем, я прошелся по оставшимся элементам массива и для каждого из них вызвал функцию вставки, которая будет рекурсивно добавлять узлы в дерево. Вот как это выглядит⁚
cpp
Node* insert(Node* root, int value) {
if (root nullptr) {
Node* newNode new Node;
newNode->data value;
newNode->left nullptr;
newNode->right nullptr;
return newNode;
}
if (value < root->data) {
root->left insert(root->left, value);
} else {
root->right insert(root->right, value);
}
return root;
}
Node* buildTree(int arr[], int n) {
Node* root nullptr;
if (n > 0) {
root new Node;
root->data arr[0];
root->left nullptr;
root->right nullptr;
}
for (int i 1; i < n; i ) { root insert(root, arr[i]); } return root; } Шаг 3⁚ Обход дерева и вывод результатов Для обхода дерева справа налево, я использовал модифицированный алгоритм обхода в глубину. Чтобы вывести значения узлов на экран, я добавил функцию `printReverse`, которая будет вызываться для каждого узла дерева. Вот как это выглядит⁚ cpp void printReverse(Node* root) { if (root nullptr) { return; }
printReverse(root->right);cout << root->data << ″ ″; printReverse(root->left);
}
void printReverseTree(Node* root) {
cout << ″Результаты обхода дерева справа налево⁚ ″;
printReverse(root);
cout << endl;
}
Шаг 4⁚ Очистка памяти
После выполнения программы очистить память, занятую древовидной структурой, я определил функцию `deleteTree`, которая будет вызываться для каждого узла дерева и рекурсивно очищать память. Вот как это выглядит⁚
cpp
void deleteTree(Node* root) {
if (root nullptr) {
return;
}
deleteTree(root->left);
deleteTree(root->right);
delete root;
}
Шаг 5⁚ Тестирование программы
Чтобы проверить правильность работы программы, я задал некоторую последовательность чисел и вывел результаты обхода дерева справа налево. Вот как это выглядит⁚
cpp
int main {
int arr[] {10٫ 5٫ 15٫ 3٫ 7٫ 12٫ 20};
int n sizeof(arr) / sizeof(arr[0]);
Node* root buildTree(arr, n);
printReverseTree(root);
deleteTree(root);
return 0;
}
В результате выполнения программы на экране должно появиться следующее⁚
Результаты обхода дерева справа налево⁚ 20 15 12 10 7 5 3
В итоге, я написал программу на языке C/C , которая строит бинарное дерево на основе заданной последовательности чисел, производит обход дерева справа налево и выводит результаты на экран. После выполнения программы я также очистил память, занятую древовидной структурой.