pointers - C++ Binary Tree -

pointers - C++ Binary Tree -

alright, i've been debugging few hours , getting nowhere. i'm trying test straightforward recursion-using binary tree.

when tested, stack overflow @ 3rd phone call in main's print_attributes function (noted below). quick inspection of callstack shows it's total of hundreds of calls bintree's bintree's height(node < t >* node) (also noted below). when "go-to" phone call call stack, takes me size(node < t >* node)'s phone call of leftside = size(node->left) (also noted below). don't know that's supposed indicate, because neither of these functions phone call each other.

here's image of compiler says right stack overflow occurs (i'm using vs2013): http://puu.sh/ca3ti/e00f653282.png

then here's image of compiler, after breaking, , clicking of height() calls in phone call stack: http://puu.sh/ca2qz/d35348ccce.png

considering (appears be) inserting nodes tree fine before while using bintree's height()and/or size() function, have no thought why same function begins having issues here. i'm sorry not beingness able able more explain issue is. i've been coding few years i'm lost this. i've tried provide much info perchance could. give thanks much takes time help this.

node class:

#include "340.h" #ifndef h_node #define h_node // definition class of nodes in bin tree template < class t > class bintree; // forwards declaration template < class t > class node { friend class bintree < t >; // bintree friend public: // default constructor node ( const t& x = t ( ), node < t >* l = 0, node < t >* r = 0 ) : info ( x ), left ( l ), right ( r ) { } private: t data; // info component node < t > *left, *right; // left , 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) homecoming true; else homecoming false; } unsigned size() const // returns no of nodes { if (root == 0) homecoming 0; else homecoming size(root); } unsigned height() const // returns height of tree { if (root == 0) homecoming 0; else homecoming height(root); } virtual void insert(const t& t) // inserts 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); homecoming 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 > { 1, -2, 3, -4, 5, -6, 7, -8, 9, -10, 11, -12, 13, -14, 15 }; // prints out val passed argument template < class t > void print ( t& x ) { cout << x << ' '; } // increments val passed argument template < class t > void increment ( t& x ) { x++; } // decrements val passed argument template < class t > void decrement ( t& x ) { x--; } // prints out attributes, such size , height of bin tree, // , prints out info val in each node in inorder, preorder, // , postorder template < class t > void print_attributes ( bintree < t >& tree, const string& name ) { cout << name; // print name of tree // check if tree empty cout << ": tree " << ( tree.empty ( ) ? "" : "not " ) << "empty\n"; // print size , 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"); homecoming 0; }

firstly, in class bintree, both size() , height() methods have next line:

if (root = 0)

obviously should ==.

the actual stack overflow problem though seems caused insert function. takes first parameter, node reference. when phone call insert(root, t), node ends reference root. when new node allocated in insert, root set point new node, , changes node reference well.

if utilize debugger set breakpoint @ top of insert function , step through can watch values change.

what means root , node same thing, when set node->left = n or node->right = n node ends pointing @ itself.

all should have prepare alter definition of insert pass node value rather reference:

void insert(node < t >* node, const t& t) // private version of insert ( )

c++ pointers recursion binary-tree stack-overflow