Description
Lab4 exercises your understanding of BINARY TREES, with particular attention to:
Traversals
Insertion
Dynamic memory and pointers
Follow these steps:
1) place the given and requested code in file L4.cpp and upload when completed to Canvas
2) use the following type definition, given in class on Wednesday 10/21/15
struct TNode
{ int data;
TNode* left;
TNode* right;
};
3) using a function, construct a binary tree containing 5 to 10 values. You may ‘cheat’ in this step (as a warmup; insert() is a difficult routine, to be covered later in the lab) by simply inputting values; the start of your construct-function code should look similar to:
TNode* root = new TNode;
root->data = firstValue;
root->left = nullptr; // 0 also fine
root->right = nullptr; // 0 also fine
TNode* auxPtr = root;
…
// add to both the left and right subtrees of root
// ensure that all leaf nodes have null links
…
4) write and verify the recursive traversal of your binary tree (print out contents), for:
a. preorder
b. postorder
c. inorder
5) if necessary, modify #3 so that your binary tree is a binary search tree (BST)
6) write and verify a function to INSERT a given value into your BST, preserving the BST property
7) write and verify a function to DELETE a given value from your BST, preserving the BST property
8) Use #6 to replace #3 with a general construction routine
