CS2040C-Lab-3/main.cpp at master · SharlynLui/CS2040C-Lab-3 · GitHub

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include "BST.h"


void testInsertion1(bool printWithHeight = true);
void testInsertion2(bool printWithHeight = true);
void testSuccessor();
void testSearchMinMax();
void testExist();
void suggestedHiddenCase1();
void suggestedHiddenCase1b();
void suggestedHiddenCase2();
void excerciseTest(bool printWithHeight = true);

int main() {

	testInsertion1(true);
	testExist();
	testSearchMinMax();
	testSuccessor();
	testInsertion2(true);
	excerciseTest();

}

void excerciseTest(bool printWithHeight) {

	cout << "Insertion Test 1" << endl;
	int array[] = { 7, 3, 1, 0, 2, 5, 4, 6, 11, 9, 8, 10, 13, 12, 14 };
	BinarySearchTree<int> bsti;
	for (int i = 0; i < 15; i++)
		bsti.insert(array[i]);

	bsti.printTree(printWithHeight);
	cout << endl << endl;
	cout << "The size of the tree is " << bsti.size() << endl;
	cout << "Pre-order Traversal:" << endl;
	bsti.preOrderPrint();
	cout << "In-order Traversal:" << endl;
	bsti.inOrderPrint();
	cout << "Post-order Traversal:" << endl;
	bsti.postOrderPrint();

	cout << endl << endl;
}

void testInsertion1(bool printWithHeight) {

	cout << "Insertion Test 1" << endl;
	int array[] = { 7, 3, 1, 0, 2, 5, 4, 6, 11, 9, 8, 10, 13, 12, 14 };
	BinarySearchTree<int> bsti;
	for (int i = 0; i < 15; i++)
		bsti.insert(array[i]);

	bsti.printTree(printWithHeight);
	cout << endl << endl;
	cout << "The size of the tree is " << bsti.size() << endl;
	cout << "Pre-order Traversal:" << endl;
	bsti.preOrderPrint();
	cout << "In-order Traversal:" << endl;
	bsti.inOrderPrint();
	cout << "Post-order Traversal:" << endl;
	bsti.postOrderPrint();

	cout << "Level order traversal" << endl;
	//bsti.LOT();

	cout << endl << endl;


}

void testExist() {

	cout << "Exist Test" << endl;
	BinarySearchTree<int> bsti;
	cout << "Numbers inserted in the tree: ";
	for (int i = 0; i < 11; i++)
	{
		cout << i * 6 << " ";
		bsti.insert(i * 6);
	}

	//	bsti.printTree(false);
	cout << endl << endl;

	for (int i = 0; i < 70; i += 8)
		cout << "The number " << i << (bsti.exist(i) ? " exists " : " does not exist ") << "in the tree" << endl;
	cout << endl << endl;
}

void testInsertion2(bool printWithHeight) {

	cout << "Insertion Test 2" << endl;
	cout << "The tree shape should be the same as Test 1" << endl;
	cout << "if you have done the balancing correctly." << endl;
	BinarySearchTree<int> bsti;
	for (int i = 0; i < 15; i++)
		bsti.insert(i);

	bsti.printTree(printWithHeight);
	cout << endl << endl;
	cout << "The size of the tree is " << bsti.size() << endl;
	cout << "Pre-order Traversal:" << endl;
	bsti.preOrderPrint();
	cout << "In-order Traversal:" << endl;
	bsti.inOrderPrint();
	cout << "Post-order Traversal:" << endl;
	bsti.postOrderPrint();

	cout << endl << endl;
}

void testSearchMinMax() {

	cout << "Search Min/Max Test" << endl;
	int array[] = { 7, 3, 1, 0, 2, 5, 4, 6, 11, 9, 8, 10, 13, 12, 14 };
	BinarySearchTree<int> bsti;
	for (int i = 0; i < 15; i++)
		bsti.insert(array[i]);

	cout << "The minimum number in the tree is " << bsti.searchMin() << endl;
	cout << "The maximum number in the tree is " << bsti.searchMax() << endl;
	cout << endl;

}

void testSuccessor() {

	cout << "Successor Test" << endl;
	BinarySearchTree<int> bsti;
	cout << "Numbers inserted in the tree: ";
	for (int i = 0; i < 11; i++)
	{
		cout << i * 7 << " ";
		bsti.insert(i * 7);
	}

	//bsti.printTree(false); //uncomment this after trial
	cout << endl << endl;

	for (int i = 0; i < 70; i+=10) //change to 70
		cout << "The successor of " << i << " in the BST is " << bsti.successor(i) << endl;
	cout << endl << endl;
}