haskell - 在 Haskell 中以树状结构打印二叉搜索树

Question

我创建了一个二叉搜索树并尝试用这个实例打印二叉搜索树

data Tree a = Nil | Node (Tree a) a (Tree a)
instance Show a => Show (Tree a) where
        show t = intercalate "\n"  (map snd (draw t))

draw :: Show a => Tree a -> [(Int,String)]
draw Nil                = [(1,"*")]
draw (Node Nil x Nil)   = [(1,show x)]
draw (Node tl x tr)     = zip (repeat 0) (map shiftl (draw tl)) ++ [(1,show x ++ "-+")] ++ zip (repeat 2) (map shiftr (draw tr)) where
        shiftl (0,x)    =       spaces ++ "  " ++ x 
        shiftl (1,x)    =       spaces ++ "+-" ++ x 
        shiftl (2,x)    =       spaces ++ "| " ++ x 
        shiftr (0,x)    =       spaces ++ "| " ++ x 
        shiftr (1,x)    =       spaces ++ "+-" ++ x 
        shiftr (2,x)    =       spaces ++ "  " ++ x
        spaces          =       replicate  (length (show x)+1) ' '
createTree :: [a] -> BTree a
createTree []   = Nil
createTree xs    = Node
    (createTree front) x (createTree back) where
        n = length xs
        (front, x:back) = splitAt (n `div` 2) xs

现在我想水平打印它，但我无法这样做。我想打印如下图所示的二叉搜索树。 (抱歉图片质量低，但你明白了)。我该怎么做？

使用示例[1..50]

更新答案:-

我自己找到了答案。我创建了一个这样显示的函数。代码在评论里。

如果您有其他解决方案，请分享

Answer 1

这是我的解决方案。它可能并不完美。它将 Nil 节点打印为 *。

基本思想是首先将左右树的可视化作为两个字符串列表。然后使用连接将它们压缩以生成并排表示两棵树的字符串列表。

instance Show a => Show (Tree a) where
    show tree =
        let (s, _) = show' tree
        in intercalate "\n" s
        where
            show' :: Show a => Tree a -> ([String], Int)
            show' Nil = (["*"], 0)
            show' (Node ltree value rtree) = (ashow, acenter)
                where
                    -- middle_padding_length = 1
                    -- middle_padding = replicate (2*middle_padding_length+1) ' '
                    middle_padding = "   "
                    pwidth = length middle_padding

                    lshow, rshow :: [String]
                    lcenter, rcenter :: Int
                    (lshow, lcenter) = show' ltree
                    (rshow, rcenter) = show' rtree

                    lwidth, rwidth :: Int
                    lwidth = length (head lshow)
                    rwidth = length (head rshow)

                    awidth, acenter :: Int
                    awidth  = lwidth + length middle_padding + rwidth
                    acenter = lwidth + pwidth `div` 2

                    -- Put subtrees side by side with some padding
                    sshow :: [String]
                    sshow =
                        zipWith (\s1 s2 -> s1 ++ middle_padding ++ s2)
                            (extend_depth lwidth lshow)
                            (extend_depth rwidth rshow)
                        where
                            extend_depth twidth tshow =
                                let
                                    sdepth = max (length lshow) (length rshow)
                                in
                                    tshow ++ replicate (sdepth - length tshow) (replicate twidth ' ')

                    vshow :: String
                    vshow =
                        let
                            text = show value
                            textWidth = length text
                            whitespaceWidth = awidth - textWidth
                            leftPadding = acenter - textWidth `div` 2
                            rightPadding = whitespaceWidth - leftPadding
                        in
                            replicate leftPadding ' ' ++ text ++ replicate rightPadding ' '


                    row :: [Char] -> String
                    row [lc, mc, rc, hc, sc] =
                        replicate lcenter sc ++ [lc] ++ replicate (acenter-lcenter-1) hc ++
                        [mc] ++
                        replicate (lwidth+pwidth+rcenter-acenter-1) hc ++ [rc] ++ replicate (awidth-lwidth-pwidth-rcenter-1) sc
                    row _ = error "incorrect number of characters"

                    two_pipes, splitter, one_pipe :: String
                    two_pipes = row "| |  "
                    splitter  = row "/^\\- "
                    one_pipe  = row " |   "

                    ashow :: [String]
                    ashow =
                        vshow :
                        one_pipe :
                        splitter :
                        two_pipes :
                        sshow

createTree [0..10] 的输出: