Haskell：在Bin树结构中获取从每个叶节点到根的路径 [英] Haskell: Get path from every leaf node to root in a Bin tree structure

问题描述

我有工作要做，但我不知道该怎么做。
我有Bin树

  1 
 / \ 
 2 3 
 / \ / \ 
 4 5 6 7 
  

我需要找到方法从根节点到coord [i，j]的节点。
例如：（2，2） - > [1,3,6]

  fromRoot :: Int  - > Int  - >树a  - > [a] 
  

我为Index和BinTree编写了一些函数，但是如何使主函数不知道

 数据树a =节点（树a）a（树a）
 
索引::树a  - > Int  - > Int  - > a 
 index（Node _ x _）0 _ = x 
 index（Node l x r）i j | （边界i）< j）=索引r（i-1）（j-（边界i）-1）
 |否则=索引l（i-1）j 
 
 
 border :: Int  - > Int 
 border 0 = 0 
 border 1 = 0 
 border l = 2 *（border（l-1））+ 1 
 
 myBuild :: Int  - > ; Tree Int 
 myBuild n =（Node（myBuild（n * 2））n（myBuild（n * 2 + 1）））
  

解决方案

既然这是作业，我不会给出一个完整的解决方案，但有些提示：

• 您如何用Tree类型表示空树？


• 您如何表示示例树（或任何其他有限树）？
>

考虑到主要功能：您不一定需要一个，开始运行的好方法

  ghci your_source_file.hs 
  

然后你就可以评估你的程序的一部分，例如：

  fromRoot 2 3 t1  - 如果你有一个t1是一棵树
  

除此之外，您可以编写一个如下所示的主函数：

  test_tree = ...  - 您需要填写点（请参阅上面的问题）
 
 main :: IO（）
 main =打印（fromRoot 2 2 test_tree）
  

如果您需要查找一些文档，请使用 http://haskell.org/hoogle/

I've got work to do, but i dunno how to do it. I have Bin tree

    1
   /  \
  2    3
 / \  / \
4  5  6  7

And I need to find the way from root to Node with the coord [i, j]. For example: (2, 2) -> [1, 3, 6]

fromRoot :: Int -> Int -> Tree a -> [a]

I wrote some function for Index and BinTree, but how to make main function i dont know.

data Tree a = Node (Tree a) a (Tree a)

index :: Tree a -> Int -> Int -> a
index (Node _ x _ ) 0 _ = x
index (Node l x r) i j  | ((border i)<j) = index r (i-1) (j-(border i)-1)       
                        | otherwise = index l (i-1) j


border :: Int -> Int
border 0 = 0
border 1 = 0
border l = 2*(border (l-1))+1

myBuild :: Int  -> Tree Int
myBuild n = (Node (myBuild (n*2)) n (myBuild (n*2+1)))

解决方案

Since this is homework I won't give a complete solution, but some hints:

• how do you represent an empty tree with your Tree type?
• how do you represent the example tree (or any other finite tree)?

Considering the main function: you don't necessarily need one, a good way to start is running

ghci your_source_file.hs

You can then evaluate parts of your program, e.g.:

fromRoot 2 3 t1 -- if you have a t1 is a tree

Apart from that you could write a main function like this:

test_tree = ...   -- you need to fill in the dots (see questions above)

main :: IO ()
main = do print (fromRoot 2 2 test_tree)

If you need to find some documentation, use http://haskell.org/hoogle/

这篇关于Haskell：在Bin树结构中获取从每个叶节点到根的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！