This lab begins our construction of Binary Trees. It is very important to get these basics down before proceeding to further functionality of Trees. Please implement empty constructor, copy constructor, put, inorderString, lowest common ancestor (LCA), and a deconstructor.
#ifndef BINARY_TREE_H
#define BINARY_TREE_H #include <string>
template<class T> class BinaryTreeNode { public:
BinaryTreeNode<T> () {
} };
template<class T> class BinaryTree { private:
/* You fill in private member data. */
/* Recommended, but not necessary helper function. */ void put(BinaryTreeNode<T> *rover, BinaryTreeNode<T> *newNode);
/* Recommended, but not necessary helper function. */ std::string inorderString(BinaryTreeNode<T> *node, std::string &ret);
public:
/* Creates an empty binary tree. */ BinaryTree();
/* Does a deep copy of the tree. */
BinaryTree(const BinaryTree<T> &tree);
/* Add a given value to the Binary Tree.
* Must maintain ordering!
* Do NOT do ANY balancing!
*/ void put(const T &val);
/* Returns the height for the binary tree. */ int getHeight();
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
/* Returns a string representation of the binary Tree in order. */ /* The tree:
4
/ \ 1 10
should return:
"1 4 10 "
without the quotes, but notice that space at the end. */
std::string inorderString();
/* Return the lowest common ancestor (LCA) of two values.
* The LCA is the most immediate parent of both values. For example:
* 4
* / \
* 2 8
* / \ / \
* 1 3 6 10
* LCA(1, 3) = 2
* LCA(1, 2) = 2
* LCA(1, 6) = 4
*/
T& lca(T& a, T& b);
/* Always free memory. */
~BinaryTree();
};
/* Since BinaryTree is templated, we include the .cpp.
* Templated classes are not implemented until utilized (or explicitly
* declared.)
*/
#include "binarytree.cpp"
#endif
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
Write some test cases:
Create some test cases, using cxxtestgen, that you believe would cover all aspects of your code.
Memory Management:
Now that are using new, we must ensure that there is a corresponding delete to free the memory. Ensure there are no memory leaks in your code! Please run Valgrind on your tests to ensure no memory leaks!
