3

主要：

#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

私のコピー コンストラクターと operator= は、av1 のコピーとして av2 または av3 を生成しないため、正しく機能していません。122 行目の cout が t->element と r->element が同じであることを反映しているため、copyNodes() が適切に機能していることがわかります。テスト プログラムの 22 行目と 24 行目で出力が生成されないのはなぜですか?

これに関するヘルプは大歓迎です。

注: printTree() は、それが問題ではなく、大きな関数であることを確実に知っているため、省略されています。

その他の注意: コードを段階的に説明し、他のクラスのコピー コンストラクター/オペレーター = 関数をいくつか調べました。ステップごとにトレースすると動作しますが、実際にコンパイルすると動作しません。

4

1 に答える 1

3

2 番目の引数を参照にすることで、コードを修正できる場合がcopy_nodesあります。コードinsert内から呼び出す場合copy_nodes、ツリーのルート ノードへの参照ではなく、 のrパラメータへの参照を渡しますcopy_node。

しかし、それを行うためのもっと簡単な (そしてより効率的で、リバランスを必要としない) 方法があると思います。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 );
}

代入演算子についても同様です。

于 2012-11-10T16:35:26.387 に答える