Skip to content

Instantly share code, notes, and snippets.

@shigemk2

shigemk2/tree.hs

Created Apr 1, 2015
Embed
What would you like to do?
-- 木構造とは、空の木、もしくは何らかの値と 2 つの木を含む要素からなる構造です。それって代数データ型で表してくれといわんばかりの構造ですね!
data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)
-- 要素が 1 つしかない木を作るための補助関数
singleton :: a -> Tree a
singleton x = Node x EmptyTree EmptyTree
-- 要素 x を木に挿入するための関数
treeInsert :: (Ord a) => a -> Tree a -> Tree a
treeInsert x EmptyTree = singleton x
treeInsert x (Node a left right)
| x == a = Node x left right
| x < a = Node a (treeInsert x left) right
| x > a = Node a left (treeInsert x right)
-- 要素 x を木に挿入するための関数
treeElem :: (Ord a) => a -> Tree a -> Bool
treeElem x EmptyTree = False
treeElem x (Node a left right)
| x == a = True
| x < a = treeElem x left
| x > a = treeElem x right
main = do
let nums = [8,6,4,1,7,3,5]
let numsTree = foldr treeInsert EmptyTree nums
print numsTree
print $ 8 `treeElem` numsTree
print $ 100 `treeElem` numsTree
print $ 99 `treeElem` numsTree
-- 結果はこんな感じだ
-- Node 5
-- (Node 3
-- (Node 1 EmptyTree EmptyTree)
-- (Node 4 EmptyTree EmptyTree)
-- )
-- (Node 7
-- (Node 6 EmptyTree EmptyTree)
-- (Node 8 EmptyTree EmptyTree)
-- )
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.