Modify the code on BST and implement the Delete Node algorithms. Consider all the three deleting algorithms. - a leaf node - a node with one child and - a node with two children
Modify the code on BST and implement the Delete Node
- a leaf node
- a node with one child and
- a node with two children
Here is the code so far:
#include <iostream>
using namespace std;
struct Tree
{
char data;
Tree *left;
Tree *right;
Tree *parent;
};
const int size=10;
struct Tree *newTreeNode(int data)
{
Tree *node = new Tree;
node->data = data;
node->left = NULL;
node->right = NULL;
node->parent = NULL;
return node;
}
struct Tree* insertTreeNode(struct Tree *node, int data)
{
static Tree *p; //retains its value between calls to this function
Tree *retNode;
if(node == NULL) {
retNode = newTreeNode(data);
retNode->parent = p;
return retNode;
}
if(data <= node->data ) {
p = node;
node->left = insertTreeNode(node->left,data);
}
else {
p = node;
node->right = insertTreeNode(node->right,data);
}
return node;
}
Tree* lookUp(struct Tree *node, char key)
{
if(node == NULL) return node;
if(node->data == key) return node;
else {
if(node->data < key)
return lookUp(node->right, key) ;
else
return lookUp(node->left, key);
}
}
int treeSize(struct Tree *node)
{
if(node == NULL)
return 0;
else
return treeSize(node->left) + 1 + treeSize(node->right);
}
int maxDepth(struct Tree *node)
{
if(node == NULL || (node->left == NULL && node->right == NULL))
return 0;
int leftDepth = maxDepth(node->left);
int rightDepth = maxDepth(node->right);
if (leftDepth > rightDepth )
return leftDepth + 1;
else
return rightDepth + 1;
}
int minDepth(struct Tree *node)
{
if(node == NULL || (node->left == NULL && node->right == NULL))
return 0;
int leftDepth = minDepth(node->left);
int rightDepth = minDepth(node->right);
if (leftDepth < rightDepth )
return leftDepth + 1;
else
return rightDepth + 1;
}
bool isBalanced(struct Tree *node)
{
if(maxDepth(node)-minDepth(node) <= 1)
return true;
else
return false;
}
/* Tree Minimum */
Tree* minTree(struct Tree *node)
{
if(node == NULL) return NULL;
while(node->left)
node = node -> left;
return node;
}
/* Tree Maximum */
Tree* maxTree(struct Tree *node)
{
while(node->right)
node = node -> right;
return node;
}
int main(int argc, char **argv)
{
char ch;
Tree *found;
/* Data for building the Tree */
char charArr[] = {'F','B','A','D','C','E','H','I','G','K'};
Tree *root = newTreeNode(charArr[0]);
for (int i=1; i < size; i++)
{
insertTreeNode(root,charArr[i]);
}
/* size of tree */
cout << "Data size in the tree = " << treeSize(root) << endl;
/* max depth */
cout << "Maximum depth = " << maxDepth(root) << endl;
/* min depth */
cout << "Minimum depth = " << minDepth(root) << endl;
/* balanced tree? */
if(isBalanced(root))
cout << "This tree is balanced!\n";
else
cout << "This tree is not balanced!\n";
/* min value of the tree*/
if(root)
cout << "Min value = " << minTree(root)->data << endl;
/* max value of the tree*/
if(root)
cout << "Max value = " << maxTree(root)->data << endl;
/* Example of Min and Max value in a sub tree */
ch = 'H';
found = lookUp(root,ch);
if(found) {
cout << "Min value of subtree " << ch << " as a root is "
<< minTree(found)->data << endl;
cout << "Max value of subtree " << ch << " as a root is "
<< maxTree(found)->data << endl;
}
return 0;
}
Step by step
Solved in 2 steps
