하스켈 - 목록

Question

내가 어떤 이해 순서없이, 통과 후 노드를 출력 코드의이 비트를 가지고에 나무와 출력 트래버스 :

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) 
       ) 

preordercreateTree에 출력 적용 :

ABEBAEA 

을 내가 원하는 것은 루트에서가는 모든 경로 목록입니다.

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

나는 이것을 어떻게하는지에 관해 모른다, 나는 하스켈에서의 초심자 다!

제공되는 모든 도움에 감사드립니다. 이것에

Answer 1

이 운동 양 : 빈 트리의 경로는 무엇

• ?
• 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"] 것을 첫 번째 하위 트리에 대한 경로입니다.

Answer 2

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 

.l.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"]