编制了C程序菜单，实现了AVL树数据的插入、删除和打印。但删除后有些不对劲。
已输入的AVL树横向打印的结果是正确的，但是当删除它并再次打印它时，它看起来像是有问题。
这里我输入的是：：6，27，19，11，36，14，81，63，75这里输出横截：前序遍历：19 11 6 14 36 27 75 63 81中序遍历：6 11 14 19 27 36 63 75 81后序遍历：6 14 11 27 63 81 75 36 19
我相信这是正确的。
但删除后：14、75、36、19、11前序遍历：27 6 63 81中序遍历：6 27 63 81后序遍历：六八一六三二七
我认为这是不正确的，因为它应该是：前序遍历：63 6 27 81中序遍历：27 6 63 81后序遍历：27 6 81 63
下面是我的代码：

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

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

int height(struct Node* node){
    if (node == NULL)
        return 0;
    return node->height;
}

int max(int a, int b){
    return (a>b)? a : b;
}

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

struct Node* rightRotate(struct Node* y){
    struct Node* x = y->left;
    struct Node* T2 = x->right;

    x->right = y;
    y->left = T2;

    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    return x;
}

struct Node* leftRotate(struct Node* x){
    struct Node* y = x->right;
    struct Node* T2 = y->left;

    y->left = x;
    x->right = T2;

    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    return y;
}

int getBalance(struct Node* node){
    if (node == NULL)
        return 0;
    return height(node->left) - height(node->right);
}

struct Node* insert(struct Node* node, int data){
    if(node == NULL)
        return newNode(data);

    if(data < node->data)
        node->left = insert(node->left, data);
    else if(data > node->data)
        node->right = insert(node->right, data);
    else 
        return node;

    node->height = 1 + max(height(node->left), height(node->right));

    int balance = getBalance(node);

    if(balance > 1 && data < node->left->data)
        return rightRotate(node);

    if(balance < -1 && data > node->right->data)
        return leftRotate(node);

    if(balance > 1 && data > node->left->data) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    if(balance < -1 && data < node->right->data) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

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

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

    return current;
}

struct Node* deleteNode(struct Node* root, int data){
    if(root == NULL)
        return root;

    if(data < root->data)
        root->left = deleteNode(root->left, data);

    else if(data > root->data)
        root->right = deleteNode(root->right, data);

    else{
        if((root->left == NULL) || (root->right == NULL)) {
            struct Node* temp = root->left ? root->left : root->right;

            if(temp == NULL){
                temp = root;
                root = NULL;
            } else 
                *root = *temp; 

            free(temp);
        } else{

            struct Node* temp = minValueNode(root->right);

            root->data = temp->data;

            root->right = deleteNode(root->right, temp->data);
            
        }
    }

    if(root == NULL)
        return root;

    root->height = 1 + max(height(root->left), height(root->right));

    int balance = getBalance(root);

    if(balance > 1 && getBalance(root->left) >= 0)
        return rightRotate(root);

    if(balance > 1 && getBalance(root->left) < 0) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    if(balance < -1 && getBalance(root->right) >= 0) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    if(balance < -1 && getBalance(root->right) < 0)
        return leftRotate(root);

    return root;
}

struct Node* search(struct Node* root, int data) {
    if(root == NULL || root->data == data)
        return root;

    if(root->data < data)
        return search(root->right, data);

    return search(root->left, data);
}

void preorder(struct Node* root) {
    if(root != NULL) {
        printf("%d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

void inorder(struct Node* root) {
    if(root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

void postorder(struct Node* root) {
    if(root != NULL) {
        postorder(root->left);
        postorder(root->right);
        printf("%d ", root->data);
    }
}

int main(){
    struct Node* root = NULL;
    int choice, data;

    do{
        printf("\n1. Insertion");
        printf("\n2. Deletion");
        printf("\n3. Traversal");
        printf("\n4. Exit");
        printf("\nChoose: ");
        scanf("%d", &choice);

        switch(choice){
            case 1:
                printf("Enter the value to be inserted: ");
                scanf("%d", &data);
                root = insert(root, data);
                break;

            case 2:
                printf("Enter the value to be deleted: ");
                scanf("%d", &data);
                if (search(root, data) == NULL) {
                    printf("Data not found.\n");
                } else {
                    root = deleteNode(root, data);
                    printf("Data deleted successfully.\n");
                }
                break;

            case 3:
                printf("\nPreorder traversal: ");
                preorder(root);
                printf("\nInorder traversal: ");
                inorder(root);
                printf("\nPostorder traversal: ");
                postorder(root);
                printf("\n");
                break;

            case 4:
                printf("Thank You\n");
                break;

            default:
                printf("Invalid choice\n");
                break;
        }
    } while(choice != 4);

    return 0;
}