我需要帮助在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