Student project in 2024
During the semester the students will (individually) working on a larger project. They will step by step create a class for the binary search tree data structure and its test environment. For every time you have to create a small additional task built on the previous results. We publish the solution of each steps after the deadline with some delay.
Submit the solutions on Canvas copying the source of the solution as text.
Task 1: Write a pretty-print function to print the tree
Our binary search tree first will be represented by a std::vector of node elements. (Later we will use pointers instead of vector and indexes.) The nodes contain the data which we store, and pointers to the left, right and parent nodes implemented by the indexes in the vector of those nodes.
As a first step, create a function to print the content of the tree using paretheses representing the levels in the tree.
The function should look like: void printBinTree(const std::vector
Update!
Use the -std=c++14 (or -std=c++17 or -std=c++20) compiler flag to compile the example below. Some of the older compilers do not like the aggregate initialization of the std::vector class.
The following is a program to test your function (don’t upload this to Canvas, only the printBinTree function).
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
#include <iostream>
#include <vector>
struct node { /* one node */
int data; /* data in the node */
int leftIdx = -1; /* left child */
int rightIdx = -1; /* right child */
int parentIdx = -1; /* parent */
};
/* the function to implement */
void printBinTree(const std::vector<node>& bt);
int main() {
std::vector<node> b1 = {
{ 42, 1, 2, -1},
{ 23, 4, 3, 0},
{ 56, 6, 5, 0},
{ 32, -1, -1, 1},
{ 8, -1, -1, 1},
{ 99, -1, -1, 2},
{ 42, -1, -1, 2}
};
std::vector<node> b2 = {
{ 5, 3, 1, -1},
{ 5, -1, 2, 0},
{ 9, -1, 4, 1},
{ 3, -1, 7, 0},
{ 66, -1, 5, 2},
{ 88, 6, -1, 4},
{ 87, -1, -1, 5},
{ 4, -1, -1, 3}
};
printBinTree(b1); /* prints ((8)23(32))42((42)56(99)) */
printBinTree(b2); /* prints (3(4))5(5(9(66((87)88)))) */
return 0;
}
Be careful, that this test program works only when the node elements are representing a correct binary tree. At this point you can suppose that the vector parameter holds the binary tree invariants. However, your program should work for other correct binary trees too.
Create your additional test cases and check your program for corner cases.
Submit your solution to Canvas by March 24, Sunday, 23:59h, copying only the source of the printBinTree() function into the textbox.
Solution
This is one possible solution. There might be many possible good solutions.
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
#include <iostream>
#include <vector>
struct node { /* one node */
int data; /* data in the node */
int leftIdx = -1; /* left child */
int rightIdx = -1; /* right child */
int parentIdx = -1; /* parent */
};
/* the function to implement */
void printBinTree(const std::vector<node>& bt);
void printSubTree(const std::vector<node>& tree, int idx) {
if (-1 != tree[idx].leftIdx) {
std::cout << '(';
printSubTree(tree, tree[idx].leftIdx);
std::cout << ')';
}
std::cout << tree[idx].data;
if (-1 != tree[idx].rightIdx) {
std::cout << '(';
printSubTree(tree, tree[idx].rightIdx);
std::cout << ')';
}
}
void printBinTree(const std::vector<node>& tree) {
if ( tree.size() > 0 ) // if ( std::ssize(tree) > 0 )
printSubTree(tree,0);
}
int main() {
std::vector<node> b1 = {
{ 42, 1, 2, -1},
{ 23, 4, 3, 0},
{ 56, 6, 5, 0},
{ 32, -1, -1, 1},
{ 8, -1, -1, 1},
{ 99, -1, -1, 2},
{ 42, -1, -1, 2}
};
std::vector<node> b2 = {
{ 5, 3, 1, -1},
{ 5, -1, 2, 0},
{ 9, -1, 4, 1},
{ 3, -1, 7, 0},
{ 66, -1, 5, 2},
{ 88, 6, -1, 4},
{ 87, -1, -1, 5},
{ 4, -1, -1, 3}
};
std::vector<node> b3 = {};
std::vector<node> b4 = {
{ 5, -1, -1, -1}
};
std::vector<node> b5 = {
{ 1, -1, 1, -1},
{ 2, -1, 2, 0},
{ 3, -1, 3, 1},
{ 4, -1, 4, 2},
{ 5, -1, -1, 3},
};
printBinTree(b1); /* prints ((8)23(32))42((42)56(99)) */
printBinTree(b2); /* prints (3(4))5(5(9(66((87)88)))) */
printBinTree(b3); /* prints */
printBinTree(b4); /* prints 5 */
printBinTree(b5); /* prints 1(2(3(4(5)))) */
return 0;
}
Task 2: Rewrite the Task 1 using pointers
In the Task 2 you should re-implement the binary tree using pointers. Each node is created in the heap memory with operator new. We have to implement the printBinTree(node *r) function and the insertBinTree(node *&r, int val) function to insert a new element under the tree.
The following is a program to test your functions (don’t upload this).
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
#include <iostream>
#include <vector>
struct node {
int data;
node *left = nullptr;
node *right = nullptr;
};
// implement these 2 functions
void printBinTree(node *root);
void insertBinTree(node *&root, int val);
void insertFromVector( node *&bt, std::vector<int> v) {
for ( int i = 0; i < v.size(); ++i) {
insertBinTree(bt, v[i]);
}
}
int main() {
std::vector<int> v1 = {42, 23, 56, 32, 8, 99, 42 };
std::vector<int> v2 = { 5, 5, 9, 3, 66, 88, 87, 4 };
std::vector<int> v3 = { };
std::vector<int> v4 = { 5 };
std::vector<int> v5 = { 1, 2, 3, 4, 5 };
for ( auto v : { v1, v2, v3, v4, v5 } ) {
node *bt = nullptr;
insertFromVector(bt, v);
printBinTree(bt); std::cout << '\n';
/* prints ((8)23(32))42((42)56(99)) */
/* prints (3(4))5(5(9(66((87)88)))) */
/* prints */
/* prints 5 */
/* prints 1(2(3(4(5)))) */
}
return 0;
}
Be careful, that this test program should work for any integer inputs.
Submit your solution to Canvas by April 14, Sunday, 23:59h, copying only the source of the void printBinTree(node *root) and void insertBinTree(node *&root, int val) functions into the textbox.
Solution
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
#include <iostream>
#include <vector>
struct node {
int data;
node *left = nullptr;
node *right = nullptr;
};
void printBinTree(node *root) {
if ( root ) {
if ( root->left ) {
std::cout << '(';
printBinTree( root->left );
std::cout << ')';
}
std::cout << root->data;
if ( root->right ) {
std::cout << '(';
printBinTree( root->right );
std::cout << ')';
}
}
}
void insertBinTree(node *&root, int val) {
if ( root ) {
if ( val < root->data ) {
insertBinTree(root->left, val);
}
else {
insertBinTree(root->right, val);
}
}
else {
root = new node{val,nullptr,nullptr};
}
}
void insertFromVector( node *&bt, std::vector<int> v) {
for ( int i = 0; i < v.size(); ++i) {
insertBinTree(bt, v[i]);
}
}
int main() {
std::vector<int> v1 = {42, 23, 56, 32, 8, 99, 42 };
std::vector<int> v2 = { 5, 5, 9, 3, 66, 88, 87, 4 };
std::vector<int> v3 = { };
std::vector<int> v4 = { 5 };
std::vector<int> v5 = { 1, 2, 3, 4, 5 };
for ( auto v : { v1, v2, v3, v4, v5 } ) {
node *bt = nullptr;
insertFromVector(bt, v);
printBinTree(bt); std::cout << '\n';
/* prints ((8)23(32))42((42)56(99)) */
/* prints (3(4))5(5(9(66((87)88)))) */
/* prints */
/* prints 5 */
/* prints 1(2(3(4(5))))) */
}
return 0;
}
Task 3: Create a BinTree class
Write a BinTree class based on the functions implemented for Task2. Define a constructor which creates a binary tree from a (possible empty) vector. Define destructor to clean up the dynamic memory. No copy or move operations are defined. Define insert(v) and contains(v) public member functions. Insert has no return value and inserts v as a new element, while contains(v) returns a bool value whether the tree contains element v. Define the output operator (and care with the chaining of outputs). Separate your solution into a header file and a source file.
Here is a main function to test your solution:
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
#include <iostream>
#include <vector>
#include "bintree.h"
int main() {
std::vector<int> v1 = {42, 23, 56, 32, 8, 99, 42 };
std::vector<int> v2 = { 5, 5, 9, 3, 66, 88, 87, 4 };
std::vector<int> v3 = { };
std::vector<int> v4 = { 5 };
std::vector<int> v5 = { 1, 2, 3, 4, 5 };
for ( auto v : { v1, v2, v3, v4, v5 } ) {
BinTree bt(v); // uses insert() to insert the elements
std::cout << bt << ' '
<< std::boolalpha << bt.contains(5) << '\n';
/* prints ((8)23(32))42((42)56(99)) false */
/* prints (3(4))5(5(9(66((87)88)))) true */
/* prints false */
/* prints 5 true */
/* prints 1(2(3(4(5))))) true */
}
BinTree bt;
std::cout << std::boolalpha << bt.contains(5) << '\n'; // false
bt.insert(4); bt.insert(5);
std::cout << bt << '\n'; // 4(5)
std::cout << std::boolalpha << bt.contains(5) << '\n'; // true
return 0;
}
Define the class in bintree.h and implement the functions in bintree.cpp. When submit the solution, just copy them each after to the canvas text box separated by a “******” line. Submit your solution on Canvas by May 5, Sunday, 23:59..