非平衡二叉树

Question

我喜欢阅读格雷厄姆·赫顿的引人入胜的书“Haskell中的编程”(第二版)。在"8声明类型和类“一节"8.4递归类型”第97页底部，我找到了二叉树的定义：

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

这是一个很好的二叉树，但是我不能用0，2，4，5，6，8，.元素。我编写了以下文件bst.hs

data Tree a = Leaf a | Node (Tree a) a (Tree a)
    deriving (Eq, Ord, Show, Read)

我在文件夹和加载文件中启动Haskell解释器。

$ ghci
GHCi, version 8.6.4: http://www.haskell.org/ghc/  :? for help
Prelude> :load bst.hs 
[1 of 1] Compiling Main             ( bst.hs, interpreted )
Ok, one module loaded.

好的，一个模块加载。但现在我试着展示“叶子”或“树”(如叶子或节点)，它是好的。

*Main> show (Leaf 3)
"Leaf 3"
*Main> show (Node (Leaf 1) 2 (Leaf 3))
"Node (Leaf 1) 2 (Leaf 3)"

但是我不能用{1，2}来做树。我怎么写这样的树？我试过：

*Main> show (Node (Leaf 1) 2 _)

<interactive>:4:23: error:
    • Found hole: _ :: Tree Integer
    • In the third argument of ‘Node’, namely ‘_’
      In the first argument of ‘show’, namely ‘(Node (Leaf 1) 2 _)’
      In the expression: show (Node (Leaf 1) 2 _)
    • Relevant bindings include
        it :: String (bound at <interactive>:4:1)
*Main> show (Node (Leaf 1) 2)

<interactive>:5:1: error:
    • No instance for (Show (Tree Integer -> Tree Integer))
        arising from a use of ‘show’
        (maybe you haven't applied a function to enough arguments?)
    • In the expression: show (Node (Leaf 1) 2)
      In an equation for ‘it’: it = show (Node (Leaf 1) 2)
*Main> show (Node (Leaf 1) 2 (Node))

<interactive>:6:24: error:
    • Couldn't match expected type ‘Tree Integer’
                  with actual type ‘Tree a0 -> a0 -> Tree a0 -> Tree a0’
    • Probable cause: ‘Node’ is applied to too few arguments
      In the third argument of ‘Node’, namely ‘(Node)’
      In the first argument of ‘show’, namely ‘(Node (Leaf 1) 2 (Node))’
      In the expression: show (Node (Leaf 1) 2 (Node))

是的，我也许知道怎么做是错误的，但如何使正确？

对于我的初学者问题，唯一的答案可能是在第99页中声明Tree为其他建议树：

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

但是如何用0，2，4，.元素？或者如果不可能的话，为什么书不谈呢？总是有很好的理由，所以什么是理由？

Answer 1

二叉树的定义是一个完整的二叉树，

“每个节点都有0或2个子节点的树。”

如果更明确地命名该类型，则会更清楚：

data FullBinaryTree a = Leaf a | Node (FullBinaryTree a) a (FullBinaryTree a)

这是一件事，但您经常会看到二叉树的另一个定义，它也允许空节点，正如您建议的那样。但是，空节点通常命名为Empty。

data BinaryTree a = Empty | Node (BinaryTree a) a (BinaryTree a) deriving (Eq, Show)

这两种树在数学上都是有效的二叉树，但显然不是相同的。使用BinaryTree，您可以创建具有0、2、4等值的树：

Prelude> Empty
Empty
Prelude> Node Empty 42 $ Node Empty 1337 Empty
Node Empty 42 (Node Empty 1337 Empty)
Prelude> Node Empty 42 $ Node (Node Empty 1337 Empty) 2112 (Node Empty 91235 Empty)
Node Empty 42 (Node (Node Empty 1337 Empty) 2112 (Node Empty 91235 Empty))

Answer 2

您最初的定义只允许具有奇数元素的树。

你可以用

data Tree a = Empty | Node (Tree a) a (Tree a)

或者只能将元素存储在叶中。

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