Сумма значений листьев бинарного дерева
Я написал этот код, и когда я использую печать, я вижу, что я получаю листья. Однако окончательный результат возврата из функции None , а не сумма листьев, которая в этом примере должна быть 7 . Я был бы рад узнать, что здесь не так. Спасибо !
class Node: def __init__(self, val=None): self.left = None self.right = None self.val = val def sum_leafs(tree): if tree is None: return 0 if tree.right and tree.left: sum_leafs(tree.right) sum_leafs(tree.left) elif tree.right or tree.left: if tree.right: sum_leafs(tree.right) elif tree.left: sum_leafs(tree.left) elif tree.right is None and tree.left is None: return sum_leafs(tree.left) + 1 node = Node(10) node.right = Node(2) node.left = Node(11) node.left.right = Node(5) print(sum_leafs(node)) 4 ответа
Вы забыли добавить + при суммировании ветвей (влево / вправо), а также забыли получить доступ к val , что наиболее важно для всей работы.
Далее логика может быть упрощена:
def sum_leafs(tree): if tree is None: return 0 if not tree.right and not tree.left: return tree.val return sum_leafs(tree.right) + sum_leafs(tree.left) Вы не возвращаете правильно рассчитанные суммы листьев. Попробуй это:
class Node: def __init__(self, val=None): self.left = None self.right = None self.val = val def sum_leafs(tree): if tree is None: return 0 elif tree.right and tree.left: return sum_leafs(tree.right) + sum_leafs(tree.left) elif tree.right or tree.left: if tree.right: return sum_leafs(tree.right) elif tree.left: return sum_leafs(tree.left) elif tree.right is None and tree.left is None: return tree.val node = Node(10) node.right = Node(2) node.left = Node(11) node.left.right = Node(5) print(sum_leafs(node)) Вы не складываете суммы и не возвращаете их. Это также можно сделать с помощью метода в классе:
class Node: def __init__(self, val=None): self.left = None self.right = None self.val = val def sum(self): s = 0 if self.left is not None: s += self.left.sum() if self.right is not None: s += self.right.sum() return self.val + s node = Node(10) node.right = Node(2) node.left = Node(11) node.left.right = Node(5) print(node.sum()) Сначала я собираюсь обновить интерфейс Node , чтобы при создании узлов можно было установить ветви left и right .
class Node: def __init__(self, val=None, left=None, right=None): self.left = left self.right = right self.val = val Это позволяет нам создавать тресс более эргономично, например:
t = Node(10, Node(11, None, Node(5)), Node(2)) Теперь мы напишем общую процедуру обхода. Это позволяет нам отделить 1) обход нашего дерева от 2) предполагаемой операции, которую мы хотим выполнить с каждым элементом дерева —
def traverse(tree): if tree is None: return else: yield tree.val yield from traverse(tree.left) yield from traverse(tree.right) Теперь sum_leafs может быть простой программой. Ему больше не нужно заниматься обходом дерева, и вместо этого он может сосредоточиться на преобразовании линейной последовательности значений в желаемую сумму —
def sum_leafs(tree): r = 0 for val in traverse(tree): r += val return r print(sum_leafs(t)) # 28 Или вместо суммирования значений мы могли бы написать функцию search , чтобы найти первое значение, которое передает предикат —
def search(test, tree): for val in traverse(tree): if test(val): return val print(search(lambda x: x < 10, t)) # 5 print(search(lambda x: x >99, t)) # None Или мы могли бы просто собрать каждое значение в список —
print(list(traverse(t))) # [ 10, 11, 5, 2 ] Как видите, удаление логики обхода из каждой функции, которая зависит от нашего дерева, может быть огромной помощью.
Если вам не нравятся генераторы, вы можете написать нетерпеливую версию traverse , которая всегда возвращает list . Разница сейчас в том, что нет возможности частично пройти по дереву. Обратите внимание на сходство этой программы с версией генератора —
def traverse(tree): if tree is None: return [] # Источник
Найдите путь максимальной суммы между двумя листьями в бинарном дереве.
Для заданного бинарного дерева напишите эффективный алгоритм нахождения максимальной суммы пути между любыми двумя его листьями. Предположим, что бинарное дерево не асимметрично и содержит не менее двух узлов.
Например, максимальный суммарный путь в следующем бинарном дереве равен 22:
Простым решением было бы вычислить максимальную сумму пути от узла к листу от левого и правого дочерних элементов для каждого узла в дереве. Максимальный суммарный путь между двумя листьями, который проходит через узел, имеет значение, равное максимальной сумме пути от узла к листу его левого и правого дочерних элементов плюс значение узла. Наконец, рассмотрим максимальное значение среди всех путей с максимальной суммой, найденных для каждого узла в дереве.
Временная сложность этого решения O(n 2 ) как есть n узлов в дереве, и для каждого узла мы вычисляем максимальную сумму пути от узла к листу его левого и правого поддерева, который занимает O(n) время.
Мы можем решить эту задачу за линейное время, обходя дерево снизу вверх. Вместо вычисления максимального суммарного пути от узла к листу левого и правого дочерних элементов для каждого узла в дереве вычислите максимальный суммарный путь между двумя листьями, который проходит через узел за постоянное время. Идея состоит в том, чтобы начать с нижней части дерева и вернуть максимальную сумму пути от узла к листу для каждого узла до его родителя.
Алгоритм может быть реализован следующим образом на C++, Java и Python. Здесь мы передаем путь максимальной суммы по ссылке на функцию (вместо того, чтобы возвращать ее) и обновляем его значение внутри самой функции, используя возвращаемое значение левого и правого поддеревьев.
Источник
Бинарное дерево. Сумма листьев на последнем уровне
Здравствуйте, мне нужно сделать данное задание: Дано бинарное дерево, необходимо вернуть сумму всех его листьев на самом глубоком уровне.
Это не совсем рабочее решение с поиском глубины
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 уровне
Почему выводится неверное кол-во узлов дерева? Помогите найти, что неверно. По заданию: Подсчитать.
Построить и вывести бинарное дерево, степень всех вершин которого, кроме листьев, равна введенному числу
Построить и вывести бинарное дерево, степень всех вершин которого, кроме листьев, равна введенному.
Источник
Бинарное дерево поиска. Сумма "листьев"
Доброго времени суток.
Суть задачи состоит в том, чтобы посчитать сумму элементов, находящих на "листочках" дерева.
Никак не дойдет, как реализацию в main написать.
Функции создания дерева и поиска по дереву есть. Но как эту сумму реализовать?!
Заранее благодарю)
Бинарное дерево поиска: "Библиотека", поиск по автору книги
Есть бинарное дерево поиска.Дерево представляет собой подобие библиотеки.Нужно осуществить поиск по.
Классы "Бинарное дерево" и "Узел" в одном приложении
Компилятор разбушевался((( Пробовала сделать вместо одного класса два класса(Дерево и узел).
Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру
Помогите, не могу понять!( Нужно исходное бинарное дерево превратить в бинарное дерево поиска, при.
Шаблон класса "Бинарное дерево" с насследованием
Здравствуйте! Есть задание сделать шаблон класса "Бинарное дерево". #include <iostream>.
Сообщение было отмечено Maria64 как решение
Решение
int summ(node *elem) { return 1 + (elem->left ? summ(elem->left) : 0) + (elem->right ? summ(elem->right)); }
Бинарное дерево (связный список "сыновей")
Здравствуйте, помогите, пожалуйста, с программой.Нужно реализовать бинарное дерево, представленное.
Бинарное дерево: посчитать количество листьев
Нужно построить бинарное дерево типа *char. В этом бинарном дереве найти количество листьев.
Бинарное дерево: найти количество листьев
Нужно написать функцию, которая находит количество листьев в бинарном дереве
Сформировать бинарное дерево, посчитать количество листьев
помогите написать программу,можно и с использованием классов. сформировать бинарное дерево.
Спор с педагогом, рассудите "Двоичное дерево поиска"
Двоичное дерево поиска Спор у нас на том, что: Если значение одинаково в дереве, то оно исчезает.
Чтения структуры из файла (описать структуру с именем "ORDER": "счет плательщика"; "счет получателя"; "сумма, переводится банковской операцией")
Описать структуру с именем "ORDER", содержащий следующие поля: "Счет плательщика"; "Счет.
Источник