Homework SourseTry to get the following code implementing a binary tree run
Try to get the following code implementing a binary tree running and document each function and necessary variable ( remove the unnecessary code.) Be sure to list any preconditions and post conditions for each function. Make sure all of the functions are working.
///Binary Tree
#include <iostream>
#include
#include <cmath>
#include \"Queue.h\"
using namespace std;
template < typename T >
class TreeNode
{
public:
T element; //
TreeNode < T > * left; //
TreeNode < T > * right; //
TreeNode() //
{
left = NULL;
next = NULL;
}
TreeNode(T element) // Constructor
{
this->element = element;
left = NULL;
right = NULL;
}
};
template < typename T >
class BinaryTree
{
public:
BinaryTree();
BinaryTree(T elements[], int arraySize);
bool insert(T element);
void inorder();
void preorder();
void postorder();
int getSize();
bool search(T element);
void breadthFirstTraversal();
int depth();
private:
TreeNode < T > * root;
int size;
void inorder(TreeNode < T > * root);
void postorder(TreeNode < T > * root);
void preorder(TreeNode < T > * root);
bool search(T element, TreeNode < T > * root);
int depth(TreeNode * root);
};
template < typename T >
BinaryTree < T >::BinaryTree()
{
root = NULL;
size = 0;
}
template < typename T >
BinaryTree < T >::BinaryTree(T elements[], int arraySize)
{
root = NULL;
size = 0;
for (int i = 0; i < arraySize; i++)
{
insert(elements[i]);
}
}
template < typename T >
bool BinaryTree < T >::insert(T element)
{
if (root == NULL)
root = new TreeNode < T > (element); // Create a new root
else
{
// Locate the parent node
TreeNode < T > * parent = NULL;
TreeNode < T > * current = root;
while (current != NULL)
if (element < current->element)
{
parent = current;
current = current->left;
}
else if (element > current->element)
{
parent = current;
current = current->right;
}
else
return false; // Duplicate node not inserted
// Create the new node and attach it to the parent node
if (element < parent->element)
parent->left = new TreeNode < T > (element);
else
parent->right = new TreeNode < T > (element);
}
size++;
return true; // Element inserted
}
/* Inorder traversal */
template < typename T >
void BinaryTree < T >::inorder()
{
inorder(root);
}
/* Inorder traversal from a subtree */
template < typename T >
void BinaryTree < T >::inorder(TreeNode < T > * root)
{
if (root == NULL) return;
inorder(root->left);
cout << root->element << \" \";
inorder(root->right);
}
/* Postorder traversal */
template < typename T >
void BinaryTree < T >::postorder()
{
postorder(root);
}
/** Inorder traversal from a subtree */
template < typename T >
void BinaryTree < T >::postorder(TreeNode < T > * root)
{
if (root == NULL) return;
postorder(root->left);
postorder(root->right);
cout << root->element << \" \";
}
/* */
template < typename T >
void BinaryTree < T >::preorder()
{
preorder(root);
}
/* */
template < typename T >
void BinaryTree < T >::preorder(TreeNode < T > * root)
{
if (root == NULL) return;
cout << root->element << \" \";
preorder(root->left);
preorder(root->right);
}
/**/
template < typename T >
int BinaryTree < T >::getSize()
{
return size;
}
template < typename T >
bool BinaryTree < T >::search(T element)
{
return search(element, root);
}
template < typename T >
bool BinaryTree < T >::search(T element, TreeNode < T > * root)
{
if (root == NULL)
return false;
else if (root->element == element)
return true;
else if (root->element > element)
return search(element, root->right);
else
return search(element, root->left);
}
int main()
{
BinaryTree < string > tree1;
tree1.insert(\"George\");
tree1.insert(\"Michael\");
tree1.insert(\"Tom\");
tree1.insert(\"Adam\");
tree1.insert(\"Jones\");
tree1.insert(\"Peter\");
tree1.insert(\"Daniel\");
cout << \"Inorder (sorted): \";
tree1.inorder();
cout << \"\ Postorder: \";
tree1.postorder();
cout << \"\ Preorder: \";
tree1.preorder();
cout << \"\ The number of nodes is \" << tree1.getSize();
int numbers[] =
{
2, 4, 3, 1, 8, 5, 6, 7
};
BinaryTree < int > tree2(numbers, 8);
cout << \"\ Inorder (sorted): \";
tree2.inorder();
cout << \"\ search 2 \" << tree2.search(2) << endl;
cout << \"\ search 99 \" << tree2.search(99) << endl;
cout << \"\ search 8 \" << tree2.search(8) << endl;
return 0;
}
FOR EACH OF THE FOLLOWING PROBLEMS MAKE SURE TO DOCUMENT THE NEW CODE AND THE TESTING CODE. ALSO, EXPLAIN IN DETAILING A DESCRIPTION OF YOUR CODE DESIGN AND INCLUDING RESULTS FROM YOUR TEST RUNS.
Add a breadth-first (level-order) traversal function to the binary tree code.
Add a function to find the height of a tree.
Re-implement one of the depth-first traversal methods using a stack instead of recursion.
Add a link to each nodes parent node.
Solution
Note:
In the given code the below functions are implemented
Solution:
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
using namespace std;
template < typename T >
class TreeNode
{
public:
T element; //
TreeNode < T > * left; //
TreeNode < T > * right; //
TreeNode <T> * next;
TreeNode() //
{
left = NULL;
next = NULL;
}
TreeNode(T element) // Constructor
{
this->element = element;
left = NULL;
right = NULL;
}
};
template < typename T > class BinaryTree
{
public:
BinaryTree();
BinaryTree(T elements[], int arraySize);
bool insert(T element);
void inorder();
void preorder();
void postorder();
int getSize();
bool search(T element);
void breadthFirstTraversal();
int depth();
private:
TreeNode < T > * root;
int size;
void inorder(TreeNode < T > * root);
void postorder(TreeNode < T > * root);
void preorder(TreeNode < T > * root);
bool search(T element, TreeNode < T > * root);
int depth(TreeNode<T> * root);
void printLvlOrdr(TreeNode < T > * root);
void printGvnLvl(TreeNode < T > * root, int lvl);
};
// method to get the height of the tree
template < typename T > int BinaryTree < T >::depth()
{
return depth(root);
}
// method to perfrom breadth first traversal
template < typename T > void BinaryTree < T >::breadthFirstTraversal()
{
printLvlOrdr(root);
}
// method to print level order of the tree
template < typename T > void BinaryTree < T >::printLvlOrdr(TreeNode < T > * root)
{
int height = depth(root);
int ilp;
for (ilp=1; ilp<=height; ilp++)
printGvnLvl(root, ilp);
}
/* Print nodes at a given level */
template < typename T > void BinaryTree < T >::printGvnLvl(TreeNode < T > * root, int lvl)
{
if (root == NULL)
return;
if (lvl == 1)
cout<<\" \"<<root->element;
else if (lvl > 1)
{
printGvnLvl(root->left, lvl-1);
printGvnLvl(root->right, lvl-1);
}
}
// method to compute depth
template < typename T > int BinaryTree < T >::depth(TreeNode < T > * elmnt)
{
if (elmnt==NULL)
return 0;
else
{
int lftDepth = depth(elmnt->left);
int rgtDepth = depth(elmnt->right);
// use the larger one
if (lftDepth > rgtDepth)
return(lftDepth+1);
else
return(rgtDepth+1);
}
}
template < typename T > BinaryTree < T >::BinaryTree()
{
root = NULL;
size = 0;
}
template < typename T > BinaryTree < T >::BinaryTree(T elements[], int arraySize)
{
root = NULL;
size = 0;
for (int i = 0; i < arraySize; i++)
{
insert(elements[i]);
}
}
template < typename T > bool BinaryTree < T >::insert(T element)
{
if (root == NULL)
root = new TreeNode < T > (element); // Create a new root
else
{
// Locate the parent node
TreeNode < T > * parent = NULL;
TreeNode < T > * current = root;
while (current != NULL)
if (element < current->element)
{
parent = current;
current = current->left;
}
else if (element > current->element)
{
parent = current;
current = current->right;
}
else
return false; // Duplicate node not inserted
// Create the new node and attach it to the parent node
if (element < parent->element)
parent->left = new TreeNode < T > (element);
else
parent->right = new TreeNode < T > (element);
}
size++;
return true; // Element inserted
}
/* Inorder traversal */
template < typename T > void BinaryTree < T >::inorder()
{
inorder(root);
}
/* Inorder traversal from a subtree */
template < typename T > void BinaryTree < T >::inorder(TreeNode < T > * root)
{
if (root == NULL) return;
inorder(root->left);
cout << root->element << \" \";
inorder(root->right);
}
/* Postorder traversal */
template < typename T > void BinaryTree < T >::postorder()
{
postorder(root);
}
/** Inorder traversal from a subtree */
template < typename T > void BinaryTree < T >::postorder(TreeNode < T > * root)
{
if (root == NULL) return;
postorder(root->left);
postorder(root->right);
cout << root->element << \" \";
}
/* */
template < typename T > void BinaryTree < T >::preorder()
{
preorder(root);
}
/* */
template < typename T > void BinaryTree < T >::preorder(TreeNode < T > * root)
{
if (root == NULL) return;
cout << root->element << \" \";
preorder(root->left);
preorder(root->right);
}
/**/
template < typename T > int BinaryTree < T >::getSize()
{
return size;
}
template < typename T > bool BinaryTree < T >::search(T element)
{
return search(element, root);
}
template < typename T > bool BinaryTree < T >::search(T element, TreeNode < T > * root)
{
if (root == NULL)
return false;
else if (root->element == element)
return true;
else if (root->element > element)
return search(element, root->right);
else
return search(element, root->left);
}
int main()
{
BinaryTree < string > tree1;
tree1.insert(\"George\");
tree1.insert(\"Michael\");
tree1.insert(\"Tom\");
tree1.insert(\"Adam\");
tree1.insert(\"Jones\");
tree1.insert(\"Peter\");
tree1.insert(\"Daniel\");
cout << \"Inorder (sorted): \";
tree1.inorder();
cout << \"\ Postorder: \";
tree1.postorder();
cout << \"\ Preorder: \";
tree1.preorder();
cout << \"\ The number of nodes is \" << tree1.getSize();
int numbers[] ={2, 4, 3, 1, 8, 5, 6, 7};
BinaryTree < int > tree2(numbers, 8);
cout << \"\ Inorder (sorted): \";
tree2.inorder();
cout << \"\ search 2 \" << tree2.search(2) << endl;
cout << \"\ search 99 \" << tree2.search(99) << endl;
cout << \"\ search 8 \" << tree2.search(8) << endl;
cout<<\"Height is \" << tree2.depth();
cout<<\"\ BFS \" ;
tree2.breadthFirstTraversal();
system(\"pause\");
return 0;
}
Result:
Inorder (sorted): Adam Daniel George Jones Michael Peter Tom
Postorder: Daniel Adam Jones Peter Tom Michael George
Preorder: George Adam Daniel Michael Jones Tom Peter
The number of nodes is 7
Inorder (sorted): 1 2 3 4 5 6 7 8
search 2 1
search 99 0
search 8 0
Height is 6
BFS 2 1 4 3 8 5 6
