1

私は現在、二分木を取り、その値を正しい順序で（横断順に）出力する関数を書いています。私が抱えている問題は、関数を呼び出すたびに非網羅的なパターンエラーが発生し続けることです。

 --k is the key and d is the value
 -- l is left tree and r is right tree
treeprint (Node l k d r)      =  treeprint l  ++ show k ++ show d ++ treeprint r 
treeprint Nil=""
4

1 に答える 1

6

ブラケットとスペースが必要なことを除けば、問題は解決したようです。

あなたの（現在の）バージョン

使っていると思います

data Tree k d = Nil | Node (Tree k d) k d (Tree k d)

あなたは言わなかったのに。サンプル ツリーを 1 つまたは 2 つ定義します。

example1, example2 :: Tree Int String
example1 = Node (Node Nil 4 "Hello" Nil) 7 "there" (Node Nil 21 "hi" Nil)
example2 = Node example1 34 "well" (Node Nil 55 "This" (Node (Node Nil 73 "one's" Nil) 102 "much" (Node Nil 132 "bigger" Nil)))

あなたの機能

treeprint (Node l k d r) =  treeprint l  ++ show k ++ show d ++ treeprint r 
treeprint Nil = ""

コンパイルはOKですが、スペースや括弧がないため、出力は混乱します:

*Main> putStrLn $ treeprint example1
4"Hello"7"there"21"hi"
*Main> putStrLn $ treeprint example2
4"Hello"7"there"21"hi"34"well"55"This"73"one's"102"much"132"bigger"

それは順調ですが、一緒に押しつぶされ、ツリー構造はなくなりました。

より多くの括弧、より多くのスペース、より明確

各ツリーの周りに括弧とスペースを入れて書き直してみましょう:

tree_print (Node l k d r) = " (" ++ treeprint l  ++ show k ++ ":" ++ show d ++ treeprint r ++ ") "
tree_print Nil = ""

そのため、今でははるかに明確になっています。

*Main> putStrLn $ tree_print example1
 ( (4:"Hello") 7:"there" (21:"hi") ) 
*Main> putStrLn $ tree_print example2
 ( ( (4:"Hello") 7:"there" (21:"hi") ) 34:"well" (55:"This" ( (73:"one's") 102:"much" (132:"bigger") ) ) )

ツリーを平らにして、ブラケットをさらに増やしましょう!

順番に印刷することはツリーを平らにすることを意図しているため、括弧は必要ないかもしれません。スペースとをそのままにしておくと、うまくいきます:。または、定義する

toList :: Tree k d -> [(k,d)]
toList Nil = []
toList (Node t1 k d t2) = toList t1 ++ (k,d):toList t2

Showつまり、リストにインスタンスを使用できるということです:

*Main> toList example1
[(4,"Hello"),(7,"there"),(21,"hi")]
*Main> toList example2
[(4,"Hello"),(7,"there"),(21,"hi"),(34,"well"),(55,"This"),(73,"one's"),(102,"much"),(132,"bigger")]

よりきれいに

pretty-treeライブラリData.Tree.Prettyのを使用してツリーを印刷する方法を次に示します。

インポートを行う必要があります。

import qualified Data.Tree as T
import Data.Tree.Pretty

Data.Treeデータ コンストラクターも定義しているため、qualifiedをインポートしましたNode。これはT.Node、インポートされたツリーを意味するときに使用することを意味しますが、Nodeあなたのものを意味する場合にのみ使用します.

バラの木を使用します (各ノードで好きなだけサブツリーを持つことができます)。

data Tree a = Node {
        rootLabel :: a,         -- ^ label value
        subForest :: Forest a   -- ^ zero or more child trees
    }

使用するものを定義drawVerticalTree :: Tree String -> Stringします。私たちがする必要があるのは、あなたのツリーをこのツリーに変換することだけです。

toTree :: (Show k,Show d) => Tree k d -> T.Tree String
toTree Nil = T.Node "-" []
toTree (Node t1 k d t2) = T.Node (show k ++ ":" ++ show d) [toTree t1,toTree t2]

show (文字列を作成) して print (IO モナドに出力) しましょう:

showtree :: (Show k, Show d) => Tree k d -> String
showtree = drawVerticalTree.toTree

printtree :: (Show k, Show d) => Tree k d -> IO ()
printtree = putStrLn.('\n':).showtree

素敵な出力が得られます：

*Main> printtree example1

    7:"there"     
        |         
     ---------    
    /         \   
4:"Hello"  21:"hi"
    |         |   
    --        --  
   /  \      /  \ 
   -  -      -  -

そして、少し大きな例でもかなり優雅に対処します:

*Main> printtree example2

                   34:"well"                   
                       |                       
         ------------------------              
        /                        \             
    7:"there"                55:"This"         
        |                        |             
     ---------       -------------             
    /         \     /             \            
4:"Hello"  21:"hi"  -         102:"much"       
    |         |                   |            
    --        --            ------------       
   /  \      /  \          /            \      
   -  -      -  -      73:"one's"  132:"bigger"
                           |            |      
                           --           --     
                          /  \         /  \    
                          -  -         -  -
于 2012-11-18T15:37:26.577 に答える