-
Notifications
You must be signed in to change notification settings - Fork 0
/
Tree.test.scala
113 lines (75 loc) · 3.31 KB
/
Tree.test.scala
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
//> using test.dep org.scalameta::munit::0.7.29
//> using file Tree.scala
import munit.FunSuite
import BinaryTree._
class TreeTests extends munit.FunSuite {
test("empty tree"){
val e = BinaryTree()
assertEquals(e, EmptyTree)
assertEquals(BinaryTree.empty, EmptyTree)
}
test("create a Tree"){
val e = create(2, BinaryTree(1), BinaryTree(3))
val expected = TreeNode(2,TreeNode(1,EmptyTree,EmptyTree),TreeNode(3,EmptyTree,EmptyTree))
assertEquals(e, expected)
}
test("size of a Tree"){
val e = BinaryTree(2, BinaryTree(1), BinaryTree(3))
assertEquals(size(e), 3)
}
test("check whether a tree contains a value"){
val e = BinaryTree(2, BinaryTree(1), BinaryTree(3))
assertEquals(contains(e, 2), true)
}
test("depth of tree"){
val e = BinaryTree.create(2, BinaryTree(1), BinaryTree(3))
assertEquals(depth(e), 2)
}
test("transform elements of a tree using map"){
val e = BinaryTree.create(2, BinaryTree(1), BinaryTree(3))
val expected = TreeNode(4,TreeNode(2,EmptyTree,EmptyTree),TreeNode(6,EmptyTree,EmptyTree))
assertEquals(map(e)(_ * 2), expected)
}
test("fold should correctly accumulate values in a binary tree"){
val tree1 = TreeNode(1, TreeNode(2, EmptyTree, EmptyTree), TreeNode(3, EmptyTree, EmptyTree))
val tree2 = TreeNode(4, TreeNode(5, TreeNode(6, EmptyTree, EmptyTree), EmptyTree), TreeNode(7, EmptyTree, EmptyTree))
val sumFunction: (Int, Int, Int) => Int = (a, b, c) => a + b + c
assertEquals(BinaryTree.fold(tree1)(0)(sumFunction), 6)
assertEquals(BinaryTree.fold(tree2)(0)(sumFunction), 22)
}
test("insert data into tree"){
val tree1 = TreeNode(1, TreeNode(2, EmptyTree, EmptyTree), TreeNode(3, EmptyTree, EmptyTree))
val e = insert(tree1, Some(5))
val expected = TreeNode(5,TreeNode(1,TreeNode(2,EmptyTree,EmptyTree),TreeNode(3,EmptyTree,EmptyTree)),EmptyTree)
assertEquals(e, expected)
}
val treeTest: BinaryTree[Int] =
TreeNode(
27,
TreeNode(
14,
TreeNode(5, EmptyTree, TreeNode(10, TreeNode(6, EmptyTree, TreeNode(9, EmptyTree, EmptyTree)), EmptyTree)),
EmptyTree
),
TreeNode(31, EmptyTree, EmptyTree)
)
test("in-order traversal of a tree"){
val tree1 = TreeNode(1, TreeNode(2, EmptyTree, EmptyTree), TreeNode(3, EmptyTree, EmptyTree))
val expected = TreeNode(5,TreeNode(1,TreeNode(2,EmptyTree,EmptyTree),TreeNode(3,EmptyTree,EmptyTree)),EmptyTree)
println(inOrderTraversal(treeTest))
assertEquals(inOrderTraversal(expected), List(2,1,3,5))
assertEquals(inOrderTraversal(treeTest), List(5, 6, 9, 10, 14, 27, 31))
}
test("post-order traversal of traversal"){
val expected = TreeNode(5,TreeNode(1,TreeNode(2,EmptyTree,EmptyTree),TreeNode(3,EmptyTree,EmptyTree)),EmptyTree)
assertEquals(postOrderTraversal(expected), List(2, 3, 1, 5))
println(postOrderTraversal(treeTest))
assertEquals(postOrderTraversal(treeTest), List(9, 6, 10, 5, 14, 31, 27))
}
test("pre-order traversal of tree"){
val expected = TreeNode(5,TreeNode(1,TreeNode(2,EmptyTree,EmptyTree),TreeNode(3,EmptyTree,EmptyTree)),EmptyTree)
println(preOrderTraversal(treeTest))
assertEquals(preOrderTraversal(expected), List(5, 1, 2, 3))
assertEquals(preOrderTraversal(treeTest), List(27, 14, 5, 10, 6, 9, 31))
}
}