Обнаружение количества четных путей от корня в дереве

Question

Я пытаюсь получить функцию, которая считает все пути от корня до листа, который имеет четное число узлов (считая корень и лист) Мое дерево выглядит следующим образом:

data Tree = Leaf Int | Node Int Tree Tree 

все я получил до сих пор является функцией, которая подсчитывает все узлы в дереве, которое достаточно легко:

countNodes (Leaf _) = 1 
countNodes (Node _ x y) = 1+ countNodes x + countNodes y 

Теперь я увидел кучу вопросов, которые имеют дело с деревьями но я чувствовал, что никакой ответ мне не помог, поэтому я просто спрошу себя. Как сделать часть остановки функции, когда лист достигнут? Я знаю, что это связано с моей проблемой, чтобы думать с рекурсиями.

Что я пытался сделать, так это составить список всех путей из корня, но я всегда получаю функцию, которая получает все элементы в дереве и каким-то образом объединяет их. Мне не хватает чего-то простого, пожалуйста, помогите. (Или ссылку мне ответ, который делает именно то, что я хочу)

Answer 1

Вероятно, проще вычислить как число , так и количество нечетных путей.

evenAndOdd (Leaf _) = (0, 1) 
evenAndOdd (Node _ l r) = let 
    (el, ol) = evenAndOdd l 
    (er, or) = evenAndOdd r 
    in (ol+or, el+er) 

Если вам действительно нужно, вы можете определить функцию в терминах этого, чтобы считать только четные пути.

evenOnly = fst . evenAndOdd 

Answer 2

Я думаю, что самый простой способ будет сделать тип данных, который может описать путь через дерево:

data Path = L Path | R Path | End deriving (Eq, Show) 

Этот тип является в основном список, но с двумя конструкторами prepend, чтобы сказать вам, либо идти влево, либо идти вправо. Это позволяет вам искать элементы по пути, или вы можете написать функцию, которая дает вам список всех путей в дереве.

-- Note that this can fail: lookupNode (Leaf 1) (L End) == Nothing 
lookupNode :: Tree -> Path -> Maybe Tree 

allPaths :: Tree -> [Path] 

Если вы можете написать функцию allPaths, то вы можете написать функцию, которую вы хотите на нем. Чтобы начать, просто начать с перечисления базовых случаев:

allPaths (Leaf _) = [End] 
allPaths (Node _ left right) = _ 

Чтобы заполнить отверстие _, подумайте о том, что это значит перечислить все пути, начинающиеся на Node и рекурсии вниз left. Вы должны были бы иметь L в начале всех этих путей, так что вы можете поместить следующее в там

allPaths (Node _ left right) = (map L $ allPaths left) 

Кроме того, вам нужно будет обрабатывать right дерево:

allPaths (Node _ left right) = 
    (map L $ allPaths left) ++ 
    (map R $ allPaths right) 

Так Сейчас:

> let tree = 
    Node 1 
     (Node 2   -- L _ 
      (Leaf 3)  -- L (L End) 
      (Node 4  -- L (R _) 
       (Leaf 5) -- L (R (L End)) 
       (Leaf 6) -- L (R (R End)) 
      ) 
     ) 
     (Leaf 7)   -- R End 
> allPaths tree 
[L (L End),L (R (L End)), L (R (R End)),R End] 

Теперь, чтобы найти Leaf с с четным числом узлов над ними, сначала написать функцию, которая вычисляет путь русификатор го:

pathLength :: Path -> Int 
pathLength End = 0 
pathLength (L rest) = 1 + pathlength rest 
pathLength (R rest) = 1 + pathLength rest 

evenNodeCountPaths :: Tree -> [Path] 
evenNodeCountPaths tree = filter (even . pathLength) $ allPaths tree 

---

Примечание: Можно сделать это с

data Dir = L | R | End 
type Path = [Dir] 

Но это может привести к неправильным путям, как [End, End, L, R, End], который только не имеет никакого смысла. По этой причине я решил пойти по списку data Path. Вы должны написать свою собственную функцию pathLength, но эта формулировка делает невозможным наличие неверных путей.