Binary Tree

[waddlaw]

#113 からの派生

definition

data Tree
  = Leaf Int
  | Node Tree Tree

-- より一般化したもの
data Tree a
  = Leaf a
  | Node (Tree a) (Tree a)

operation

-- 部分木を左右反転させた木を返す
mirror :: Tree a -> Tree a

-- 葉の数を返す
count :: Tree a -> Int

-- 木の高さを返す
depth :: Tree -> Int

-- 木が平衡かどうか
balanced :: Tree -> Bool

-- 葉の値を集めてリストにして返す
leaves :: Tree a -> [a]

-- 左の部分木を返す
left :: Tree a -> Maybe (Tree a)

-- 右の部分木を返す
right :: Tree a -> Maybe (Tree a)

reference

• CIS 552: Advanced Programming
• Tree Implementation in Haskell
• Haskell/Other data structures
• Data.Tree
• Monad instance for binary tree
• Monads and all that… I. Monads
• Monads and all that… I. Monads (Exercises)
• INFORMATION ON EXAM 2