$20
Data Structure-lab 15 Binary Trees part 2 Solved
This lab continues our construction of Binary Trees. For this lab extend your previous implementation of Binary Search Tree with contains, delete, remove, existsInRange, and countInRange.
#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!
*/ void put(const T &val);
/* Returns the height of the binary tree. */ int getHeight();
/* Returns true if an item exists in the Binary Tree */ bool contains(const T &val) const;
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
/* Removes a specific val from the Binary Tree. * Returns true if the value exists (and was removed.) * Otherwise, returns false.
*/ bool remove(const T &val);
/* This method returns true iff there is a value in the tree
* >= min and <= max. In other words, it returns true if there
* is an item in the tree in the range [min, max]
*/ bool existsInRange(T min, T max) const;
/* This is similar but it returns the number of items in the range. */ int countInRange(T min, T max) const;
/* Returns a string representation of the binary Tree in order. */ std::string inorderString();
/* Returns a string representation of the binary Tree pre order. */ std::string preorderString();
/* Returns a string representation of the binary Tree pre order. */ std::string postorderString();
/* Does an inorder traversal of the Binary Search Tree calling * visit on each node.
*/ void inorderTraversal(void (*visit) (T &item)) const;
/* 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
74
75
76
77
78
79
80
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!
