我需要幫助在Haskell上顯示AVL樹

Question

data AVL t = Empty | Node t (AVL t) (AVL t) Int 
       deriving (Eq, Ord, Show) 


insertNode :: (Ord a) => a -> AVL a -> AVL a 
insertNode x Empty = Node x Empty Empty 0 
insertNode x (Node n left right balanceFactor) 
    | x < n = let leftNode = insertNode x left 
       in 
       balanceTree (Node n leftNode right ((treeHeight leftNode) - (treeHeight right))) 
    | otherwise = let rightNode = insertNode x right 
        in 
        balanceTree (Node n left rightNode ((treeHeight left) - (treeHeight rightNode))) 

findNode :: AVL a -> a 
findNode Empty = error "findNode from Empty" 
findNode (Node a _ _ _) = a 

findLeftNode :: AVL a -> AVL a 
findLeftNode Empty = error "findLeftNode from Empty" 
findLeftNode (Node _ left _ _) = left 

findRightNode :: AVL a -> AVL a 
findRightNode Empty = error "findRightNode from Empty" 
findRightNode (Node _ _ right _) = right 

findBalanceFactor :: AVL a -> Int 
findBalanceFactor Empty = 0 
findBalanceFactor (Node _ _ _ bf) = bf 

treeHeight :: AVL a -> Int 
treeHeight Empty = 0 
treeHeight (Node _ left right _) = 1 + (max (treeHeight left) (treeHeight right)) 

balanceTree :: AVL a -> AVL a 
balanceTree Empty = Empty 
balanceTree (Node r Empty Empty bf) = Node r Empty Empty bf 
balanceTree (Node r left right bf) 
    | bf == -2 && rbf == -1 = let rl = (findLeftNode right) 
           in 
           (Node (findNode right)                -- This is for the 
           (Node r left rl ((treeHeight left) - (treeHeight rl)))        -- "right right" case 
           (findRightNode right) 
           ((1 + (max (treeHeight left) (treeHeight rl))) - (treeHeight (findRightNode right))) 
           ) 
    | bf == -2 && rbf == 1 = let rl = findLeftNode right 
           rr = findRightNode right 
          in 
           (Node (findNode (rl))                 -- This is for the 
           (Node r left (findLeftNode rl) ((treeHeight left) - (treeHeight (findLeftNode rl)))) -- "right left" case 
           (Node (findNode right) (findRightNode rl) rr ((treeHeight (findRightNode rl)) - (treeHeight rr))) 
           ((max (treeHeight left) (treeHeight (findLeftNode rl))) - (max (treeHeight (findRightNode rl)) (treeHeight rr))) 
          ) 
    | bf == 2 && lbf == 1 = let lr = findRightNode left 
          in 
          (Node (findNode left)                 -- This is for the 
          (findLeftNode left)                 -- "left left" case 
          (Node r lr right ((treeHeight lr) - (treeHeight right))) 
          ((treeHeight (findLeftNode left)) - (1 + (max (treeHeight lr) (treeHeight right)))) 
          ) 
    | bf == 2 && lbf == -1 = let lr = findRightNode left 
           ll = findLeftNode left 
          in 
           (Node (findNode lr)                    -- This is for the 
           (Node (findNode left) ll (findLeftNode lr) ((treeHeight ll) - (treeHeight (findLeftNode lr)))) -- "left right" case 
           (Node r (findRightNode lr) right ((treeHeight (findRightNode lr)) - (treeHeight right))) 
           ((max (treeHeight ll) (treeHeight (findLeftNode lr))) - (max (treeHeight(findRightNode lr)) (treeHeight right))) 
          ) 
    | otherwise = (Node r left right bf) 
    where rbf = findBalanceFactor right 
      lbf = findBalanceFactor left 

這是我實現AVL樹的當前狀態。正常的輸入通常是：

insertNode 4 (Node 2 (Node 1 Empty Empty 0) (Node 3 Empty Empty 0) 0) 

這導致：

Node 2 (Node 1 Empty Empty 0) (Node 3 Empty (Node 4 Empty Empty 0) (-1)) (-1) 

我想現在有一個功能，以在一個整潔的方式直接在上面顯示輸入的樹，例如，樹：

2 
1 
    Empty 
    Empty 
3 
    Empty 
    4 
    Empty 
    Empty 

有沒有人有任何建議，如何可以實施？我希望僅顯示節點，並且一旦到達分支的末尾，它將打印「空白」。我打了一堵磚牆，並嘗試了幾次嘗試，但都取得了一些成功。

編輯：嗨，大家好，謝謝你的快速反應。你的建議可以工作，但是，我希望在不使用包或庫的情況下顯示樹的實現。對不起，沒有澄清這一點！

Answer 1

您可以使用您的第一個AVL樹轉換到 一個Data.Tree.Tree使用Data.Tree庫：

import qualified Data.Tree as T 

data AVL t = Empty | Node t (AVL t) (AVL t) Int 
       deriving (Eq, Ord, Show) 

toTree :: Show t => AVL t -> T.Tree String 
toTree Empty = T.Node "Empty" [] 
toTree (Node t left right a) 
    = T.Node (show t ++ " " ++ show a) [toTree left, toTree right] 

avl = Node 2 (Node 1 Empty Empty 0) (Node 3 Empty (Node 4 Empty Empty 0) (-1)) (-1) 

test = putStrLn $ T.drawTree (toTree avl) 

運行test打印：

2 -1 
| 
+- 1 0 
| | 
| +- Empty 
| | 
| `- Empty 
| 
`- 3 -1 
    | 
    +- Empty 
    | 
    `- 4 0 
     | 
     +- Empty 
     | 
     `- Empty 

Answer 2

你是什麼尋找是一個漂亮的打印機！我總是使用Hackage上的「 pretty 」包。

import Text.PrettyPrint 

你的樹是一個非常簡單的結構，所以我只需要一次性定義它。雖然在Text.PrettyPrint有很多有用的組合器，所以檢查出來！它們在GHCi中也非常容易使用，所以當你不理解文檔時，只需旋轉即可。

prettyTree :: Show t => AVL t -> Doc 
prettyTree Empty   = text "Empty" 
prettyTree (Node t l r _) = text (show t) 
          $+$ nest 1 (prettyTree l) 
          $+$ nest 1 (prettyTree r) 

Doc有Show實例你可能會罰款，或者你可以使用更強大的造型功能。

λ let tree = Node 2 (Node 1 Empty Empty 0) (Node 3 Empty (Node 4 Empty Empty 0) (-1)) (-1) 
λ prettyTree (tree :: AVL Int) 
2 
1 
    Empty 
    Empty 
3 
    Empty 
    4 
    Empty 
    Empty 

---

如果你想做到這一點沒有任何外部依賴，只是嬰兒牀的風格，但在子自己墊片的組合子。

type Doc = [String] 

text :: String -> Doc 
text = pure 

indent :: Doc -> Doc 
indent = map (' ':) 

vertical :: Doc -> Doc -> Doc 
vertical = (++) 

prettyTree :: Show t => AVL t -> Doc 
prettyTree Empty   = text "Empty" 
prettyTree (Node t l r _) = vertical (text (show t)) 
            (indent (vertical (prettyTree l) 
                 (prettyTree r))) 

render :: Doc -> String 
render = concat