— Jiayu Han (932-907-189)
— Han-Hsing Pao (933-651-943)
— Grading note: 10pts total
—* 2pts for inBST
—* 1pt for all other definitions
module HW1 where
— | Integer-labeled binary trees.
data Tree
= Node Int Tree Tree — ^ Internal nodes
| Leaf Int — ^ Leaf nodes
deriving (Eq,Show)
— | An example binary tree, which will be used in tests.
t1 :: Tree
t1 = Node 1 (Node 2 (Node 3 (Leaf 4) (Leaf 5))
(Leaf 6))
(Node 7 (Leaf 8) (Leaf 9))
— | Another example binary tree. This one satisfies the BST property.
t2 :: Tree
t2 = Node 6 (Node 2 (Leaf 1) (Node 4 (Leaf 3) (Leaf 5)))
(Node 8 (Leaf 7) (Leaf 9))
— | Some more trees that violate the BST property.
t3, t4, t5, t6 :: Tree
t3 = Node 3 (Node 2 (Leaf 1) (Leaf 4)) (Leaf 5)
t4 = Node 3 (Leaf 1) (Node 4 (Leaf 2) (Leaf 5))
t5 = Node 4 (Node 2 (Leaf 3) (Leaf 1)) (Leaf 5)
t6 = Node 2 (Leaf 1) (Node 4 (Leaf 5) (Leaf 3))
— | All of the example trees in one list.
ts :: [Tree]
ts = [t1,t2,t3,t4,t5,t6]
— | The integer at the left-most node of a binary tree.
—
— >>> leftmost (Leaf 3)
— 3
—
— >>> leftmost (Node 5 (Leaf 6) (Leaf 7))
— 6
—
— >>> map leftmost ts
— [4,1,1,1,3,1]
—
leftmost :: Tree -> Int
leftmost (Leaf x) = x
leftmost (Node _ l _) = leftmost l
— If there is only one leaf, then the leftmost is just the leaf itself.
— If there is a tree, we`ll be only looking for left child under the tree since
— we`re looking for the leftmost. Then do the recursive till the left child becaomes
—a leaf.
— | The integer at the right-most node of a binary tree.
—
— >>> rightmost (Leaf 3)
— 3
—
— >>> rightmost (Node 5 (Leaf 6) (Leaf 7))
— 7
—
— >>> map rightmost ts
— [9,9,5,5,5,3]
—
rightmost :: Tree -> Int
rightmost (Leaf x) = x
rightmost (Node _ _ r) = rightmost r
–Same idea as the leftmost.
— | Get the maximum integer from a binary tree.
—
— >>> maxInt (Leaf 3)
— 3
—
— >>> maxInt (Node 5 (Leaf 4) (Leaf 2))
— 5
—
— >>> maxInt (Node 5 (Leaf 7) (Leaf 2))
— 7
—
— >>> map maxInt ts
— [9,9,5,5,5,5]
—
maxInt :: Tree -> Int
maxInt (Leaf x) = x
maxInt (Node x l r) = maximum [x, maxInt l, maxInt r]
–If there is only one leaf, then the maximum is just the leaf itself.
–If there is a tree, we will just be looking for the maximum number between
— [x, leftchild, rightchild]. Do the recursive for both leftchild and rightchild till
—they become a leaf.
— | Get the minimum integer from a binary tree.
—
— >>> minInt (Leaf 3)
— 3
—
— >>> minInt (Node 2 (Leaf 5) (Leaf 4))
— 2
—
— >>> minInt (Node 5 (Leaf 4) (Leaf 7))
— 4
—
— >>> map minInt ts
— [1,1,1,1,1,1]
—
minInt :: Tree -> Int
minInt (Leaf x) = x
minInt (Node x l r) = minimum [x, minInt l, minInt r]
— Same as maxInt.
— | Get the sum of the integers in a binary tree.
—
— >>> sumInts (Leaf 3)
— 3
—
— >>> sumInts (Node 2 (Leaf 5) (Leaf 4))
— 11
—
— >>> sumInts (Node 10 t1 t2)
— 100
—
— >>> map sumInts ts
— [45,45,15,15,15,15]
—
sumInts :: Tree -> Int
sumInts (Leaf x) = x
sumInts (Node x l r) = x + sumInts l + sumInts r
—If there is only one leaf, then the sum is just the leaf itself.
—If there is a tree, then the sum would x + (the sum of leftchild) +
—(the sum of rightchild), which is just recursive.
— | The list of integers encountered by a pre-order traversal of the tree.
—
— >>> preorder (Leaf 3)
— [3]
—
— >>> preorder (Node 5 (Leaf 6) (Leaf 7))
— [5,6,7]
—
— >>> preorder t1
— [1,2,3,4,5,6,7,8,9]
—
— >>> preorder t2
— [6,2,1,4,3,5,8,7,9]
—
— >>> map preorder [t3,t4,t5,t6]
— [[3,2,1,4,5],[3,1,4,2,5],[4,2,3,1,5],[2,1,4,5,3]]
—
preorder :: Tree -> [Int]
preorder (Leaf x) = [x]
preorder (Node x l r) = [x] ++ preorder l ++ preorder r
—If there is only one leaf, then the preorder is just the leaf itself.
—If there is a tree, we just need to add the int into the list [x] from left to right.
— | The list of integers encountered by an in-order traversal of the tree.
—
— >>> inorder (Leaf 3)
— [3]
—
— >>> inorder (Node 5 (Leaf 6) (Leaf 7))
— [6,5,7]
—
— >>> inorder t1
— [4,3,5,2,6,1,8,7,9]
—
— >>> inorder t2
— [1,2,3,4,5,6,7,8,9]
—
— >>> map inorder [t3,t4,t5,t6]
— [[1,2,4,3,5],[1,3,2,4,5],[3,2,1,4,5],[1,2,5,4,3]]
—
inorder :: Tree -> [Int]
inorder (Leaf x) = [x]
inorder (Node x l r) = inorder l ++ [x] ++ inorder r
— Similar idea as preorder.
— | Check whether a binary tree is a binary search tree.
—
— >>> isBST (Leaf 3)
— True
—
— >>> isBST (Node 5 (Leaf 6) (Leaf 7))
— False
—
— >>> map isBST ts
— [False,True,False,False,False,False]
—
isBST :: Tree -> Bool
isBST (Leaf x) = True
isBST (Node x l r) = (maxInt l < x) && (minInt r > x) && (isBST l) && (isBST r)
—If there is only one leaf, then isBST is true.
—Based on the definition of BST, the maxInt l < x < maxInt r. Then we should –do recursive for both l and r. It is only true when all of them match.– | Check whether a number is contained in a binary search tree.– You should assume that the given tree is a binary search tree– and *not* explore branches that cannot contain the value if– this assumption holds. The last two test cases violate the– assumption, but are there to help ensure that you do not– explore irrelevant branches.—- >>> inBST 2 (Node 5 (Leaf 2) (Leaf 7))
— True
—
— >>> inBST 3 (Node 5 (Leaf 2) (Leaf 7))
— False
—
— >>> inBST 4 t2
— True
—
— >>> inBST 10 t2
— False
—
— >>> inBST 4 t3
— False
—
— >>> inBST 2 t4
— False
—
inBST :: Int -> Tree -> Bool
inBST i (Leaf x) = i == x
inBST i (Node x l r) = (isBST (Node x l r)) && ((i == x) || (inBST i l) || (inBST i r))
— If there only a leaf, we just need to check whether they match or not.
— If there is a tree, we need to check whether the tree is in BST or not,
—if true, then check if the int is included,
—if yes, return true,
—else false.
—else false.
Reviews
There are no reviews yet.