编辑代码

#include <stdio.h>
#include "windows.h"

// 平衡二叉树（AVL树），查找（搜索）二叉树的升级
typedef int E;

// 平衡二叉树 （AVL树）
struct TreeNode {
    E element;
    struct TreeNode *left;
    struct TreeNode *right;
    int height;         //纪律节点高度，用来计算平衡因子       //平衡因子= 左节点height-右节点height 
    // 平衡节点大于1或小于-1 则需要采取旋转策略
};

typedef struct TreeNode *Node;

// 创建节点
Node createNode(E element) {
    Node node = malloc(sizeof(struct TreeNode));
    if (node == NULL) return NULL;
    node->left = node->right = NULL;
    node->element = element;
    node->height = 1;   // 第一个创造的根节点 或 叶子节点默认高度为1 ，后面高度会在插入时改变
    return node;
}

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

// 得到节点高度
int getHeight(Node root) {
    if (root == NULL) return 0;
    return root->height;
}

// 左旋 适用于RR型
Node leftRotation(Node root) {  //传入原本根节点，返回新的根节点
    Node newRoot = root->right;
    root->right = newRoot->left;
    newRoot->left = root;

    root->height = Max(getHeight(root->left), getHeight(root->right))+1;
    newRoot->height = Max(getHeight(newRoot->left), getHeight(newRoot->right))+1;

    return newRoot;
}

// 右旋 适用于LL型
Node rightRotation(Node root) {  //传入原本根节点，返回新的根节点
    Node newRoot = root->left;
    root->left = newRoot->right;
    newRoot->right = root;

    root->height = Max(getHeight(root->left), getHeight(root->right))+1;
    newRoot->height = Max(getHeight(newRoot->left), getHeight(newRoot->right))+1;

    return newRoot;
}

// 左右旋 适用于LR型
Node leftRightRotation(Node root) {  //传入原本根节点，返回新的根节点
    root->left = leftRotation(root->left);
    return rightRotation(root);
}

// 右左旋 适用于RL型
Node rightLeftRotation(Node root) {  //传入原本根节点，返回新的根节点
    root->right = rightRotation(root->left);
    return leftRotation(root);
}


// 遍历方法
void preOrder(Node root) {
    if (root == NULL) return;
    printf("%d ", root->element);
    preOrder(root->left);
    preOrder(root->right);
}

// 递归实现 插入操作
Node insert(Node root, E element) {
    if (root == NULL)
        root = createNode(element);
    else if (root->element > element) {
        root->left = insert(root->left, element);
// 旋转策略，因为插入后从下往上执行调整 so 放置在插入中
        if (getHeight(root->left) - getHeight(root->right) > 1) {
            if (root->left->element > element)
                root = rightRotation(root);
            else
                root = leftRightRotation(root);
        }

    } else if (root->element < element) {
        root->right = insert(root->right, element);
// 旋转策略
        if (getHeight(root->left) - getHeight(root->right) < -1) {
            if (root->right->element < element)
                root = leftRotation(root);
            else
                root = rightLeftRotation(root);
        }
    }
// 更新节点高度
    root->height = Max(getHeight(root->left), getHeight(root->right))+1;
    return root;
}

int main() {
    Node node = NULL;
    while (1) {
        E e;
        scanf("%d", &e);
        node = insert(node, e);
        printf(" ");
        preOrder(node);
        printf(" \n");
    }
}