Хорошая печать/отображение двоичного дерева в Haskell

У меня есть тип данных дерева:

data Tree a b = Branch b (Tree a b) (Tree a b) | Leaf a

... и мне нужно сделать экземпляр Show, не используя deriving. Я обнаружил, что приятно показать небольшую ветку с двумя листьями легко:

instance (Show a, Show b) => Show (Tree a b) where
   show (Leaf x) = show x
   show (Branch val l r) = " " ++ show val ++ "\n" ++ show l ++ "  " ++ show r

Но как я могу передать красивую структуру дереву произвольного размера? Похоже, что определение интервала потребует от меня знать, сколько листьев будет на самом дне (или, может быть, только на том, сколько листьев есть в целом), чтобы я мог выделить все пространство, в котором я нуждаюсь, и просто работать. ' Мне, вероятно, нужно будет вызвать функцию размера. Я вижу, что это работоспособно, но это делает его сложнее, чем оно есть?

Ответ 1

Вы можете изучить функцию drawTree в базе Data.Tree. Просто бесстыдно импортировать его даст вам что-то вроде этого:

import Data.Tree hiding (Tree )
data Tree a b = Branch b (Tree a b) (Tree a b) 
              | Leaf a deriving (Eq,Ord,Show)

toDataTree (Leaf a) = Node a []
toDataTree (Branch b cs ds) = Node b [toDataTree cs, toDataTree ds]

d = Branch "1" (Branch "11" (Leaf "111") (Leaf "112")) 
               (Branch "12" (Leaf "121") (Leaf "122"))

e = toDataTree d
f = putStrLn $ drawTree e

{-
*Main> f
1
|
+- 11
|  |
|  +- 111
|  |
|  `- 112
|
`- 12
   |
   +- 121
   |
   `- 122
-}

Ответ 2

Используя аппликативную ссылку на источник Data.Tree, я придумал это. Я хотел написать свой собственный, чтобы я мог больше узнать об этом. Метод drawTree в источнике обобщается для работы с узлами с несколькими дочерними элементами; мой - только для двоичных деревьев.

Примечание. Определение моего дерева немного отличается от определения OP. Я не совсем понимаю, для чего используется параметр типа a, но подход должен быть тем же самым

data Tree a
    = Branch (Tree a) a (Tree a)
    | Leaf

prettyprint (Leaf)
    = "Empty root."
-- unlines concats a list with newlines
prettyprint (Branch left node right) = unlines (prettyprint_helper (Branch left node right n h))

prettyprint_helper (Branch left node right)
    = (show node) : (prettyprint_subtree left right)
        where
            prettyprint_subtree left right =
                ((pad "+- " "|  ") (prettyprint_helper right))
                    ++ ((pad "`- " "   ") (prettyprint_helper left))
            pad first rest = zipWith (++) (first : repeat rest)
prettyprint_helper (Leaf)
    = []

Что создает дерево, подобное

4
+- 8
|  +- 9
|  |  +- 10
|  `- 6
|     +- 7
|     `- 5
`- 2
   +- 3
   `- 1

Я просто хотел объяснить, как работает функция pad, поскольку это было труднее всего для меня (называемый shift в источнике).

Во-первых, zipWith применяет функцию (первый аргумент) для объединения двух списков. zipWith (+) [1, 2, 3] [4, 5, 6] return [5, 7, 9]. Он останавливается, когда один из списков пуст. zipWith применяется только к одному списку, возвращает функцию, которая может быть применена для zip второго списка (я считаю, что это называется currying функции). Здесь более простая версия функции pad:

> let pad = zipWith (++) (repeat "   ")
> :type pad
pad :: [[Char]] -> [[Char]]
> pad ["1", "2", "3"]
["   1", "   2", "   3"]

Примечание: 1. Один из списков бесконечен (repeat " "), но он останавливается, когда один из списков пуст 2. zipWith принимает только функцию и список. pad - это функция, которая берет список списков символов/строк и возвращает зашифрованный список списка символов/строк. Таким образом, вы применяете pad в одном списке, чтобы закрепить его первым с помощью

Теперь посмотрим на

prettyprint_subtree left right =
    ((pad "+- " "|  ") (prettyprint_helper left))
        ++ ((pad "`- " "   ") (prettyprint_helper right))

(pad "+- " "| ") создает бесконечный список, например ["+- ", "| ", "| ", "| ", ...]. (prettyprint_helper right) строит список строк, представляющий поддерево справа, начиная с правого корня node. Но все дерево нужно смещать вправо; мы делаем это, застегивая его прокладкой. Мы используем бесконечный список, потому что мы не знаем, насколько велик поддерево; всегда будет достаточно "| " для ввода дополнительных строк (это также работает из-за ленивой оценки). Обратите внимание, что первая строка; т.е. поддерево-корневое-node, вместо этого добавляется "+- ", "обозначение" для правого node.

Левая сторона практически такая же. Обозначение для левого node составляет "`- ". Единственное другое отличие - заполнение; " " вместо "| ". Так почему же не оставлять узлы нужны "ветки"? Ну, вы можете думать об этом как о правильных узлах (добавление добавляется слева), идущих в левые узлы ниже. Вам нужно заполнить позади правой стороны, чтобы соединить левый node/поддерево с родительским node. За левой стороной дерева нет ничего, кроме родительского дерева. Это подводит меня к моему последнему моменту; каждое поддерево, представленное как список строк в функции prettyprint_helper, получает дополнительный уровень заполнения каждого родительского дерева вверх. Я думаю, что это лучше всего иллюстрируется примером.

При создании дерева выше (обратите внимание, что я точно не знаю порядок выполнения, особенно с ленивой оценкой, но это просто, чтобы помочь понять, почему он работает):

Скажем, мы возвращаемся к 10. Ну поддеревье слева и поддерево справа пусто, поэтому prettyprint_helper (Branch Leaf 10 Leaf) возвращает ["10"].

Теперь мы до 9. Это поддерево: "9" : ([] ++ ((pad "+- " "| ") [10])) (без левой стороны) или "9" : ["+- 10"], или:

9
+- 10

Теперь мы до 8. ((pad "+- " "| ") (prettyprint_helper right)) создает:

+- 9
|  +- 10

Вы можете проследить его самостоятельно, но с левой стороны:

6
+- 7
`- 5

Какие пэды (первый элемент "`- ", rest " "):

`- 6
   +- 7
   `- 5

Таким образом, в целом для 8, который является левой стороной, прикрепленной к правой стороне, мы имеем:

8
+- 9
|  +- 10
`- 6
   +- 7
   `- 5

Если перейти на один шаг вверх, это поддерево 8 будет дополнено для дерева 4, и снова вы сможете проследить через другую сторону, чтобы убедиться, что он работает. Вы получаете

+- 8
|  +- 9
|  |  +- 10
|  `- 6
|     +- 7
|     `- 5

И конечный результат, как и выше. Помните, что на протяжении всего этого процесса дерево представляется в виде списка строк. Только в самом конце он объединяется с unlines. Возможно, мои рисунки вводят в заблуждение, потому что это может выглядеть так, что поддеревья передаются как многострочные строки. Как только вы это понимаете, очень легко добавить дополнительную ветвь ("|") между левым и правым узлами, например, в функции Data.Tree drawTree. Я дам вам понять:)

Мои извинения, если это чрезмерное; мне было трудно понять из источника как новичка, и это было большим прыжком для меня. Я надеюсь, что это поможет кому-то еще решить эту проблему.