main:
#include <iostream>
#include <cstdlib>
#include "avl_tree.h"
using namespace std;
int main()
{
AVLTree<int> av1;
int testarray [10] = { 16, 2, 77, 40, 54 , 1 , 100, 39, 73, 35 };
AVLTree<int> av3;
for( unsigned int i = 0; i < 10; i++ )
{
av1.insert( testarray[i] );
}
AVLTree<int> av2 = av1; //test copy constructor
av3 = av1; //test operator=
av2.printTree();
av1.printTree();
av3.printTree();
exit( 0 );
}
标题:
#ifndef AVL
#define AVL
#include <iostream>
using namespace std;
/**
* An AVL tree class adapted from Weiss.
* Does NOT allow duplicate elements.
*/
template <typename Comparable>
class AVLTree
{
public:
AVLTree( ) : root ( )
{
//nothing goes in the main constructor
}
AVLTree( const AVLTree & rhs ) : root ()
{
copyNodes( rhs.root , root );
}
~AVLTree( )
{
makeEmpty( root );
delete root;
}
const AVLTree & operator=( const AVLTree & rhs )
{
makeEmpty( root );
copyNodes( rhs.root , root );
}
void printTree( ) const
{
printTree( root, 0 );
}
void makeEmpty( )
{
makeEmpty( root );
}
void insert( const Comparable & x )
{
insert( x , root );
}
// void remove( const Comparable & x );
private:
struct AVLNode
{
Comparable element;
AVLNode *left;
AVLNode *right;
int height;
AVLNode( const Comparable & element,
AVLNode *left,
AVLNode *right,
int height = 0 )
: element( element ), left( left ), right( right ), height( height ) { }
}; // end of AVLNode
AVLNode * root;
void insert( const Comparable & x, AVLNode * & t )
{
if( t == NULL )
{
//cout << "tnull" <<endl;
t = new AVLNode( x, NULL, NULL );
}
else if( x < t->element )
{
//cout << "c1" <<endl;
insert( x, t->left );
if( height( t->left ) - height( t->right ) == 2 )
if( x < t->left->element )
rotateWithLeftChild( t );
else
doubleWithLeftChild( t );
}
else if( t->element < x )
{
// cout << "c2 " << t->element << " " << x <<endl;
insert( x, t->right );
if( height( t->right ) - height( t->left ) == 2 )
if( t->right->element < x )
rotateWithRightChild( t );
else
doubleWithRightChild( t );
}
//cout << "end" << endl;
// else duplicate; do nothing
t->height = max( height( t->left ), height( t->right ) ) + 1;
}
void makeEmpty( AVLNode * & t )
{
if ( t != NULL )
{
makeEmpty ( t -> left ) ;
makeEmpty ( t -> right ) ;
}
delete t;
t = NULL;
}
void copyNodes( AVLNode * t , AVLNode * r )
{
if ( t != NULL )
{
copyNodes( t->left , r );
copyNodes( t->right, r );
insert(t->element, r );
cout << t->element << r->element << endl; //these always print as the same
}
}
#endif
我担心我的复制构造函数和操作员=无法正常工作,因为它们不会导致AV2或AV3作为AV1的副本。我知道cyretnodes()的工作正常,因为第122行上的cout反映了t->元素和r->元素相同。为什么测试程序的第22行和24行不会产生输出?
对此的任何帮助将不胜感激。
注意:省略了printtree(),因为我确定这不是问题,而且是一个很大的功能。
其他注意:我已经逐步浏览了代码,并检查了其他几个类的其他复制构造函数/操作员=功能。当我逐步跟踪时,我会导致它起作用,但是当我实际编译它时,它不会。
您可以通过将第二个参数作为copy_nodes
作为参考来修复代码。在您的代码中,当您从copy_nodes
中调用insert
时,您不是传递对树的根节点的引用,而是传递对copy_node
的r
参数的引用。
但我认为这样做的方法更容易(更有效,无需重新平衡)。重写copy_nodes
作为返回复制节点的静态方法。
static AVLNode * copyNodes( AVLNode * t)
{
if ( t != NULL )
{
AVLNode* left = copyNodes( t->left );
AVLNode* right = copyNodes( t->right );
return new AVLNode(t->element, left, right, t->height);
}
else
{
return NULL;
}
}
然后,您可以在复制构造函数中使用此方法
AVLTree( const AVLTree & rhs )
{
root = copyNodes( rhs.root );
}
对于分配运营商类似。