Максимальная глубина дерева в Haskell

-3

Я дал это определение типа:Максимальная глубина дерева в Haskell

data Tree = Leaf Char | Branch2 Char Tree Tree | Branch3 Char Tree Tree Tree

Как я могу написать метод, который дает мне максимальную длину пути дерева (количество узлов в пути)?

источник

2014-01-20 Chryb

В будущем, пожалуйста, продемонстрируйте все попытки, которые вы предприняли для решения проблемы, с которой вы столкнулись. Stackoverflow - это место, где можно получить помощь по конкретной проблеме, а не место, чтобы заставить кого-то написать свой код для вас. – bheklilr

Может ли это дерево удерживать 2 элемента? Можно ли удалить элемент из дерева из трех элементов? Мы либо должны добавить 'Branch1 Char Tree' там, либо просто« Empty »в конце концов. –

Для этого нужно написать рекурсивную функцию. Для каждого конструктора Tree вам понадобится другой случай в вашей функции. Начнем с того, вы знаете, что глубина любой Leaf является 1, так

maxDepth :: Tree -> Int 
maxDepth (Leaf _) = 1 
maxDepth (Branch2 c left right) = maximum [???] 
maxDepth (Branch3 c left center right) = maximum [???]

Я дам вам закончить остальные функции. Вы могли бы сделать это несколько разных способов (например, используя max вместо maximum).

источник

2014-01-20 16:44:20 bheklilr

Обычно лист имеет глубину '0', а не' 1'. – kosmikus

@kosmikus В этом случае лист содержит данные. Это определение дерева не включает пустую ветвь. Если бы я подсчитывал количество хранимых в этом дереве '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' s ' – bheklilr

Я не вижу, что связано с наличием данных или желанием подсчитать количество символов. Глубина узла обычно является минимальной длиной пути к корню. Если дерево является единственным листом, то лист является корнем, а путь имеет длину '0'. – kosmikus

depth :: Tree -> Int 
depth (Leaf _) = 1 
depth (Branch2 c left right) = max((depth(left) + 1) (depth(right) + 1)) 
depth (Branch3 c left center right) = max(max((depth(left) + 1) (depth(right) + 1)) (depth(center) + 1))

Это правильно? Извините, я не так хорош в рекурсивном программировании.

источник

2014-01-20 16:56:27 Chryb

Этот код не компилируется. Синтаксис 'max ((глубина (слева) + 1) (глубина (справа) + 1))' неверна. Рекомендуемый стиль заключается в том, чтобы использовать только круглые скобки при группировке подвыражения, которое должно быть единственным аргументом для другой функции, и избегать круглых скобок, когда они являются избыточными. Вместо этого вы можете написать его как 'max (глубина слева + 1) (глубина справа + 1)' – bheklilr

Хорошо спасибо. Но правильно ли функция? – Chryb

Выглядит хорошо. Вы протестировали его? Это работает? –

с lazy corecursive breadth-first tree traversal:

treedepth tree = fst $ last queue 
    where 
    queue = (1,tree) : gen 1 queue 

    gen 0 p      = [] 
    gen len ((d,Leaf _  ) : p) = gen (len - 1) p 
    gen len ((d,Branch2 _ l r) : p) = (d+1,l) : (d+1,r) : gen (len + 1) p 
    gen len ((d,Branch3 _ l c r) : p) = (d+1,l) : (d+1,c) : (d+1,r) : gen (len + ??) p

изменяя его на глубину первого обхода будет превратить его в обычный рекурсии.

источник

2014-01-20 17:42:33

+1 это, безусловно, правильный подход. –

@ChrisTaylor либо это, либо рекурсивный код глубины, [в зависимости от формы дерева] (http://stackoverflow.com/a/21216809/849891), если он известен заранее. :) –

Я бы, вероятно, написал рекурсивное решение с помощью продолжения прохождения.

depth :: Tree -> Int 
depth t = go t id 
where 
    go (Leaf _)   k = k 0 
    go (Branch2 _ l r) k = go l $ \dl -> go r $ \dr -> k (1 + max dl dr) 
    go (Branch3 _ l m r) k = go l $ \dl -> go m $ \dm -> go r $ \dr -> k (1 + max dl (max dm dr))

источник

2014-01-20 18:47:52

Я считаю, что это работает, но я никогда не вижу ничего подобного ^^. Вы можете это объяснить? – Chryb

@Chryb посмотреть [здесь] (http://stackoverflow.com/a/21205572/849891) для объяснений. –

Максимальная глубина дерева в Haskell

ответ

Смежные вопросы