函数采用二叉树并按顺序打印其值 [英] Function which Takes a binary tree and prints out its values in order

查看：112
本文介绍了函数采用二叉树并按顺序打印其值的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我正在写一个函数来获取二叉树并以正确的顺序打印出它的值（顺序横向）。我遇到的问题是当我调用函数时，我一直得到一个非穷尽的模式错误

p> 

  --k是键，d是值
  -  l是左树，r是右树
 treeprint（node lkdr）= treeprint l ++ show k ++ show d ++ treeprint r 
 treeprint Nil =


解决方案

似乎已经解决了您的问题，除非您需要一些括号和空格。



您的（当前）版本



我假设您使用 

 数据树kd = Nil | Node（Tree k d）k d（Tree Tree）

虽然你没说。我将定义一个或两个示例树：

  example1，example2 :: Tree Int String 
 example1 = Node节点Nil 4HelloNil）7there（节点Nil 21hiNil）
 example2 =节点example1 34well（节点Nil 55This ）102多（节点无132较大无）））

您的函数

  treeprint（节点lkdr）= treeprint l ++ show k ++ show d ++ treeprint r 
 treeprint Nil =

编译正常，但由于没有空格或括号，输出很混乱：

  *主要> putStrLn $ treeprint example1 
 4Hello7there21hi
 * Main> putStrLn $ treeprint example2 $ b $ 4Hello7there21hi34well55这个73的102多了132更大
  
 
 
 
它是按顺序排列在一起的，并且树状结构不再存在。 
 
 
更多括号，更多空格，更清晰
 
 
 
让我们用每个树周围的括号和空格重写它： 
 
 
  tree_print（Node lkdr）=（++ treeprint l ++ show k ++：++ show d ++ treeprint r ++）
 tree_print Nil = 
  
所以现在更清晰： 
 
 
  *主> putStrLn $ tree_print example1 
（（4：Hello）7：there（21：hi））
 * Main> putStrLn $ tree_print example2 $ b $（（（4：Hello）7：there（21：hi））34：well（55：This（（73：one's）102 ：多（132：更大））））
  
 
 
 
展开树并获得更多括号！
 
 
 
也许你不需要括号，因为打印命令是为了使树变平。你可以保留空格和：，它可以工作。或者，定义 
 
 
  toList :: Tree k d  - > [（k，d）] 
 toList Nil = [] 
 toList（Node t1 kd 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）， 102，多），（132，更大）] 
  
 
 
 
漂亮
 
 
 
以下是使用 Data.Tree.Pretty 打印树的方法。 http://hackage.haskell.org/package/pretty-tree\">pretty-tree 库。 
 
 
 
我需要做一些导入： 
 
 
  import qualified Data.Tree as T 
 import Data.Tree.Pretty 
  
我导入了 Data.Tree 合格，因为它也定义了一个数据构造函数 Node 。这意味着当我指的是导入的树时，我将使用 T.Node ，但当我指的是你的时候，只是 Node 。  
 
 
它使用玫瑰树（在每个节点上可以有多少个子树）： 
 
 
 数据树a =节点{
 rootLabel :: a， -  ^标签值
 subForest :: Forest a  -  ^零个或多个子树
} 
  
并定义 drawVerticalTree :: Tree String  - >字符串这就是我将要使用的。 
我们所需要做的就是将您的树转换为这棵树，然后我们就可以开始工作： 
 
 
  toTree ::（Show k，Show d）=>树k d  - > T.Tree String 
 toTree Nil = T.Node - [] 
 toTree（节点t1 kd t2）= T.Node（show k ++：++ show d）[toTree t1 ，toTree t2] 
  
现在让我们展示（创建一个String）并打印（在IO monad中输出） ： 
 
 
  showtree ::（Show k，Show d）=>树k d  - >字符串
 showtree = drawVerticalTree.toTree 
 
 printtree ::（显示k，显示d）=>树k d  - > IO（）
 printtree = putStrLn。（'\\\
':)。showtree 
  
这给了很好的输出：
  * Main> printtree example1 
 
 7：there
 | 
 --------- 
 / \ 
 4：Hello21：hi
 | | 
  -   -  
 / \ / \ 
  -   -   -   -  
  
对于稍微大一些的例子，我们可以比较优雅地处理： 
 
 
  * Main> printtree example2 
 
 34：well
 | 
 ------------------------ 
 / \ 
 7：there55：This
 | | 
 --------- ------------- 
 / \ / \ 
 4：Hello21：hi -  102：多
 | | | 
  -   -  ------------ 
 / \ / \ / \ 
  -   -   -   -  73：one's132：更大
 | | 
  -   -  
 / \ / \ 
  -   -   -   -  
  
 
I am currently writing a a function to take a binary tree and print out its values in the right order(in order transversal).The problem i have is i keep getting a non exhaustive pattern error when ever i call the function
 --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=""



 解决方案 
You seem to have solved your problem, except you need some brackets and spaces. 



Your (current) version



I assume you're using
data Tree k d = Nil | Node (Tree k d) k d (Tree k d)

although you didn't say. I'll define an example tree or two:
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)))

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

compiles OK but because there are no spaces or brackets, the output is confusing:
*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"

It's in order, but squashed together, and the tree structure is gone.



More brackets, more spaces, more clarity



Let's rewrite it with brackets and spaces around each tree:
tree_print (Node l k d r) = " (" ++ treeprint l  ++ show k ++ ":" ++ show d ++ treeprint r ++ ") "
tree_print Nil = ""

so it's much clearer now:
*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") ) ) ) 




Flatten the tree and get even more brackets!



Maybe you don't want the brackets because the in order print is meant to flatten the tree. You could just keep the spaces and the : and it would work. Alternatively, define
toList :: Tree k d -> [(k,d)]
toList Nil = []
toList (Node t1 k d t2) = toList t1 ++ (k,d):toList t2

Which means you'd be able to use the Show instance for lists:
*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")]




Prettier



Here's a way to print the tree using a Data.Tree.Pretty from the pretty-tree library. 



I'll have to do some importing:
import qualified Data.Tree as T
import Data.Tree.Pretty

I've imported Data.Tree qualified because it also defines a data constructor Node. This means I'll use T.Node when I mean the imported tree, but just Node when I mean yours.



It uses rose trees (that can have as many subtrees as they like at each node):
data Tree a = Node {
        rootLabel :: a,         -- ^ label value
        subForest :: Forest a   -- ^ zero or more child trees
    }

and defines drawVerticalTree :: Tree String -> String which is what I'll use.
All we need to do is convert your tree to this tree, and we'll be in business:
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]

Now let's show (make a String) and print (output in the IO monad):
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

Which gives nice output:
*Main> printtree example1

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

And copes fairly gracefully with slightly larger examples:
*Main> printtree example2

                   34:"well"                   
                       |                       
         ------------------------              
        /                        \             
    7:"there"                55:"This"         
        |                        |             
     ---------       -------------             
    /         \     /             \            
4:"Hello"  21:"hi"  -         102:"much"       
    |         |                   |            
    --        --            ------------       
   /  \      /  \          /            \      
   -  -      -  -      73:"one's"  132:"bigger"
                           |            |      
                           --           --     
                          /  \         /  \    
                          -  -         -  -    



                        
这篇关于函数采用二叉树并按顺序打印其值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
相关文章
其他开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆