AVL的Right Rotate函數仍然給舊的值？

Question

我正在爲AVL樹寫正確的旋轉。目前我忽略AVL樹的高度部分。我稍後會處理這個問題。但只是在5上應用右旋轉會給出錯誤的值。即使在執行右旋轉之後，l->data,ll->data,lll->data仍然會給出舊值（分別爲5,3,2）。我用AVL樹是：

        9(Root) 

       5(Left Child)       13(Right Child) 

     3      7     11      17 
    2 
1 

C代碼：

#include <stdio.h> 
#include <stdlib.h> 
#include <malloc.h> 


struct AVLTree 
{ 
    int data; 
    struct AVLTree *left; 
    struct AVLTree *right; 
}; 




struct AVL *RightRotate1(struct AVLTree *rootop,struct AVLTree *root) 
{ 
    if(root == NULL) 
    { 
     return NULL; 
    } 
    if(rootop->data > root->data) 
    { 
     root->right = RightRotate1(rootop,root->right); 
    } 
    else if(rootop->data < root->data) 
    { 
     root->left = RightRotate1(rootop,root->left); 
    } 
    else 
    { 
     struct AVLTree *A = rootop->left; 
     rootop->left = A->right; 
     A->right = rootop; 

     return A; 
    } 
    return root; 

} 




int main() 
{ 
    struct AVLTree * root = (struct AVLTree *)malloc(sizeof(struct AVLTree)); 
    root-> data = 9; 
    struct AVLTree * l = (struct AVLTree *)malloc(sizeof(struct AVLTree)); 
    l -> data = 5; 
    struct AVLTree * ll = (struct AVLTree *)malloc(sizeof(struct AVLTree)); 
    ll -> data = 3; 
    ll -> left = ll -> right = NULL; 
    struct AVLTree * lll = (struct AVLTree *)malloc(sizeof(struct AVLTree)); 
    lll -> data = 2; 
    lll -> left = lll -> right = NULL; 
    ll->left = lll; 
    struct AVLTree * llll = (struct AVLTree *)malloc(sizeof(struct AVLTree)); 
    llll -> data = 1; 
    llll -> left = llll -> right = NULL; 
    lll->left = llll; 
    struct AVLTree * lr = (struct AVLTree *)malloc(sizeof(struct AVLTree)); 
    lr -> data = 7; 
    lr -> left = lr -> right = NULL; 
    l -> left = ll; 
    l -> right = lr; 
    struct AVLTree * r = (struct AVLTree *)malloc(sizeof(struct AVLTree)); 
    r -> data = 13; 
    struct AVLTree * rl = (struct AVLTree *)malloc(sizeof(struct AVLTree)); 
    rl -> data = 11; 
    rl -> left = rl -> right = NULL; 
    struct AVLTree * rr = (struct AVLTree *)malloc(sizeof(struct AVLTree)); 
    rr -> data = 17; 
    rr -> left = rr -> right = NULL; 
    r -> left = rl; 
    r -> right = rr; 
    root -> left = l; 
    root -> right = r; 



    root = RightRotate1(l,root); 

    printf("Root is %d\n",root->data); 
    printf("Root Left is %d\n",root->left->data); 
    printf("Root Left Left is %d\n",root->left->left->data); 
    printf("Root Left Right is %d\n",root->left->right->data); 

    printf("Left is %d\n",l->data); 
    printf("Left left is %d\n",ll->data); 
    printf("Left right is %d\n",lll->data); 


    return 0; 
} 

Answer 1

你仍然得到舊值l, ll, and lll因爲它們是局部變量main()定義和他們之後你沒有得到新的價值從RightRotate1()返回。 main()中只有root指針被RightRotate1()更改。如果您想使用l, ll, and lll，則需要重新指定它們，以便旋轉該樹後指向新的位置。

root = RightRotate1(l,root); 
l = root->left; 
ll = root->left->left; 
lll = root->left->left->left;