Необходимо построить дерево двоичного поиска, элементами которого являются целые числа. Данные хранятся в файле (в нём записано через пробел в одну строку числа (например: 1 2 3 6 9)).
Вывести элементы дерева на экран используя следующие обходы дерева:
а) инфиксным обходом
б) постфиксным обходом
в) префиксным обходом
Также нужно реализовать следующие функции:
г) Найти сумму элементов дерева
д) Найти произведение элементов кратных 3
Для решения используется рекурсивный метод.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 |
#include<iostream> #include<fstream> //библиотека для работы с файлами using namespace std; int c = 0, z = 1; //нужно для счётчика сложения и умножения typedef struct Node { //задаём структуру нашего дерева int data; Node *left, *right; }tree; tree *first(int x, tree *p) { //верхушка дерева p = new tree; p->data = x; p->left = p->right = NULL; return p; } tree *add(int x) { //добавляем tree *p; p = new tree; p->data = x; p->left = p->right = NULL; return p; } void search(int x, tree *p) { //ищем и распределяем согласно определению бинарного дерева if (x < p->data) { if (p->left != NULL) { //пока не встречен NULL вызываем search search(x, p->left); } else { p->left = add(x); //в левую ветку добавляем x } } else { if (x > p->data) { if (p->right != NULL) { //пока не встречен NULL вызываем search search(x, p->right); } else { p->right = add(x); //в правую ветку добавляем x } } } } void infix(tree *p) { //инфиксный способ if (p->left != NULL) { infix(p->left); } cout << p->data << " " << endl; if (p->right != NULL) { infix(p->right); } } void prefix(tree *p) { //префиксный способ cout << p->data << " " << endl; if (p->left != NULL) { infix(p->left); } if (p->right != NULL) { infix(p->right); } } void postfix(tree *p) { //постфиксный способ if (p->left != NULL) { infix(p->left); } if (p->right != NULL) { infix(p->right); } cout << p->data << " " << endl; } int sum(tree *p) { //сумма всех элементов дерева if (p->left != NULL) { sum(p->right); } if (p->right != NULL) { sum(p->right); } c = c + p->data; return c; } int proiz(tree *p) { //произведение всех элементов кратных 3 if (p->left != NULL) { proiz(p->right); } if (p->right != NULL) { proiz(p->right); } if (p->data % 3 == 0) { z = z * p->data; } return z; } int main() { ifstream in("input.txt"); //читаем наш файл (в нём через пробел записаны числа(например, 1 2 3 5 9)) int a; in >> a; //передаём первый элемент tree *root = NULL; //начинаем дерево с нуля root = first(a, root); //записываем в root верхушку дерева (дерево начинает "расти") while (!in.eof()) { //проходим по всему файлу и отправляем каждое значение в функцию search in >> a; search(a, root); } in.close(); //закрыли файл cout << "INFIX\n"; infix(root); //инфиксный способ cout << "\nPOSTFIX\n"; postfix(root);//постфиксный способ cout << "\nPREFIX\n"; prefix(root);//префиксный способ cout << "\nCount\n"; int q = sum(root);//сумма элементов cout << q << endl; cout << "\nProizvedenie\n"; int w = proiz(root);//произведение элементов кратных 3 cout << w << endl; system("pause"); return 0; } |
1 thought on “Бинарное дерево”
Paul
(14.07.2019 - 15:04)Подскажите пожалуйста как этот алгоритм переделать для подсчета не всех элементов а только вершин имеющих потдеревья одинаковой высоты с выводом списка потомков.