C 语言在线编译器

main.c

ShareResetEraseRun

StdinOptional input fed to the program on stdin - one line per line.2 linesAlice 30

Output

Click Run to see the output here.

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

typedef struct Node {
    int value, height;
    struct Node* left;
    struct Node* right;
} Node;

int height(const Node* n) { return n ? n->height : 0; }
int balanceFactor(const Node* n) { return height(n->left) - height(n->right); }
int maxInt(int a, int b) { return a > b ? a : b; }

Node* newNode(int value) {
    Node* n = calloc(1, sizeof(Node));
    n->value = value;
    n->height = 1;
    return n;
}

void updateHeight(Node* n) {
    n->height = 1 + maxInt(height(n->left), height(n->right));
}

Node* rotateRight(Node* y) {
    Node* x = y->left;
    y->left = x->right;
    x->right = y;
    updateHeight(y);
    updateHeight(x);
    return x;
}

Node* rotateLeft(Node* x) {
    Node* y = x->right;
    x->right = y->left;
    y->left = x;
    updateHeight(x);
    updateHeight(y);
    return y;
}

Node* insert(Node* node, int value) {
    if (node == NULL) return newNode(value);
    if (value < node->value) node->left = insert(node->left, value);
    else node->right = insert(node->right, value);
    updateHeight(node);
    int balance = balanceFactor(node);
    // Four rebalancing cases: LL, RR, LR, RL
    if (balance > 1 && value < node->left->value) return rotateRight(node);
    if (balance < -1 && value > node->right->value) return rotateLeft(node);
    if (balance > 1) {
        node->left = rotateLeft(node->left);
        return rotateRight(node);
    }
    if (balance < -1) {
        node->right = rotateRight(node->right);
        return rotateLeft(node);
    }
    return node;
}

void inorder(const Node* n) {
    if (n == NULL) return;
    inorder(n->left);
    printf("%d(h%d) ", n->value, n->height);
    inorder(n->right);
}

int main(void) {
    int values[] = {10, 20, 30, 40, 50, 25};
    Node* root = NULL;
    for (int i = 0; i < 6; i++) root = insert(root, values[i]);
    printf("Root after rebalancing: %d\n", root->value);
    printf("In-order: ");
    inorder(root);
    printf("\n");
    return 0;
}