I need help with a C++ Ordered Binary Tree. Here is the problem: Write a program

Question

I need help with a C++ Ordered Binary Tree. Here is the problem:

Write a program to read in a set of numbers and build an ordered binary tree. For the given tree, compute the following:

a. Print out the tree in inorder

b. Print out the tree in preorder

c. Print out the tree in postorder

d. Print out the number of nodes in the tree. (Traverse the tree and count the nodes)

e. Sum up all the values in the tree and compute the average

f. Count the number of leafs in the tree

g. Print the value that is the deepest in the tree

The numbers in the file are like this: 75 97 82 47 90 59 23 51 36 110 66 102 69 79 13 130 49 41 19 67 85 64 115 30 94

Don't use classes for this program if possible.

Explanation / Answer

//Binary Search Tree Program

#include <iostream>
#include <cstdlib>
using namespace std;

class BinarySearchTree
{
private:
struct tree_node
{
tree_node* left;
tree_node* right;
int data;
};
tree_node* root;

public:
BinarySearchTree()
{
root = NULL;
}

bool isEmpty() const { return root==NULL; }
void print_inorder();
void inorder(tree_node*);
void print_preorder();
void preorder(tree_node*);
void print_postorder();
void postorder(tree_node*);
void insert(int);
void remove(int);
void leafcount(tree_node*);
};

// Smaller elements go left
// larger elements go right
void BinarySearchTree::insert(int d)
{
tree_node* t = new tree_node;
tree_node* parent;
t->data = d;
t->left = NULL;
t->right = NULL;
parent = NULL;

// is this a new tree?
if(isEmpty()) root = t;
else
{
//Note: ALL insertions are as leaf nodes
tree_node* curr;
curr = root;
// Find the Node's parent
while(curr)
{
parent = curr;
if(t->data > curr->data) curr = curr->right;
else curr = curr->left;
}

if(t->data < parent->data)
parent->left = t;
else
parent->right = t;
}
}

void BinarySearchTree::remove(int d)
{
//Locate the element
bool found = false;
if(isEmpty())
{
cout<<" This Tree is empty! "<<endl;
return;
}

tree_node* curr;
tree_node* parent;
curr = root;

while(curr != NULL)
{
if(curr->data == d)
{
found = true;
break;
}
else
{
parent = curr;
if(d>curr->data) curr = curr->right;
else curr = curr->left;
}
}
if(!found)
{
cout<<" Data not found! "<<endl;
return;
}


// 3 cases :
// 1. We're removing a leaf node
// 2. We're removing a node with a single child
// 3. we're removing a node with 2 children

// Node with single child
if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL
&& curr->right == NULL))
{
if(curr->left == NULL && curr->right != NULL)
{
if(parent->left == curr)
{
parent->left = curr->right;
delete curr;
}
else
{
parent->right = curr->right;
delete curr;
}
}
else // left child present, no right child
{
if(parent->left == curr)
{
parent->left = curr->left;
delete curr;
}
else
{
parent->right = curr->left;
delete curr;
}
}
return;
}

//We're looking at a leaf node
if( curr->left == NULL && curr->right == NULL)
{
if(parent->left == curr) parent->left = NULL;
else parent->right = NULL;
delete curr;
return;
}


//Node with 2 children
// replace node with smallest value in right subtree
if (curr->left != NULL && curr->right != NULL)
{
tree_node* chkr;
chkr = curr->right;
if((chkr->left == NULL) && (chkr->right == NULL))
{
curr = chkr;
delete chkr;
curr->right = NULL;
}
else // right child has children
{
//if the node's right child has a left child
// Move all the way down left to locate smallest element

if((curr->right)->left != NULL)
{
tree_node* lcurr;
tree_node* lcurrp;
lcurrp = curr->right;
lcurr = (curr->right)->left;
while(lcurr->left != NULL)
{
lcurrp = lcurr;
lcurr = lcurr->left;
}
curr->data = lcurr->data;
delete lcurr;
lcurrp->left = NULL;
}
else
{
tree_node* tmp;
tmp = curr->right;
curr->data = tmp->data;
curr->right = tmp->right;
delete tmp;
}

}
return;
}

}

void BinarySearchTree::print_inorder()
{
inorder(root);
}

void BinarySearchTree::inorder(tree_node* p)
{
if(p != NULL)
{
if(p->left) inorder(p->left);
cout<<" "<<p->data<<" ";
if(p->right) inorder(p->right);
}
else return;
}

void BinarySearchTree::print_preorder()
{
preorder(root);
}

void BinarySearchTree::preorder(tree_node* p)
{
if(p != NULL)
{
cout<<" "<<p->data<<" ";
if(p->left) preorder(p->left);
if(p->right) preorder(p->right);
}
else return;
}

void BinarySearchTree::print_postorder()
{
postorder(root);
}

void BinarySearchTree::postorder(tree_node* p)
{
if(p != NULL)
{
if(p->left) postorder(p->left);
if(p->right) postorder(p->right);
cout<<" "<<p->data<<" ";
}
else return;
}

void BinarySearchTree::print_leafcount()
{
leafcount(root);
}

int BinarySearchTree::leafcount(tree_node* p)
{
if(p == NULL)
return 0;
if(p->left == NULL && p->right==NULL)
return 1;
else
return getLeafCount(p->left)+getLeafCount(p->right);
}

void BinarySearchTree::print_nodecount(tree_node* p)
{
nodecount(root);
}

int BinarySearchTree::nodecount(tree_node* p)
{
int sum= 0;

while (p) {
sum++;
if (p->left) {
if (p->right) sum += nodecount (p->right);
p = p->left;

} else p = p->right;
}
return sum;
}

void BinarySearchTree::print_deepestnode(tree_node* p)
{
deepestnode(root);
}

void BinarySearchTree::deepestnode(tree_node* p)
{
if (p == NULL)
return 0;
else {
// compute the depth of each subtree
int lDepth = deepestnode(p->left);
int rDepth = deepestnode(p->right);

// use the larger one
if(lDepth > rDepth)
{
cout<<p->left->data;
return(lDepth+1);
}
else
{
cout<<p->right->data;
return(rDepth+1);
}
}
}

int main()
{
BinarySearchTree b;
int ch,tmp,tmp1;
while(1)
{
cout<<endl<<endl;
cout<<" Binary Search Tree Operations "<<endl;
cout<<" ----------------------------- "<<endl;
cout<<" 1. Insertion/Creation "<<endl;
cout<<" 2. In-Order Traversal "<<endl;
cout<<" 3. Pre-Order Traversal "<<endl;
cout<<" 4. Post-Order Traversal "<<endl;
cout<<" 5. Removal "<<endl;
cout<<" 6. leafcount "<<endl;
cout<<" 7. nodecount "<<endl;
cout<<" 8. deepestvalue "<<endl;
cout<<" 9. exit "<<endl;
cout<<" Enter your choice : ";
cin>>ch;
switch(ch)
{
case 1 : cout<<" Enter Number to be inserted : ";
cin>>tmp;
b.insert(tmp);
break;
case 2 : cout<<endl;
cout<<" In-Order Traversal "<<endl;
cout<<" -------------------"<<endl;
b.print_inorder();
break;
case 3 : cout<<endl;
cout<<" Pre-Order Traversal "<<endl;
cout<<" -------------------"<<endl;
b.print_preorder();
break;
case 4 : cout<<endl;
cout<<" Post-Order Traversal "<<endl;
cout<<" --------------------"<<endl;
b.print_postorder();
break;
case 5 : cout<<" Enter data to be deleted : ";
cin>>tmp1;
b.remove(tmp1);
break;
case 6 : cout<<endl;
cout<<" leafcount "<<endl;
cout<<" --------------------"<<endl;
cout<<b.print_leafcount();
break;
case 7 : cout<<endl;
cout<<" nodecount "<<endl;
cout<<" --------------------"<<endl;
cout<<b.print_nodecount();
break;
case 9 : cout<<endl;
cout<<" deepestnode "<<endl;
cout<<" --------------------"<<endl;
cout<<" the last value printed is the deepest value "<<endl;
cout<<b.print_deepestnode();
break;
case 8 :
return 0;

}
}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.