Hello programmers! I am working on a custom tree class [with the code example being copied from Dietl's C++ How to Program, 9th edition].
It is in my fashion to copy all the code examples in the book when reading it (for muscle memory), but the authors created a custom template Tree class, creating the driver program first, and then a TreeNode class, which defines the Tree class template to be a friend.
I hope that you know about the concept of trees in programming.
Anyhow, this involves using pointers (not my strong suit). I copied all they did, and was planning to modify it, when I got a 8 errors in a function preOrderHelper (which is recursive) that is called by preOrderTraversal. As I trusted the authors of the book, I copied everything they did, but the code in the book that I copied from apperently has errors.
I checked everything, and I am at loss for what to do now.
Could someone help? Thanks! My code is below:
This is the driver program (no errors here), which created two Trees, one of type int, and the other of type double:
// main.cpp
// Creating and transversing a binary tree
#include <iostream>
#include <iomanip>
#include "Tree.h"
using namespace std;
int main()
{
Tree<int> intTree; //create Tree of int values
cout << "Enter 10 integer values:\n";
//insert 10 integers to intTree
for (int i=0; i < 10; i++)
{
int intValue=0;
cin >> intValue;
intTree.insertNode(intValue);
}
cout << "\nPreorder traversal\n";
intTree.preOrderTraversal();
cout << "\nInorder traversal\n";
intTree.inOrderTraversal();
cout << "\nPostorder traversal\n";
intTree.postOrderTraversal();
Tree<double> doubleTree; //create Tree of double values
cout << fixed << setprecision(1) << "\n\n\nEnter 10 double values:\n";
//insert 10 doubles to doubleTree
for (int j=0; j < 10; j++)
{
double doubleValue=0.0;
cin >> doubleValue;
doubleTree.insertNode(doubleValue);
}
cout << "\nPreorder traversal\n";
doubleTree.preOrderTraversal();
cout << "\nInorder traversal\n";
doubleTree.inOrderTraversal();
cout << "\nPostorder traversal\n";
doubleTree.postOrderTraversal();
cout << endl;
}
This is the header file for TreeNode_h (used by the class template Tree), and also has no errors:
// TreeNode class-template definition
#ifndef TreeNode_h
#define TreeNode_h
//forward declaration of class-template Tree
template<typename NODETYPE> class Tree;
//TreeNode class-template definition
template<typename NODETYPE>
class TreeNode
{
friend class Tree<NODETYPE>; //making class Tree a friend- Tree can access TreeNode's private members
public:
//constructor
TreeNode(const NODETYPE& d):
leftPtr(nullptr), //pointer to left subtree
data(d), //tree node data
rightPtr(nullptr) //pointer to right subtree
{}
//return copy of node's data
NODETYPE getData() const
{
return data;
}
private:
TreeNode<NODETYPE> *leftPtr; //pointer to left subtree
NODETYPE data; //data contained by an instance of TreeNode
TreeNode<NODETYPE> *rightPtr; //pointer to right subtree
};
#endif
And then, the class template Tree with the problematic function unction preOrderHelper (which is recursive) that is called by preOrderTraversal:
// Tree class-template definition
#ifndef Tree_h
#define Tree_h
#include <iostream>
#include "TreeNode.h"
//Tree class-template definition
template <typename NODETYPE> class Tree
{
public:
//constructor
Tree(): rootPtr(nullptr)
{}
//inset node in Tree
void insertNode(const NODETYPE& value)
{
insertNodeHelper(&rootPtr,value);
}
//begin preorder traversal of Tree
void preOrderTraversal() const
{
this->preOrderHelper(rootPtr);
}
//begin inorder traversal of Tree
void inOrderTraversal() const
{
this->inOrderHelper(rootPtr);
}
//begin postorder traversal of Tree
void postOrderTraversal() const
{
this->postOrderHelper(rootPtr);
}
private:
TreeNode<NODETYPE> *rootPtr;
//utilitiy function called by insertNode; recieves a pointer
//a pointer so that the function can modify pointer's value
void insertNodeHelper(TreeNode<NODETYPE> **ptr,const NODETYPE &value)
{
//subtree is empty; create new TreeNode containing value
if (*ptr == nullptr) //base case for recursion
*ptr = new TreeNode<NODETYPE>(value);
else //subtree is not empty
{
//data to insert is less than data in current node
if (value < (*ptr)->data)
insertNodeHelper(&((*ptr)->rightPtr), value);
else
{
//data to insert is greater han data in current node
if (value > (*ptr)->data)
insertNodeHelper(&((*ptr)->rightPtr), value);
else
//duplicate data value ignored
std::cout << value << " dup" << std::endl;
}
}
}
//utility function to perform preorder traversal of Tree
void preOrderHelper( Tree<NODETYPE> *ptr) const
{
if (ptr != nullptr) //base case for recursion
{
std::cout << (ptr->data) << ' ';//process node
preOrderHelper(ptr->leftPtr); //traverse left subtree
preOrderHelper(ptr->rightPtr); //raverse right subtree
}
}
//utility function to perform inorder traversal of Tree
void inOrderHelper(TreeNode<NODETYPE> *ptr) const
{
if (ptr != nullptr) //base case for recursion
{
inOrderHelper(ptr->leftPtr); //traverse left subtree
std::cout << (ptr->data) << ' ';//process node
inOrderHelper(ptr->rightPtr); //traverse right subtree
}
}
//utility function to perform postorder traversal of Tree
void postOrderHelper(TreeNode<NODETYPE> *ptr) const
{
if (ptr != nullptr)
{
postOrderHelper(ptr->leftPtr); //traverse left subtree
postOrderHelper(ptr->rightPtr);//traverse right subtree
std::cout << (ptr->data) << ' '; //process node
}
}
};
#endif
I apoligize for the largeness of my code, but this is the only way to solve the problem.
All of them are Semantic issues.
I am going to put the error messages where they are occurring:
//begin preorder traversal of Tree
void preOrderTraversal() const
{
this->preOrderHelper(rootPtr);
}
/* 2 ERROR messages for line 4 of above code sample:
1-Cannot initialize a parameter of type 'Tree<int> *' with an rvalue of type 'TreeNode<int> *const *'
2-Cannot initialize a parameter of type 'Tree<double> *' with an rvalue of type 'TreeNode<double> *const *'
*/
//utility function to perform preorder traversal of Tree
void preOrderHelper( Tree<NODETYPE> *ptr) const
{
if (ptr != nullptr) //base case for recursion
{
std::cout << (ptr->data) << ' ';//process node
preOrderHelper(ptr->leftPtr); //traverse left subtree
preOrderHelper(ptr->rightPtr); //raverse right subtree
}
}
/*
Error messages are:
1- No member named 'data' in Tree<int>
2- No member named 'leftPtr' in Tree<int>
3- No member named 'rightPtr' in Tree<int>
4- No member named 'data' in Tree<double>
5- No member named 'leftPtr' in Tree<double>
6- No member named 'rightPtr' in Tree<double>
*/
