Fork me on GitHub

在看real world haskell,关于两种二叉树定义的疑问

书上给出了两种二叉树的定义
###第一种定义方法

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

treeA=Node "parent" (Node "left" Empty Empty)   (Node "right" Empty Empty) 

第二种使用Maybe ,只有一个值构造器

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

treeB=Node "parent"  (Just (Node "left" Nothing Nothing )) (Just  (Node "right" Nothing Nothing ))

想问一下这两种定义方法的对应的应用场景

Submitted by at 6 years ago

所有回复

我理解为是同一个事情的不同实现。
貌似是第二种更接近于书上Java的定义。

wuhaisheng 6 years ago

其实我也不会Java,只写过一点C#。 我是看到书里面有一句

Where the Java example provides null to the
Tree constructor, we supply Empty in Haskell

仔细想想 Maybe 有点类似模板,我还是改过来把。


后面写计算二叉树高度,还是用了第一种定义。第二种手写一个二叉树有点麻烦,要Just一下。

sillyousu 6 years ago

我更喜欢如下的定义:

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

这样可以避免非"二叉"的情况出现.

看了一下 wikipedia, 这个叫 full binary tree, proper binary tree 或者 strict binary tree. 通常的定义允许零个,一个, 或两个分叉.

ninegua 6 years ago

我觉得楼主那样定义是不好的。因为Maybe代表的是计算的失败,而Leaf是代表下面没有节点,C#中可以用null,但是这样就不知道是因为计算失败返回了null,还是树下面本身为空,而在Haskell中应该将他们分开。

xiaoxiaflash 6 years ago

用到 Maybe 的写法是书里的习题要求。后来计算树的高度发现的确不好用。

sillyousu 6 years ago

@sillyousu 你可以将两个类型复合
data Tree a = Leaf | Node (Tree a) a ( Tree a)
type MaybeTree a = Tree (Maybe a)

xiaoxiaflash 6 years ago