非平衡二叉树

Question

我喜欢阅读格雷厄姆·赫顿（Graham Hutton）的迷人著作《在Haskell中编程》（第二版）。在第97章“ 8声明类型和类”的章节“ 8.4递归类型”的底部，我找到了二叉树的定义：

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))

是的，我也许理解这是怎么回事，但是如何使之正确？

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

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你可以用零，二，四，等值创建树：

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))