树

Question

的较大的分支。如果我有数据类型：

data Tree t = Leaf | Branch t t 

我怎样才能让一个函数来获取一棵树的最长的分支？我想在列表中得到答案，该列表包含从根到树叶的最长分支节点的所有值。事情是这样的：

longestBranch :: (Tree a) -> [a] 

什么建议吗？ 谢谢。

Answer 1

As amalloy noted你目前在你的问题的类型不是树：

data Tree t = Leaf | Branch t t 

这是同构的Maybe (t,t) - 它要么包含两个t值，或什么都没有。

两种最常见的二叉树，人们定义要么值的分支：

 A 
    / \ 
    B  C 
/\ /\ 
    D * * E 
/\  /\ 
* F  * G 
/\  /\ 
    * *  * * 

，或者在叶子：

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

既然你正在寻找的东西，“包含所有从根到树叶的最长分支的节点 的值“，我假设你正在为前者寻找 。

此数据类型可被定义为：

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

甲Leaf是一个高度-0树。 A Branch包含两个子树和一个值。

longestBranch Leaf = _ 
longestBranch (Branch left value right) = 
    let longestLeft = longestBranch left 
     longestRight = longestBranch right 
    in _ 

现在对于一些引导性问题：

现在

，看着所需功能的类型

longestBranch :: Tree a -> [a] 

我们可以通过类型把它分解为两种情况

• 从Leaf开始的最长分支是什么？

• 鉴于longestLeft对于left子树最长的分支， 即longestRight是为right子树最长的分支，你能 确定Branch left value right最长的分支是什么？