Truy tìm cây?

Question

Tôi có một kiểu cho một cây như vậy:

data Tree a = EmptyTree | Tree a [Tree a] deriving (Show, Ord, Eq) 

freeTree :: Tree Integer 
freeTree = Tree 2 [Tree 5 [], Tree 6 [Tree 8 [], Tree 9 []], Tree 7 []] 

main = print freeTree 

Những gì tôi đang cố gắng làm là viết một hàm có thể dùng nói như vậy:

trace freeTree 

Và những gì một dấu vết trên cây này sẽ quay trở lại là: [2],[2,5],[2,6],[2,7],[2,6,8],[2,6,9]

về cơ bản những gì nó làm là:

Giữ một danh sách các nút đã có trên 'đống' (gốc không ở mỗi độ sâu đã đưa chúng ta đến đây). Mỗi khi bạn đạt đến một nút mới, hãy thêm danh sách đó là danh sách các nút chồng ++ current_node vào danh sách kết quả.

Có ai có thể đưa ra lời khuyên nào về cách thực hiện việc này không?

Cảm ơn

Answer 1

A đầu tiên (thực hiện không thực sự hiệu quả):

trace :: Tree a -> [[a]] 
trace t = trace' [([],t)] [] 

type Level a = [([a],Tree a)] 

trace' :: Level a -> Level a -> [[a]] 
trace' [] [] = []           -- current and next level empty? We're done! 
trace' [] l = trace' l []         -- current level exhausted? Next level becomes current level and we construct a new level 
trace' ((_,EmptyTree):ts) lu = trace' ts lu    -- currently an EmptyTree? Skip it 
trace' ((h,Tree t c):ts) lu = ht : trace' ts (lu++el)  -- currently a tree? Enumerate and add childs 
    where ht = h++[t] 
      el = map (\x -> (ht,x)) c 

Thuật toán sử dụng hai Level a 's, mức hiện tại và cấp độ tiếp theo. Bạn luôn luôn lặp đầu tiên trên mức hiện tại và cho mỗi mục ở cấp độ hiện tại, bạn thêm các con của cấp đó vào cấp độ tiếp theo cho đến khi mức hiện tại bị cạn kiệt. Vấn đề duy nhất với cách tiếp cận này là các hoạt động ++ là khá tốn kém, đặc biệt là kể từ khi chúng được áp dụng kết hợp trái và không đúng. Người ta có thể làm cho nó một chút bộ nhớ hiệu quả hơn bằng cách sử dụng một đại diện danh sách tuple nhỏ gọn hơn.

Bạn có thể làm cho nó hiệu quả hơn bằng cách sử dụng một hàng đợi FIFO, ví dụ this one (chúng ta hãy giả định ít nhất là giao diện cho tất cả các hàng đợi là như nhau, vì vậy trong trường hợp bạn thích nhau, bạn có thể trao đổi những nơi).

Trong trường hợp đó mã sẽ đọc:

type Level a = [([a],Tree a)] 
type LevelFiF a = FIFO ([a],Tree a) 

trace' :: Level a -> LevelFiF a -> [[a]] 
trace' [] ln | isEmpty ln = [] 
      | otherwise = trace' (toList ln) empty 
trace' ((h,Tree t c):ts) ln = ht : trace' ts (foldl (flip enqueue) ln el) 
    where ht = h++[t] 
      el = map (\x -> (ht,x)) c 
trace' (_:ts) ln = ht : trace' ts ln 

Bạn có lẽ có thể làm cho nó hiệu quả hơn sử dụng một trong hàng đợi monadic Haskell là tốt.

Answer 2

Về cơ bản bạn muốn duy trì trạng thái qua các cuộc gọi đệ quy để trace. Vì vậy, hãy xem xét một chữ ký chức năng như thế này:

-- First argument is the tree to trace 
-- Second argument is the accumulated route 
trace :: Tree a -> [a] -> [[a]] 

Với cấu trúc này bạn đang tìm kiếm chiều sâu trên cây này một cách hiệu quả.

Answer 3

Chúng ta có thể nghĩ rằng chúng tôi có một trie nơi mỗi nút đánh dấu một từ hợp lệ, và sau đó là công việc là để tranh thủ dòng chữ:

trace :: Tree a -> [[a]] 
trace (Tree a ts) = [a] : map (a:) (trace =<< ts) 
trace Empty  = [] 

tree1 = Tree 1 [Tree 2 [ Tree 3 [ Tree 4 [Tree 5 [] ]]]] 
tree2 = Tree 2 [Tree 5 [], Tree 6 [Tree 8 [], Tree 9 []], Tree 7 []] 

-- trace tree1 = [[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5]] 
-- trace tree2 = [[2],[2,5],[2,6],[2,6,8],[2,6,9],[2,7]] 

Đây là một giải pháp chiều sâu-đầu tiên có thể được lười biếng xử lý với không gian chỉ cần thiết cho từ hiện tại. Nó không trả về các từ theo thứ tự chính xác mà bạn đã chỉ định; nếu theo thứ tự chiều rộng đầu tiên nghiêm ngặt là rất quan trọng, bạn nên đi cho chiều sâu lặp đi lặp lại:

traceIDeep :: Tree a -> [[a]] 
traceIDeep t = concat $ takeWhile (not . null) $ map (`lvl` t) [0..] 
    where 
    lvl 0 (Tree a ts) = [[a]] 
    lvl l (Tree a ts) = map (a:) (lvl (l - 1) =<< ts) 
    lvl _ Empty  = [] 

-- Now we have bfs order: 
-- trace tree2 = [[2],[2,5],[2,6],[2,7],[2,6,8],[2,6,9]]