Problem in C++ WILL GIVE A LOT OF POINTS FOR CORRECT AND COMPLETE ANSWER. MAKE S
ID: 3582742 • Letter: P
Question
Problem in C++
WILL GIVE A LOT OF POINTS FOR CORRECT AND COMPLETE ANSWER.
MAKE SURE YOU USE THE CODE PROVIDED BELOW AND postorder traversal IS IN FACT NON-RECURSIVE. I POSTED THIS EARLIER AND GOT SOMEONE THAT REPLIED WITH A RECURSIVE ALGORITHM.
YOU CAN NAME THE NON-RECURSIVE functions postorderTraversal1() and postOrder1() and just add them to the code provided belo.
ALSO DON'T FORGET ABOUT THE TEST PROGRAM.
DETAILS BELOW.
a. Write the definition of the function to implement the nonrecursive
postorder traversal algorithm.
b. Write a program to test the nonrecursive inorder, preorder, and postorder
traversal algorithms. (Note: First create a binary search tree.)
BINARY TREE HAS ALREADY BEEN CREATED AND THE CODE IS AS FOLLOWED
//Header File Binary Search Tree
#ifndef H_binaryTree
#define H_binaryTree
//*************************************************************
// Author: D.S. Malik
//
// class binaryTreeType
// This class specifies the basic operations to implement a
// binary tree.
//*************************************************************
#include <iostream>
using namespace std;
//Definition of the node
template <class elemType>
struct binaryTreeNode
{
elemType info;
binaryTreeNode<elemType> *llink;
binaryTreeNode<elemType> *rlink;
};
//Definition of the class
template <class elemType>
class binaryTreeType
{
public:
const binaryTreeType<elemType>& operator=
(const binaryTreeType<elemType>&);
//Overload the assignment operator.
bool isEmpty() const;
//Returns true if the binary tree is empty;
//otherwise, returns false.
void inorderTraversal() const;
//Function to do an inorder traversal of the binary tree.
void preorderTraversal() const;
//Function to do a preorder traversal of the binary tree.
void postorderTraversal() const;
//Function to do a postorder traversal of the binary tree.
int treeHeight() const;
//Returns the height of the binary tree.
int treeNodeCount() const;
//Returns the number of nodes in the binary tree.
int treeLeavesCount() const;
//Returns the number of leaves in the binary tree.
void destroyTree();
//Deallocates the memory space occupied by the binary tree.
//Postcondition: root = NULL;
int singleParent();
binaryTreeType(const binaryTreeType<elemType>& otherTree);
//copy constructor
binaryTreeType();
//default constructor
~binaryTreeType();
//destructor
protected:
binaryTreeNode<elemType> *root;
private:
void copyTree(binaryTreeNode<elemType>* &copiedTreeRoot,
binaryTreeNode<elemType>* otherTreeRoot);
//Makes a copy of the binary tree to which
//otherTreeRoot points. The pointer copiedTreeRoot
//points to the root of the copied binary tree.
void destroy(binaryTreeNode<elemType>* &p);
//Function to destroy the binary tree to which p points.
//Postcondition: p = NULL
void inorder(binaryTreeNode<elemType> *p) const;
//Function to do an inorder traversal of the binary
//tree to which p points.
void preorder(binaryTreeNode<elemType> *p) const;
//Function to do a preorder traversal of the binary
//tree to which p points.
void postorder(binaryTreeNode<elemType> *p) const;
//Function to do a postorder traversal of the binary
//tree to which p points.
int height(binaryTreeNode<elemType> *p) const;
//Function to return the height of the binary tree
//to which p points.
int max(int x, int y) const;
//Returns the larger of x and y.
int nodeCount(binaryTreeNode<elemType> *p) const;
//Function to return the number of nodes in the binary
//tree to which p points
int leavesCount(binaryTreeNode<elemType> *p) const;
//Function to return the number of leaves in the binary
//tree to which p points
int singleP(binaryTreeNode<elemType> *p);
};
template <class elemType>
int binaryTreeType<elemType>::singleParent()
{
return singleP(root);
}
template <class elemType>
int binaryTreeType<elemType>::singleP(binaryTreeNode<elemType> *p)
{
if (p == NULL)
return 0;
else if (p->llink == NULL && p->rlink != NULL)
return 1 + singleP(p->rlink);
else if (p->llink != NULL && p->rlink == NULL)
return 1 + singleP(p->llink);
else
{
return singleP(p->llink) + singleP(p->rlink);
}
}
template <class elemType>
binaryTreeType<elemType>::binaryTreeType()
{
root = NULL;
}
template <class elemType>
bool binaryTreeType<elemType>::isEmpty() const
{
return (root == NULL);
}
template <class elemType>
void binaryTreeType<elemType>::inorderTraversal() const
{
inorder(root);
}
template <class elemType>
void binaryTreeType<elemType>::preorderTraversal() const
{
preorder(root);
}
template <class elemType>
void binaryTreeType<elemType>::postorderTraversal() const
{
postorder(root);
}
template <class elemType>
int binaryTreeType<elemType>::treeHeight() const
{
return height(root);
}
template <class elemType>
int binaryTreeType<elemType>::treeNodeCount() const
{
return nodeCount(root);
}
template <class elemType>
int binaryTreeType<elemType>::treeLeavesCount() const
{
return leavesCount(root);
}
template <class elemType>
void binaryTreeType<elemType>::copyTree
(binaryTreeNode<elemType>* &copiedTreeRoot,
binaryTreeNode<elemType>* otherTreeRoot)
{
if (otherTreeRoot == NULL)
copiedTreeRoot = NULL;
else
{
copiedTreeRoot = new binaryTreeNode<elemType>;
copiedTreeRoot->info = otherTreeRoot->info;
copyTree(copiedTreeRoot->llink, otherTreeRoot->llink);
copyTree(copiedTreeRoot->rlink, otherTreeRoot->rlink);
}
} //end copyTree
template <class elemType>
void binaryTreeType<elemType>::inorder(binaryTreeNode<elemType> *p) const
{
if (p != NULL)
{
inorder(p->llink);
cout << p->info << " ";
inorder(p->rlink);
}
}
template <class elemType>
void binaryTreeType<elemType>::preorder(binaryTreeNode<elemType> *p) const
{
if (p != NULL)
{
cout<<p->info<<" ";
preorder(p->llink);
preorder(p->rlink);
}
}
template <class elemType>
void binaryTreeType<elemType>::postorder(binaryTreeNode<elemType> *p) const
{
if (p != NULL)
{
postorder(p->llink);
postorder(p->rlink);
cout << p->info << " ";
}
}
//Overload the assignment operator
template <class elemType>
const binaryTreeType<elemType>& binaryTreeType<elemType>::
operator=(const binaryTreeType<elemType>& otherTree)
{
if (this != &otherTree) //avoid self-copy
{
if (root != NULL) //if the binary tree is not empty,
//destroy the binary tree
destroy(root);
if (otherTree.root == NULL) //otherTree is empty
root = NULL;
else
copyTree(root, otherTree.root);
}//end else
return *this;
}
template <class elemType>
void binaryTreeType<elemType>::destroy(binaryTreeNode<elemType>* &p)
{
if (p != NULL)
{
destroy(p->llink);
destroy(p->rlink);
delete p;
p = NULL;
}
}
template <class elemType>
void binaryTreeType<elemType>::destroyTree()
{
destroy(root);
}
//copy constructor
template <class elemType>
binaryTreeType<elemType>::binaryTreeType
(const binaryTreeType<elemType>& otherTree)
{
if (otherTree.root == NULL) //otherTree is empty
root = NULL;
else
copyTree(root, otherTree.root);
}
template <class elemType>
binaryTreeType<elemType>::~binaryTreeType()
{
destroy(root);
}
template <class elemType>
int binaryTreeType<elemType>::height(binaryTreeNode<elemType> *p) const
{
if (p == NULL)
return 0;
else
return 1 + max(height(p->llink), height(p->rlink));
}
template <class elemType>
int binaryTreeType<elemType>::max(int x, int y) const
{
if (x >= y)
return x;
else
return y;
}
template <class elemType>
int binaryTreeType<elemType>::nodeCount(binaryTreeNode<elemType> *p) const
{
if (p==NULL)
return 0;
else
{
return 1 + nodeCount(p->llink) + nodeCount(p->rlink);
}
}
template <class elemType>
int binaryTreeType<elemType>::leavesCount(binaryTreeNode<elemType> *p) const
{
if (p == NULL)
return 0;
else
if (p->llink == NULL && p->rlink == NULL)
return 1;
else
return leavesCount(p->llink) + leavesCount(p->rlink);
}
#endif
//Header File Binary Search Tree
#ifndef H_binarySearchTree
#define H_binarySearchTree
#include <iostream>
#include <cassert>
#include "binaryTree.h"
//*************************************************************
// Author: D.S. Malik
//
// This class specifies the basic operations to implement a
// binary search tree.
//*************************************************************
using namespace std;
template <class elemType>
class bSearchTreeType: public binaryTreeType<elemType>
{
public:
bool search(const elemType& searchItem) const;
//Function to determine if searchItem is in the binary
//search tree.
//Postcondition: Returns true if searchItem is found in the
// binary search tree; otherwise, returns false.
void insert(const elemType& insertItem);
//Function to insert insertItem in the binary search tree.
//Postcondition: If no node in the binary search tree has the
// same info as insertItem, a node with the info insertItem
// is created and inserted in the binary search tree.
void deleteNode(const elemType& deleteItem);
//Function to delete deleteItem from the binary search tree
//Postcondition: If a node with the same info as deleteItem
// is found, it is deleted from the binary search tree.
private:
void deleteFromTree(binaryTreeNode<elemType>* &p);
//Function to delete the node to which p points is deleted
//from the binary search tree.
//Postcondition: The node to which p points is deleted from
// the binary search tree.
};
template <class elemType>
bool bSearchTreeType<elemType>::
search(const elemType& searchItem) const
{
binaryTreeNode<elemType> *current;
bool found = false;
if (root == NULL)
cerr << "Cannot search the empty tree." << endl;
else
{
current = root;
while (current != NULL && !found)
{
if (current->info == searchItem)
found = true;
else if (current->info > searchItem)
current = current->llink;
else
current = current->rlink;
}//end while
}//end else
return found;
}//end search
template <class elemType>
void bSearchTreeType<elemType>::insert(const elemType& insertItem)
{
binaryTreeNode<elemType> *current; //pointer to traverse the tree
binaryTreeNode<elemType> *trailCurrent= NULL; //pointer behind current
binaryTreeNode<elemType> *newNode; //pointer to create the node
newNode = new binaryTreeNode<elemType>;
assert(newNode != NULL);
newNode->info = insertItem;
newNode->llink = NULL;
newNode->rlink = NULL;
if (root == NULL)
root = newNode;
else
{
current = root;
while (current != NULL)
{
trailCurrent = current;
if (current->info == insertItem)
{
cerr << "The insert item is already in the list-";
cerr << "duplicates are not allowed."
<< insertItem << endl;
return;
}
else if (current->info > insertItem)
current = current->llink;
else
current = current->rlink;
}//end while
if (trailCurrent->info > insertItem)
trailCurrent->llink = newNode;
else
trailCurrent->rlink = newNode;
}
}//end insert
template <class elemType>
void bSearchTreeType<elemType>::deleteNode(const elemType& deleteItem)
{
binaryTreeNode<elemType> *current; //pointer to traverse the tree
binaryTreeNode<elemType> *trailCurrent; //pointer behind current
bool found = false;
if (root == NULL)
cout << "Cannot delete from the empty tree." << endl;
else
{
current = root;
trailCurrent = root;
while (current != NULL && !found)
{
if (current->info == deleteItem)
found = true;
else
{
trailCurrent = current;
if (current->info > deleteItem)
current = current->llink;
else
current = current->rlink;
}
}//end while
if (current == NULL)
cout << "The delete item is not in the tree." << endl;
else if (found)
{
if (current == root)
deleteFromTree(root);
else if (trailCurrent->info > deleteItem)
deleteFromTree(trailCurrent->llink);
else
deleteFromTree(trailCurrent->rlink);
}//end if
}
}//end deleteNode
template <class elemType>
void bSearchTreeType<elemType>::deleteFromTree
(binaryTreeNode<elemType>* &p)
{
binaryTreeNode<elemType> *current; //pointer to traverse the tree
binaryTreeNode<elemType> *trailCurrent; //pointer behind current
binaryTreeNode<elemType> *temp; //pointer to delete the node
if (p == NULL)
cerr << "Error: The node to be deleted is NULL." << endl;
else if(p->llink == NULL && p->rlink == NULL)
{
temp = p;
p = NULL;
delete temp;
}
else if(p->llink == NULL)
{
temp = p;
p = temp->rlink;
delete temp;
}
else if(p->rlink == NULL)
{
temp = p;
p = temp->llink;
delete temp;
}
else
{
current = p->llink;
trailCurrent = NULL;
while (current->rlink != NULL)
{
trailCurrent = current;
current = current->rlink;
}//end while
p->info = current->info;
if (trailCurrent == NULL) //current did not move;
//current == p->llink; adjust p
p->llink = current->llink;
else
trailCurrent->rlink = current->llink;
delete current;
}//end else
}//end deleteFromTree
#endif
Explanation / Answer
post-order traversal without recursion:
public string PostOrderIterative()
{
List<int> nodes = new List<int>();
if (null != this._root)
{
BinaryTreeNode lastPostOrderTraversalNode = null;
BinaryTreeNode iterativeNode = null;
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
stack.Push(this._root);
while(stack.Count > 0)
{
iterativeNode = stack.Pop();
if ((iterativeNode.Left == null)&& (iterativeNode.Right == null))
{
nodes.Add(iterativeNode.Element);
lastPostOrderTraversalNode = iterativeNode;
// we have to make sure that the stack is not empty as we need to peek at the top, a tree with just root node doesn't have to enter loop and also node Peek() will throw invalidoperationexception, if it is performed if the stack is empty. so, it handles both of them.
while(stack.Count > 0)
{
var stackTop = stack.Peek();
bool removeTop = false;
if ((stackTop.Right != null) &&(stackTop.Right == lastPostOrderTraversalNode))
//i.e. last post order traversal node is nothing but right node of stacktop. so, all the elements in the right subtree have been visted.So, we can pop the top element
{
removeTop = true;
}
else if((stackTop.Right == null)&& (stackTop.Left != null) && (stackTop.Left == lastPostOrderTraversalNode))
{ //right subtree is null
//last traversal node is nothing but the root of left sub tree node
removeTop = true;
}
else
{
break;
}
if(removeTop)
{
var top = stack.Pop();
Debug.Assert(stackTop == top);
lastPostOrderTraversalNode = top;
nodes.Add(top.Element);
}
}
}
else
{
stack.Push(iterativeNode);
if(iterativeNode.Right != null)
{
stack.Push(iterativeNode.Right);
}
if(iterativeNode.Left != null)
{
stack.Push(iterativeNode.Left);
}
}
}
}
return this.ListToString(nodes);
}
The definitions:
class BinaryTreeNode
{
public int Element;
public BinaryTreeNode Left;
public BinaryTreeNode Right;
public bool visted;
}
string ListToString(List<int> list)
{
string s = string.Join(", ", list);
return s;
}
Pre-order,in-order,post-order traversal of BST:
void inorder_non_recursive(NODE<T>* nodePtr);
void preorder_non_recursive(NODE<T>* nodePtr);
void postorder_non_recursive(NODE<T>* nodePtr);
void postorder_non_recursive_1(NODE<T>* nodePtr)
template<typename T> void BST<T>::inorder_non_recursive(NODE<T>* nodePtr)
{
cout << endl; stack<NODE<T>*> s;
while (!s.empty() || nodePtr)
{
/*If nodePtr is NULL, we need to pop from top of the stack and print it's value. Then traverse the right sub-tree*/
if (!nodePtr)
{
nodePtr = s.top();
cout << nodePtr->data << " ";
nodePtr = nodePtr->right;
s.pop();
}
/*Keep traversing left unless nodePtr is NULL*/
if (nodePtr)
{
s.push(nodePtr);
nodePtr = nodePtr->left;
}
}
cout << endl; return;
}
/*Non recursive preorder tree traversal*/
template<typename T> void BST<T>::preorder_non_recursive(NODE<T>* nodePtr)
{
cout << endl;
stack<NODE<T>*> s;
if (!nodePtr)
return;
/*we have to Push root*/
s.push(nodePtr);
while (!s.empty())
{
/*we have to Pop the top element*/
NODE<T>* tmpPtr = s.top();
cout << tmpPtr->data << " ";
s.pop();
/*Go right before going left as we are using a stack.*/
if (tmpPtr->right)
s.push(tmpPtr->right);
if (tmpPtr->left)
s.push(tmpPtr->left);
}
cout << endl;
return;
}
template<typename T> void BST<T>::postorder_non_recursive(NODE<T>* nodePtr)
{
cout << endl;
if (!nodePtr)
return;
stack<NODE<T>*> s1;
stack<NODE<T>*> s2;
/*Push root into stack s1*/
s1.push(nodePtr);
while (!s1.empty())
{
/*Pop fropm sack s1 and push it to stack s2*/
NODE<T>* tmpPtr = s1.top();
s2.push(tmpPtr);
s1.pop();
/*Now push left child before right. Because when we push it back to stack s2, the order will be correct.*/
if (tmpPtr->left)
s1.push(tmpPtr->left);
if (tmpPtr->right)
s1.push(tmpPtr->right);
}
/*Now s2 has got all the nodes in postorder. We will just pop it one by one and print.*/
while (!s2.empty())
{
NODE<T>* tmpPtr = s2.top();
s2.pop(); cout << tmpPtr->data << " ";
}
cout << endl; return;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.