Бинарное дерево. Сумма листьев на последнем уровне
Здравствуйте, мне нужно сделать данное задание: Дано бинарное дерево, необходимо вернуть сумму всех его листьев на самом глубоком уровне.
Это не совсем рабочее решение с поиском глубины
1 2 3 4 5 6 7 8 9 10 11 12 13 14
-- Дано бинарное дерево, необходимо вернуть сумму всех его листьев на самом глубоком уровне. data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving ( Show, Read, Eq ) -- Returns the Depth of a binary tree treeDepth :: Tree a -> Int treeDepth EmptyTree = 0 treeDepth (Node _ leftBranch rightBranch) = 1 + max (treeDepth leftBranch) (treeDepth rightBranch) -- If Depth = max depth then +x, else +0 sumOfDeepest :: Int a -> Num a => Tree a -> a sumOfDeepest _ EmptyTree = 0 sumOfDeepest depth (Node x left right) = if (depth == treeDepth Tree a) then x + (sumOfDeepest depth left) + (sumOfDeepest depth right) else 0 + (sumOfDeepest depth left) + (sumOfDeepest depth right)
Дано целочисленное бинарное дерево. Найти количество листьев дерева, находящихся на n-м уровне
//Дано целочисленное бинарное дерево. //Найти количество листьев дерева, находящихся на n-м уровне.
Подсчитать количество листьев дерева не на последнем уровне, имеющем листья.
Добрый день! Не могу разобраться со следующим: нужно подсчитать количество листьев не на последнем.
Бинарное дерево поиска. Сумма «листьев»
Доброго времени суток. Суть задачи состоит в том, чтобы посчитать сумму элементов, находящих на.
Бинарное дерево: посчитать количество листьев
Нужно построить бинарное дерево типа *char. В этом бинарном дереве найти количество листьев.
Преобразуем дерево в список пар (значение, уровень). Дальше задача сводится к спискам.
1 2 3 4 5 6 7 8 9 10 11 12 13 14
data Tree a = Empty | Node a (Tree a) (Tree a) deriving ( Show, Read, Eq ) tree2arr :: (Num a) => Tree a -> Int -> [(a,Int)] tree2arr Empty n = [(0,n)] tree2arr (Node x left right) n = (x,n):(tree2arr left (n+1))++(tree2arr right (n+1)) sumlev :: (Num a) => [(a,Int)] -> a sumlev xs = sum $ map fst $ filter (\ (s,l) -> l==ml) xs where ml = (maximum $ map snd xs)-1 task t = sumlev $ tree2arr t 0 main = print $ task (Node 111 (Node 222 Empty Empty) (Node 666 Empty (Node 777 Empty Empty) ))
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
data Tree a = Empty | Node a (Tree a) (Tree a) deriving ( Show, Read, Eq ) sumOfDeepest :: Num a => Tree a -> a sumOfDeepest tree = byLvl [] [tree] where byLvl p t = case concatMap (\case Node _ l r -> [l,r] _ -> []) t of [] -> foldr (\n s -> case n of Node v _ _ -> s+v _ -> s) 0 p nxt -> byLvl t nxt main :: IO () main = do let testdata = (Node 111 (Node 222 Empty (Node 333 Empty (Node 444 Empty Empty))) (Node 555 Empty (Node 666 (Node 777 Empty Empty) Empty))) :: Tree Int print $ sumOfDeepest testdata Бинарное дерево: найти количество листьев
Нужно написать функцию, которая находит количество листьев в бинарном дереве
Можно ли заполнить бинарное дерево, начиная с листьев?
По заданию нужно вывести на экран своеобразную турнирную таблицу: вводятся 2^n имен команд, они.
Сформировать бинарное дерево, посчитать количество листьев
помогите написать программу,можно и с использованием классов. сформировать бинарное дерево.
Бинарное дерево, число вершин на n уровне
Почему выводится неверное кол-во узлов дерева? Помогите найти, что неверно. По заданию: Подсчитать.
Построить и вывести бинарное дерево, степень всех вершин которого, кроме листьев, равна введенному числу
Построить и вывести бинарное дерево, степень всех вершин которого, кроме листьев, равна введенному.
Источник
Дано дерево. Подсчитать сумму листьев
Здравствуйте! Если такая тема уже была — прошу скинуть ссылку.
Для каждого задания создать дерево, вывести его на экран, используя симметричный обход для случая дерева бинарного поиска и прямой обход для идеально сбалансированного дерева, выполнить задание и вывести результат на экран. Использовать динамические структуры. Выполнив задание, вывести новое дерево.
Дано дерево. Подсчитать сумму листьев.
Если кто-то поможет — просьба, оставьте заметки в коде к основным действиям.
Заранее благодарю.
Создать N-дерево и посчитать сумму листьев (нужно добавить ввод с клавиатуры и из файла)
Добрый день, нужна ваша помощь. Задача такая, создать N-дерево (дерево с любым кол-вом.
Бинарное дерево: найти количество листьев
Нужно написать функцию, которая находит количество листьев в бинарном дереве
Бинарное дерево: посчитать количество листьев
Нужно построить бинарное дерево типа *char. В этом бинарном дереве найти количество листьев.
Сформировать бинарное дерево, посчитать количество листьев
помогите написать программу,можно и с использованием классов. сформировать бинарное дерево.
Реализуйте дерево целых чисел, добавление и удаление листьев
Добрый день. Ребят, помогите пожалуйста. Дали вот такое задание: Реализуйте дерево целых.
Сообщение от switcher11 
Сообщение было отмечено switcher11 как решение
Решение
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
#include #include #include #include struct node { node(int d) : data(d){} int data{}; node* left{}, *right{}; }; struct tree { tree() = default; tree(std::initializer_listint> il) { for (auto val : il) { insert(val); } } void insert(int d) { if (!root) { root = new node(d); } else { node* tmp = root; while (true) { if (tmp->data > d && tmp->left) { tmp = tmp->left; } else if(tmp->data d && tmp->right) { tmp = tmp->right; } else { break; } } if (tmp->data > d) { tmp->left = new node(d); } else { tmp->right = new node(d); } } } void lsum() { int sum{}; std::stacknode*> stk; if (root) stk.push(root); while (!stk.empty()) { while (stk.top()->left) { stk.push(stk.top()->left); } while (!stk.empty()) { auto tmp = stk.top(); stk.pop(); if (!tmp->left && !tmp->right) sum += tmp->data; if (tmp->right) { stk.push(tmp->right); break; } } } std::cout <"sum: " <"\n"; } void print() { std::stacknode*> stk; if(root) stk.push(root); while (!stk.empty()) { while (stk.top()->left) { stk.push(stk.top()->left); } while (!stk.empty()) { auto tmp = stk.top(); stk.pop(); std::cout - >data <" "; if (tmp->right) { stk.push(tmp->right); break; } } } std::cout <"\n"; } node* root{}; }; int main() { tree tr{1,-33,44,2,-3,55}; tr.print(); tr.lsum(); } Источник
Вывести сумму значений всех листьев данного дерева
доброго всем времени суток)
дали нам опять задачи и все бы хорошо,но про бинарные деревья я ничего не знаю(
условие задачи такое:дан указатель Р1 на корень не пустого дерева. вывести сумму значений всех листьев данного дерева
я правильно поняла,что мне надо спуститься(или подняться) от корня к поддереву,затем к листьям и затем подсчитать их сумму?
если это так то подскажите как это делать
заранее спасибо))))
Вывести разность значений всех листьев бинарного дерева
Дан указатель P1 на корень непустого дерева. Вывести разность значений всех листьев данного.
Вывести элементы из всех листьев дерева
Здравствуйте, помогите пожалуйста с заданием по прологу, нужно вывести элементы из всех листьев.
Вычислить произведение всех отрицательных листьев дерева
подсчитать произведение всех отрицательных листьев дерева, заданного списком если кто знает как.
Turbo Prolog: подсчитать сумму всех вершин данного дерева, значения которых принадлежат заданному диапазону
Помогите,пожалуйста,кто в этом разбирается. Нужно создать предикат,подсчитывающий сумму всех вершин.
Сообщение было отмечено Памирыч как решение
Решение
type //Указатель на узел. TPNode = ^TNode; //Узел. TNode = record Data : Integer; PLeft, PRight : TPNode; end;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
function CalcSum(const aPNode : TPNode) : Integer; var Sum : Integer; begin if aPNode = nil then begin CalcSum := 0; Exit; end; Sum := 0; //Если узел оказался листом, то берём его значение. if (aPNode^.PLeft = nil) and (aPNode^.PRight = nil) then Sum := aPNode^.Data //Если узел не является листом, то запускаем рекурсию по его веткам. else begin if aPNode^.PLeft <> nil then Sum := Sum + CalcSum(aPNode^.PLeft); if aPNode^.PRight <> nil then Sum := Sum + CalcSum(aPNode^.PRight); end; CalcSum := Sum; end;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
. var PTree : TPNode; //Корень дерева. Sum : Integer; . begin . //Подсчёт суммы значений всех листьев дерева. Sum := CalcSum(PTree); Writeln('Сумма значений листьев дерева = ', Sum); //Процедура удаления дерева из памяти. TreeFree(PTree); Readln; end.
Источник
Найдите путь максимальной суммы между двумя листьями в бинарном дереве.
Для заданного бинарного дерева напишите эффективный алгоритм нахождения максимальной суммы пути между любыми двумя его листьями. Предположим, что бинарное дерево не асимметрично и содержит не менее двух узлов.
Например, максимальный суммарный путь в следующем бинарном дереве равен 22:
Простым решением было бы вычислить максимальную сумму пути от узла к листу от левого и правого дочерних элементов для каждого узла в дереве. Максимальный суммарный путь между двумя листьями, который проходит через узел, имеет значение, равное максимальной сумме пути от узла к листу его левого и правого дочерних элементов плюс значение узла. Наконец, рассмотрим максимальное значение среди всех путей с максимальной суммой, найденных для каждого узла в дереве.
Временная сложность этого решения O(n 2 ) как есть n узлов в дереве, и для каждого узла мы вычисляем максимальную сумму пути от узла к листу его левого и правого поддерева, который занимает O(n) время.
Мы можем решить эту задачу за линейное время, обходя дерево снизу вверх. Вместо вычисления максимального суммарного пути от узла к листу левого и правого дочерних элементов для каждого узла в дереве вычислите максимальный суммарный путь между двумя листьями, который проходит через узел за постоянное время. Идея состоит в том, чтобы начать с нижней части дерева и вернуть максимальную сумму пути от узла к листу для каждого узла до его родителя.
Алгоритм может быть реализован следующим образом на C++, Java и Python. Здесь мы передаем путь максимальной суммы по ссылке на функцию (вместо того, чтобы возвращать ее) и обновляем его значение внутри самой функции, используя возвращаемое значение левого и правого поддеревьев.
Источник