Сумма элементов в бинарном дереве
Требуется реализовать функцию(void findSum(); ) которая определить сумму цифр в значениях тех узлов, которые лежат на пути от корня до максимального элемента.
Построение — реализовал, но как теперь мне определять узлы которые на пути от корня до максимального элемента и сложить их?
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 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175
#define compLT(a,b) (a < b)#define compEQ(a,b) (a == b) #include #include #include using namespace std; typedef int T; // тип элемента typedef struct Node_ { T data; // значение узла struct Node_ *left;// левый потомок struct Node_ *right;// правый потомок struct Node_ *parent;// родитель } Node; Node *root = NULL; //корень бинарного дерева поиска //PROTOTYPE START Node* insertNode(T data); void deleteNode(Node *z); Node* findNode(T data); void printTree(Node *node, int l = 0); void findSum(); //PROTOTYPE END int main(){ setlocale(LC_ALL,""); int i, *a, maxnum; cout "Введите количество элементов maxnum(бинарного дерева) : "; cin >> maxnum; cout endl; a = new int[maxnum]; srand(time(NULL)*1000); // генерация массива for (i = 0; i maxnum; i++) { a[i] = rand(); } cout "Вывод сгенерированной последовательности" endl; for (i = 0; i maxnum; i++) cout a[i] " "; cout endl; cout endl; // добавление элементов в бинарное дерево поиска for (i = 0; i maxnum; i++) { insertNode(a[i]); } cout "Вывод бинарного дерева поиска" endl; printTree(root); cout endl; // поиск элементов по бинарному дереву поиска for (i = maxnum-1; i >= 0; i--) { findNode(a[i]); } cout "Сумма цифр в значениях тех узлов, которые лежат на пути от корня до максимального элемента." endl; findsum(); // очистка бинарного дерева поиска for (i = 0; i maxnum; i++) { deleteNode(findNode(a[i])); } system("pause"); return 0; } //функция выделения памяти для нового узла и вставка в дерево Node* insertNode(T data) { Node *x, *current, *parent; current = root; parent = 0; while (current) { if ( data == current->data ) return (current); parent = current; current = data current->data ? current->left : current->right; } x = new Node; x->data = data; x->parent = parent; x->left = NULL; x->right = NULL; if(parent) if( x->data parent->data ) parent->left = x; else parent->right = x; else root = x; return(x); } //функция удаления узла из дерева void deleteNode(Node *z) z == NULL) return; if (z->left == NULL if (y->left != NULL) x = y->left; else x = y->right; if (x) x->parent = y->parent; if (y->parent) if (y == y->parent->left) y->parent->left = x; else y->parent->right = x; else root = x; if (y != z) { y->left = z->left; if (y->left) y->left->parent = y; y->right = z->right; if (y->right) y->right->parent = y; y->parent = z->parent; if (z->parent) if (z == z->parent->left) z->parent->left = y; else z->parent->right = y; else root = y; free (z); } else { free (y); } } //функция поиска узла, содержащего data Node* findNode(T data) { Node *current = root; while(current != NULL) if(compEQ(data, current->data)) return (current); else current = compLT(data, current->data) ? current->left : current->right; return(0); } //функция вывода бинарного дерева поиска void printTree(Node *node, int l){ int i; if (node != NULL) { printTree(node->right, l+1); for (i=0; i l; i++) cout " "; printf ("%4ld", node->data); printTree(node->left, l+1); } else cout endl; } void findsum() { // node *current = root; //while(current != null) // sum = current->data); //todo cout "Sum equal "; }
Источник
Как найти суммы последовательных узлов в бинарном дереве?
Дано: бинарное дерево (алгоритм дерева написан вручную). Число S. Нужно найти последовательность узлов (только с вверху вниз или наоборот) в бинарном дереве, сумма которых равна S. Например: есть бинарное дерево, а число S = 9. Решение: 3+6, 4+5, 9. п.с. желательно, что бы это был отдельный класс, который имел доступ к классу binTree
#pragma once class binTree < protected: struct Node < int Value; Node * pLeft; Node * pRight; Node * pParent; Node(int x) :Value(x), pLeft(NULL), pRight(NULL), pParent(NULL) <>>; Node * m_pRoot; void InoderTreeWalk(Node * x); Node * TreeSuccessor(Node *x); Node * TreeMin(Node * x); public: binTree(); ~binTree(); virtual void TreeInsert(int k); Node * TreeSearch(Node * X, int k); void ShowTree(); int Root(); >; 2 ответа 2
Задача тянет на олимпиадную, пишу идею.
Решение будет сделано с помощью динамики по дереву.
Для каждого узла в дереве заведём список значений. Инициализация — в листах . Пересчёт снизу вверху. Значение для узла пересчитывается примерно так (текущая вершина U):
for (auto left : U->left->list) U->list.add(left + U->Value); for (auto right: U->left->right) U->list.add(right+ U->Value); U->add(U->Value); U->list->unique(); Я специально пишу псевдокодом, т.к. там может быть любая структура от специфики задачи (list vector set bitset) и т.д.
Для каждой вершины, где в списке есть S будет последовательность ответ, которая заканчивается в ней. Её можно восстановить примерно так. Последовательность однозначно задаётся начальным и конченым элементом. Я верну только начальные.
list fun(Tree *U, int S)< S -= U->Value; list tmp; if (S == 0) tmp.add(U); if (U->left->list.contains(S)) tmp.add(fun(U->left,S); if (U->rigth->list.contains(S)) tmp.add(fun(U->rigth,S); return tmp; > Сложно что-то порядка O(N^2 log N). Оптимизировать можно, но если выводить все последовательности то их может быть примерно столько же. Дальнейшие реализации/оптимизации вам виднее.
Источник
Рекурсия: подсчет суммы элементов бинарного дерева
Создать бинарное дерево. Написать рекурсивную числовую функцию, которая подсчитывает суму элементов дерева.
Поиск суммы нечетных элементов бинарного дерева
Пытаюсь написать программу поиска суммы нечетных элементов бинарного дерева. Получается как то не.
Подсчет вершин бинарного дерева с++
Задача такая: Написать рекурсивную функцию подсчета вершин в дереве. есть такое дерево: #include.
Подсчет количества вершин бинарного дерева
#include "pch.h" #include <iostream> #include <ctime> #include <cstring> using namespace std;.
Рекурсия: подсчитать сумму элементов бинарного дерева
Написать программу, которая создает сбалансированное бинарное дерево. Написать рекурсивную функцию.
Сообщение было отмечено petpy как решение
Решение
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
#include struct node { node* left, *right; int val; node(int v):left(nullptr), right(nullptr), val(v){} }; void tree_add(node*& tr, int val); void tree_clear(node* tr); int tree_sum(const node* tr); int main(void){ node* tr = nullptr; tree_add(tr, 10); tree_add(tr, 200); tree_add(tr, 200); tree_add(tr, 590); std::cout "sum: " tree_sum(tr) std::endl; tree_clear(tr); return 0; } //сумма int tree_sum(const node* tr){ int l, r; if(tr != nullptr){ l = (tr->left != nullptr) ? tree_sum(tr->left) : 0; r = (tr->right != nullptr) ? tree_sum(tr->right) : 0; return l + r + tr->val; } return 0; } //вставка void tree_add(node*& tr, int val){ if(tr == nullptr) tr = new node(val); else if(val tr->val) tree_add(tr->left, val); else tree_add(tr->right, val); } //уаление всех void tree_clear(node* tr){ if(tr != nullptr){ if(tr->left != nullptr) tree_clear(tr->left); if(tr->right != nullptr) tree_clear(tr->right); delete tr; } } Источник
Найдите вертикальную сумму бинарного дерева
Для заданного бинарного дерева выведите его вертикальную сумму. Предположим, что левый и правый потомки узла составляют угол 45 градусов с родителем.
Например, вертикальная сумма показана в следующем бинарном дереве:
1. Использование хеширования
Мы можем легко решить эту проблему с помощью Хеширование. Идея состоит в том, чтобы создать пустую карту, где каждый ключ представляет относительное горизонтальное расстояние узла от корневого узла, а значение на карте поддерживает сумму всех узлов, присутствующих на одном и том же горизонтальном расстоянии. Затем выполните обход предварительного заказа на дереве и обновить сумму для текущего горизонтального расстояния на карте. Для каждого узла повторяйте для его левого поддерева, уменьшая горизонтальное расстояние на единицу, и повторяйте для правого поддерева, увеличивая горизонтальное расстояние на единицу.
На следующем рисунке показано горизонтальное расстояние и уровень каждого узла в приведенном выше бинарном дереве. Окончательные значения на карте будут:
(horizontal distance —> vertical sum)
Ниже приведена программа на C++, Java и Python, которая демонстрирует это:
C++
результат:
9 6 11 6
Java
результат:
9 6 11 6
Python
результат:
9 6 11 6
Временная сложность приведенного выше решения равна O(n.log(n)) и требует O(n) дополнительное пространство, где n размер бинарного дерева.
Упражнение: Уменьшите временную сложность до линейной, используя std::unordered_map / HashMap .
2. Использование вспомогательной структуры данных
Мы можем улучшить временную сложность приведенного выше решения до линейного, используя структуру данных двусвязного списка. Идея состоит в том, чтобы хранить вертикальную сумму двоичного дерева в двусвязном списке, где каждый узел двусвязного списка хранит сумму всех узлов, соответствующих вертикальной линии в двоичном дереве.
Мы начинаем с создания узла двусвязного списка, в котором хранится сумма узлов, присутствующих на вертикальной линии, проходящей через корневой узел. затем node->prev а также node->next будет соответствовать сумме узлов, присутствующих на вертикальной линии, проходящей через левый и правый потомки корневого узла соответственно. Хитрость заключается в рекурсивном построении связанного списка и обновлении узлов с вертикальными суммами по мере прохождения дерева.
Алгоритм может быть реализован следующим образом на C++, Java и Python:
Источник