c - 查看 AVL 树未给出正确的输出

Question

我正在开展一个学校项目，该项目涉及实现一个具有插入、删除和查看功能的 AVL 树。但是我的程序在使用前序遍历查看 avl 树时没有给出正确的输出。

avl树的变量:

 typedef struct Node{
 int data;
 int height;
 struct Node *right;
 struct Node *left;
 }Node;

这是我的插入函数和 newnode 函数调用:

Node *newNode(int data){
Node *node = (Node*)malloc(sizeof(Node));
node->data = data;
node->left = NULL;
node->right = NULL;
node->height = 1;
return(node);
}

Node *insertNode(Node *node, int data){
if(node == NULL)
    return(newNode(data));
if(data < node->data)
    node->left = insertNode(node->left, data);
if(data > node->data)
    node->right = insertNode(node->right, data);
if(data == node->data){
    printf("No duplicate allowed.");
    return node;
}

node->height = getHeight(node);
return(balancing(node, data));
}

使用 minvaluenode 函数调用删除函数:

Node * minValueNode(Node* node){
Node* current = node;

while (current->left != NULL)
    current = current->left;

return current;
}

Node *deleteNode(Node *root, int data){
 if(root == NULL){
    printf("Value not found.");
    return root;
}
else if ( data < root->data )
    root->left = deleteNode(root->left, data);
else if( data > root->data )
    root->right = deleteNode(root->right, data);
else if(data == root->data){
    if( (root->left == NULL) || (root->right == NULL) ){
        Node *temp = root->left ? root->left : root->right;
        if (temp == NULL){
            temp = root;
            root = NULL;
        }
        else
            *root = *temp;

        free(temp);
    }
    else{
        Node* temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right,temp->data);
    }
}
if(root == NULL)
    return root;
root->height = getHeight(root);
return(balancing(root, data));
}

具有旋转、getbalancefactor、max 和 getheight 函数调用的平衡函数:

int max(int number1, int number2){
return (number1 > number2) ? number1 : number2;
}

int getHeight(Node* n) {
          return max(height(n->left), height(n->right)) + 1;
   }

int getBalanceFactor(Node *currentNode){
if(currentNode == NULL)
    return 0;
return height(currentNode->left) - height(currentNode->right);
}

Node *rightRotate(Node *currentNode){
Node *temp = currentNode->left;
currentNode->left = temp->right;
temp->right = currentNode;
temp->height =  getHeight(temp);
currentNode->height = getHeight(currentNode);
return temp;
}

Node *leftRotate(Node *currentNode){
Node *temp = currentNode->right;
currentNode->right = temp->left;
temp->left = currentNode;
temp->height =  getHeight(temp);
currentNode->height = getHeight(currentNode);
return temp;
}



Node *balancing(Node *node, int data){
    if(getBalanceFactor(node) >= 2 && data < node->left->data)

    return rightRotate(node);
if(getBalanceFactor(node) <= -2 && data > node->right->data)

    return leftRotate(node);
if(getBalanceFactor(node) >= 2 && data > node->left->data){
    node->left = leftRotate(node->left);
    return(rightRotate(node));
}
if(getBalanceFactor(node) <= -2 && data < node->right->data){
    node->right = rightRotate(node->right);
    return(leftRotate(node));
}
return node;
}

我的查看功能:

//print AVL Tree in preorder traversal
void printAVLTree(Node *root){
 if(root != NULL)
{
    printf("%d ", root->data);
    printAVLTree(root->left);
    printAVLTree(root->right);
}
}

我用随机插入输入进行了测试:

9 5 10 6 0 11 -1 1 2

调用 View 函数时的输出为:

5 1 0 -1 2 9 6 10 11

正确的输出应该是:

9 1 0 -1 5 2 6 10 11

Answer 1

您的错误是您以错误的顺序更新高度值(从上到下):

temp->height =  getHeight(temp);
currentNode->height = getHeight(currentNode);

旋转后，下层节点是currentNode，所以必须先更新它。
否则，如果您在更新 currentNode 之前更新 temp，则 temp 将使用 currentNode 高度的先前值，并且将具有高度错误