好吧,我已经调试了几个小时了,但一无所获。我正在尝试测试一个直接使用递归的二叉树。
测试时,我在第三次调用 main 的 print_attributes 函数时出现堆栈溢出(如下所示)。对调用堆栈的快速检查表明它充满了对 binTree 的 binTree's height(Node < T >* node) 的数百次调用(也在下面注明)。当我“转到”来自调用堆栈的调用时,它会将我带到 size(Node < T >* node) 的 leftside = size(node->left) 调用(也在下面注明)。我不知道那应该表示什么,因为这两个函数都不互相调用。
这是编译器在发生堆栈溢出时所说的图像(我使用的是 VS2013): http://puu.sh/ca3ti/e00f653282.png
下面是编译器的图像,在中断并单击调用堆栈中的任何 height() 调用之后:http://puu.sh/ca2Qz/d35348ccce.png
考虑到它(似乎)在使用 bintree 的 height() 和/或 size() 函数之前将节点很好地插入树中,我不知道为什么相同的函数在这里开始出现问题。很抱歉无法更清楚地解释问题所在。我已经编码了几年,但我真的迷失了。我已尽力提供尽可能多的信息。非常感谢任何花时间帮助解决此问题的人。
节点类:
#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
节点树类:
#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
主要:
#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;
}
最佳答案
首先,在您的 binTree
类中,size()
和 height()
方法都有以下行:
if (root = 0)
显然这应该是 ==
。
实际的堆栈溢出问题似乎是由您的 insert
函数引起的。它通过引用获取第一个参数 node
。因此,当您使用 insert(root, t)
调用它时,node
最终作为对 root
的引用。当在 insert
中分配新节点时,root
被设置为指向新节点,这也会更改 node
引用。
如果您使用调试器在 insert
函数的顶部设置断点并单步执行,您可以看到值的变化。
这意味着 root
和 node
是同一件事,所以当你设置 node->left = n
或 node->right = n
节点最终指向自身。
要修复它,您需要做的就是更改 insert
的定义,以按值而不是引用传递 node
:
void insert(Node < T >* node, const T& t) // private version of insert ( )
关于C++ 二叉树堆栈溢出,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26330554/