c - AVL 的右旋转功能仍然给出旧值？

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 和 lll 的旧值，因为它们是在 main() 中定义的局部变量，并且在您执行此操作后它们不会获得新值从RightRotate1()返回。只有 main() 中的 root 指针会被 RightRotate1() 更改。如果您想使用 l、ll 和 lll，则需要重新分配它们以指向旋转树后的新位置。

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