Homework Sourse1 Add a breadthfirst levelorder traversal function to the bi
1. Add a breadth-first (level-order) traversal function to the binary tree code.
2. Add a function to find the height of a tree.
3. Re-implement one of the depth-first traversal methods using a stack instead of recursion.
4. Add a link to each nodes parent node.
#include <iostream>
#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);
};
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;
}
Solution
#include <iostream>
#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();
void BFS();
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 printLevelOrder(TreeNode < T > * root);
void printGivenLevel(TreeNode < T > * root, int level);
};
template < typename T >
int BinaryTree < T >::depth()
{
depth(root);
}
template < typename T >
void BinaryTree < T >::BFS()
{
printLevelOrder(root);
}
template < typename T >
void BinaryTree < T >::printLevelOrder(TreeNode < T > * root)
{
int h = depth(root);
int i;
for (i=1; i<=h; i++)
printGivenLevel(root, i);
}
/* Print nodes at a given level */
template < typename T >
void BinaryTree < T >::printGivenLevel(TreeNode < T > * root, int level)
{
if (root == NULL)
return;
if (level == 1)
cout<<\" \"<<root->element;
else if (level > 1)
{
printGivenLevel(root->left, level-1);
printGivenLevel(root->right, level-1);
}
}
template < typename T >
int BinaryTree < T >::depth(TreeNode < T > * element)
{
if (element==NULL)
return 0;
else
{
int lDepth = depth(element->left);
int rDepth = depth(element->right);
// use the larger one
if (lDepth > rDepth)
return(lDepth+1);
else return(rDepth+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.BFS();
return 0;
}
===============================================================
akshay@akshay-Inspiron-3537:~/Chegg$ g++ bst1.cpp
akshay@akshay-Inspiron-3537:~/Chegg$ ./a.out
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
2 1 4 3 8 5 6
========================================
i have implemented first two functions
