AVL樹奇怪的行爲

下面的代碼讓我非常困惑。AVL樹奇怪的行爲

類

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 =孩子似乎在本地交換，但它並沒有反映出其他代碼的變化。給我一個無限循環。

來源

2011-03-05 Everton

什麼是你的_specific_問題？ – GWW 2011-03-05 20:50:15

你是否已經通過使用調試器來查看發生了什麼？ – 2011-03-05 20:53:26

「下面的代碼讓我感到非常困惑，[......]任何人都知道爲什麼？」嗯......我會說：「因爲你不懂代碼。」現在，也許你可以更具體地問我們你不明白的東西？ – 2011-03-05 20:53:37

如果n在進入該函數時爲空，那麼該行將試圖解引用它，並給出錯誤。您分配新節點的代碼應該將其分配給n本身，而不是具有相同名稱的單獨變量，這會影響函數參數。

更改if (n == NULL)塊的第一線，從

AVLNode *n = new AVLNode;

到

n = new AVLNode;

關於更新：在你的旋轉功能，n是本地（自動）變量，並改變韓元不影響功能以外的任何東西。您需要通過引用來傳遞指針，或者返回新的指針值（就像在insert()中那樣）。

來源

2011-03-05 21:39:30

這確實有幫助。但還有一些我不確定的事情。 – Everton 2011-03-05 22:29:25

AVL樹奇怪的行爲

回答

相關問題