0

次のコードは、私を本当に困惑させました。

クラス

class AVLTree {
   private:
struct AVLNode
{
    AVLNode *leftchild;
    AVLNode *rightchild;
    int data;
    int height;
};

AVLNode *root;

public:

AVLTree()
{
    root = NULL;
}

bool isEmpty() const { return root == NULL; }
void print();
void inorder(AVLNode *n, int l);
void insert(int d);
void rotateLeft(AVLNode* n);
void rotateRight(AVLNode* n);
void rotateLeftTwice(AVLNode* n);
void rotateRightTwice(AVLNode* n);
AVLTree::AVLNode* insert(int d, AVLNode* n);
int max( int a, int b);
int height( AVLNode* n); };

挿入機能。

  AVLTree::AVLNode* AVLTree::insert(int d,AVLNode *n){
    if (n == NULL)
    {
        AVLNode *n = new AVLNode;
        n->data = d;
        n->leftchild = NULL;
        n->rightchild = NULL;
        n->height = 0;
    } else if( d < n->data) {
        n->leftchild = insert(d,n->leftchild);

    } else if (d > n->data) {
        n->rightchild = insert(d,n->rightchild);
    }
    else {      
        n->height = max(height(n->leftchild), height(n->rightchild));
        return n;
         }
        -----> This section of the code gives be "EXC_BAD_ACCESS".
    n->height = max(height(n->leftchild), height(n->rightchild));
       return n;
}

これが高さ関数です。

int AVLTree::height(AVLNode* node)
{   cout << "HEIGHT"; 
    if(node == NULL)
    {
        return -1;
    }
    else {
        return node->height;
    }
}

誰でも理由を知っていますか？

=== 更新:

ローテーションをするとき

 void AVLTree::rotateLeft(AVLNode* n)
    {
            AVLNode *child = n->leftchild;
            n->leftchild = child->rightchild;
            child->rightchild = n;

            n->height = max(height(n->leftchild),height(n->rightchild))+1;
            child->height = max(height(child->leftchild),height(child->rightchild))+1;
            n = child;
}

必要に応じて値を交換していないようです。n = child はローカルでスワップしているように見えますが、残りのコードの変更は反映されていません。私に無限ループを与えます。

4

1 に答える 1

2

関数へのエントリで null の場合n、その行はそれを逆参照しようとし、エラーが発生します。新しいノードを割り当てるコードはn、関数の引数をシャドウする同じ名前の別の変数ではなく、それ自体に割り当てる必要があります。

if (n == NULL)ブロックの最初の行を

AVLNode *n = new AVLNode;

に

n = new AVLNode;

更新について: 回転関数でnは、ローカル (自動) 変数であり、それを変更しても関数の外部には影響しません。ポインターを参照渡しするか、新しいポインター値を返す必要があります ( のようにinsert())。

于 2011-03-05T21:39:30.923 に答える