Alright, I've been debugging this for a few hours now and am getting nowhere. I'm trying to test a straightforward recursion-using binary tree.
When tested, I get a stack overflow at the third call in main's print_attributes function (noted below). A quick inspection of the callstack shows that it's full of hundreds of calls to binTree's binTree's height(Node < T >* node) (also noted below). When I "go-to" the call from the Call Stack, it takes me to size(Node < T >* node)'s call of leftside = size(node->left) (also noted below). I don't know what that's supposed to indicate, because neither of these functions call each other.
Here's an image of what the compiler says right as the stack overflow occurs (I'm using VS2013): http://puu.sh/ca3ti/e00f653282.png
Then here's an image of the compiler, after breaking, and clicking any of the height() calls in the call stack: http://puu.sh/ca2Qz/d35348ccce.png
Considering that it (appears to be) inserting nodes into the tree fine just before while using bintree's height()and/or size() function, I have no idea why the same function begins having issues here. I'm sorry for not being able to be able to more clearly explain what the issue is. I've been coding for a few years but I'm really lost with this. I've tried to provide as much information as I possibly could. Thank you so much to anyone who takes the time to help with this.
Node Class:
#include "340.h"
#ifndef H_NODE
#define H_NODE
// definition for class of nodes in bin tree
template < class T > class binTree; // forward declaration
template < class T >
class Node {
friend class binTree < T >; // binTree is friend
public:
// default constructor
Node ( const T& x = T ( ), Node < T >* l = 0, Node < T >* r = 0 ) :
data ( x ), left ( l ), right ( r ) { }
private:
T data; // data component
Node < T > *left, *right; // left and right links
};
#endif
NodeTree Class:
#include "Node.h"
#ifndef H_TREE
#define H_TREE
template < class T > class binTree {
public:
binTree(Node < T >* emptyroot = nullptr) : // default constructor
root(emptyroot) { }
bool empty() const // checks if tree empty
{
if (root == 0)
return true;
else
return false;
}
unsigned size() const // returns no of nodes
{
if (root == 0)
return 0;
else
return size(root);
}
unsigned height() const // returns height of tree
{
if (root == 0)
return 0;
else
return height(root);
}
virtual void insert(const T& t) // inserts a node in shortest subtree
{
if (empty())
{
Node< T >* n = new Node< T >;
n->data = t;
root = n;
}
else
insert(root, t);
}
protected:
Node < T >* root; // root of tree
private:
unsigned size(Node < T >* node) const // private version of size ( )
{
unsigned leftside;
unsigned rightside;
if (node->left == 0)
leftside = 0;
else
leftside = size(node->left); //******issue(?) here******
if (node->right == 0)
rightside = 0;
else
rightside = size(node->right);
return(leftside + rightside + 1);
}
unsigned height(Node < T >* node) const // private version of height ( )
//*****issue(?) here************
{
unsigned leftside;
unsigned rightside;
if (node->left == 0)
leftside = 0;
else
leftside = height(node->left);
if (node->right == 0)
rightside = 0;
else
rightside = height(node->right);
return 1 + max(leftside, rightside);
}
void insert(Node < T >* node, const T& t) // private version of insert ( )
{
if (node->left == 0)
{
Node< T >* n = new Node< T >;
n->data = t;
root = n;
node->left = n;
return;
}
else if (node->right == 0)
{
Node< T >* n = new Node< T >;
n->data = t;
root = n;
node->right = n;
return;
}
unsigned lefth = height(node->left);
unsigned righth = height(node->right);
if (lefth <= righth)
{
insert(node->left, t);
}
else
{
insert(node->right, t);
}
}
};
#endif
Main:
#include "binTree.h"
// vectors used in testing
const vector < int > A { 1, -2, 3, -4, 5, -6, 7, -8, 9, -10, 11, -12,
13, -14, 15 };
// prints out val passed as argument
template < class T > void print ( T& x ) { cout << x << ' '; }
// increments val passed as argument
template < class T > void increment ( T& x ) { x++; }
// decrements val passed as argument
template < class T > void decrement ( T& x ) { x--; }
// prints out attributes, such as size and height of bin tree,
// and prints out data val in each node in inorder, preorder,
// and postorder
template < class T >
void print_attributes ( binTree < T >& tree, const string& name )
{
cout << name; // print name of tree
// check if tree is empty
cout << ": tree is " << ( tree.empty ( ) ? "" : "not " ) << "empty\n";
// print size and height of tree
cout << "\tno of nodes = " << setw ( 2 ) << tree.size ( )
<< "\n\theight of tree = " << setw ( 2 ) << tree.height ( )
<< endl << endl; //*******issue here************
system("pause");
return 0;
}