Haskell - траверс дерева и вывода в списках

У меня есть этот кусок кода, который выводит узлы после прохождения, без какого-либо приемлемого порядка:Haskell - траверс дерева и вывода в списках

preorder :: Tree a -> [a] 
preorder Empty = [] 
preorder (Branch x e d) = [x]++(preorder e)++(preorder d) 

createTree = Branch 'A' 
        (Branch 'B' 
          (Branch 'E' Empty Empty) 
          (Branch 'B' Empty Empty) 
       ) 
        (Branch 'A' 
          (Branch 'E' Empty Empty) 
          (Branch 'A' Empty Empty) 
       )

Применение preorder к createTree выходов:

ABEBAEA

То, что я хотел бы иметь, - это список всех путей, идущих от корня:

["ABE","ABB","AAE","AAA"]

Я понятия не имею, как это сделать, я новичок в Haskell!

Благодарим вас за помощь, которая может быть предоставлена.

источник

2015-01-01 skills

Я не вижу, что 'функция preorder' имеет отношение к этому. – leftaroundabout

Это приемлемый порядок: префиксный порядок, ther также порядок инфикс и постфикс. Но вы, вероятно, хотите отобразить путь к каждому узлу, поэтому вы, вероятно, (именно так я понял ваш вопрос) также нуждаются в использовании стека для достижения этого. – Yoda

Обратите внимание, что ваш пример не уточняет, какими должны быть пути 'Branch 'A' Empty (Branch 'B' Empty Empty)'. Можно было бы сказать '[" AB "]' или '[" A "," AB "]'. – chi

Это упражнение сводится к тому:

Каковы пути для пустого дерева?
Позвольте e и d быть деревьями, каждый из которых имеет свои списки путей ep и dp, соответственно. Как вычислить пути для дерева, помеченного x и имеющего e и d как поддеревья?

Так,

paths :: Tree a -> [[a]] 
paths Empty = ??? 
paths (Branch x e d) = ??? -- use x,ep,dp accordingly 
     where ep = paths e 
      dp = paths d

Как дополнительный намек, связанный с вашим собственным примером:

[ 'A':xs | xs <- ["BE","BB"] ] = [ "ABE" , "ABB" ]

Обратите внимание, что ["BE","BB"] являются путями для вашего первого поддерева.

источник

2015-01-01 23:53:47 chi

paths :: Tree a -> [[a]] 
paths Empty     = [[]] 
paths (Branch x Empty d ) = map (x:) $ paths d 
paths (Branch x e  Empty) = map (x:) $ paths e 
paths (Branch x e  d ) = map (x:) $ paths e ++ paths d

I.e. просто добавьте x к каждому подпути.

createTree = Branch 'A' 
        (Branch 'B' 
          (Branch 'E' Empty (Branch 'A' Empty Empty)) 
          (Branch 'B' Empty Empty) 
       ) 
        (Branch 'A' 
          (Branch 'E' Empty Empty) 
          (Branch 'A' Empty Empty) 
       ) 

main = print $ paths createTree

печатает ["ABEA","ABB","AAE","AAA"]

источник

2015-01-01 23:58:54 user3237465

Haskell - траверс дерева и вывода в списках

ответ

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