Your cart is currently empty!
Exercise 1: Binary trees Let consider the following template of binary trees template <typename T> class BinaryTree{ private: Declare a structure for the list struct TreeNode { T value; struct TreeNode *left; struct TreeNode *right; }; A function to create a node TreeNode…
Exercise 1: Binary trees
Let consider the following template of binary trees
template <typename T>
class BinaryTree{
private:
{
T value;
struct TreeNode *left; struct TreeNode *right;
};
TreeNode *node = new TreeNode; node->value = key;
node->left = NULL; node->right = NULL; return node;
}
public:
BinaryTree (void) // Constructor
{ root = NULL; }
1
BinaryTree (T);
T& pop_front(); bool empty(); void insertNode(T);
void deleteNode(T, bool); void preOrderTraversal(); void inOrderTraversal(); void postOrderTraversal(); int countLesserThan(T); int countGreaterThan(T); int length();
int height(); void clear(); void mirror();
bool isIdenticalTo(BinaryTree); bool isIsomorphicWith(BinaryTree); int countLeafNodes();
int countSemiLeafNodes();
};
Suppose that this class permits the manipulation of binary search trees. Write an algorithm (Pseudo-code please, no sentences!!) and a C++ program for each of the following methods for this BinaryTree class:
Hint: use the function TreeNode * createNode(T key);
2
example input and output for mirror().
4 | 4 | ||
/ \ | / \ | ||
2 | 5 | 5 | 2 |
/ \ | / \ | ||
1 | 3 | 3 | 1 |
INPUT TREE | OUTPUT TREE |
3
Hint: some method can reuse other methods, like for example you can reuse the method clear() in the destructor.
Exercise 2: Binary min-heap
We saw in class that a binary min-heap can be represented by an array as illustrated in the figure 1.
Figure 1
For a given entry , it follows that the parent node is at /2, the left child is at the index 2k and the right child it at the index 2 + 1 as shown in the figure 2.
Figure 2
The aim is to implement a class in C++ that manipulate the binary min-heap. For that purpose, let the following template of the binary min-heap:
template <typename T>
class BinaryMinHeap{
private:
T *array; // An array to store the binary min-heap int capacity; // the capacity of this array int size; // the current size of this array
public:
4
BinaryMinHeap (void)
{ array = NULL;
capacity = 0;
size = 0;
// Constructor
}
BinaryMinHeap (int Capacity);
T getMin();
T extractMin();
void deleteNode(int nodeI);
void decreaseKey(int node, int new_val); void insertKey(T val);
T getLeftChild(int nodeI); T getRightChild(int nodeI); bool empty():
};
int temp = *x; *x = *y;
*y = temp;
}
Write an algorithm (Pseudo-code please, no sentences!!) and a C++ program for each of the following methods for this BinaryMinHeap class:
5
6