#include<stdio.h>
#include<stdlib.h>
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
}Node;
typedef struct  {
    Node* root;
}Tree;
void addnode(Tree* tree, int data) {//添加
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    if (tree->root == NULL) {
        tree->root = node;
    }
    else {
        Node* temp = (Node*)malloc(sizeof(Node));//存储当前根节点内容
        temp = tree->root;
        while (temp != NULL) {
            if (temp->data > data) {
                if (temp->left == NULL) {
                    temp->left = node;
                    return;
                }
                else {
                    temp = temp->left;
                }
            }
            else {
                if (temp->data < data) {
                    if (temp->right == NULL) {
                        temp->right = node;
                        return;
                    }
                    else {
                        temp = temp->right;
                    }
                }
            }
        }
    }
}
Node* findmin(Node* node) {//找到最小值
    if (node == NULL)
        return NULL;
    while (node->left != NULL)
        node = node->left;
    return node;
}
Node *denode(Node* node, int data) {//删除
    if (node ==NULL) {
        return node;
    }
    else {
        if (node->data > data) {
            node->left = denode(node->left, data);
        }
        else if (node->data < data) {
            node->right = denode(node->right, data);
        }
        else {
            if (node->left == NULL && node->right == NULL) {
                node = NULL;
            }
            else if (node->left != NULL && node->right == NULL) {
                node = node->left;
            }
            else if (node->right != NULL && node->left == NULL) {
                node = node->right;
            }
            else {
                Node* pre = findmin(node->right);
                node = denode(node,pre->data);
                node->data = pre->data;
            }
        }
    }
    return node;
}
int height(Node* node) {//求树的高度
    if (node == NULL) {
        return -1;
    }
    else if (node->left == NULL && node->right == NULL) {
        return 0;
    }
    else {
        int left = height(node->left);
        int right = height(node->right);
        return left>right?(left + 1):(right + 1);
    }
}
Node* leftrotation(Node* node) {//左旋
    Node* temp = node->right;
    node->right = temp->left;
    temp->left = node;
    return temp;
}
Node* rightrotation(Node* node) {//右旋
    Node* temp = node->left;
    node->left = temp->right;
    temp->right = node;
    return temp;
}
Node* balance(Node* current) {//平衡
    if (current == NULL) {
        return current;
    }
    if (height(current->left) - height(current->right) > 1) {
        if (height(current->left->left) >= height(current->left->right)){
            return rightrotation(current);
        }
        else {
            return rightrotation(leftrotation(current->left));
        }
    }
    if (height(current->right) - height(current->left) > 1) {
        if (height(current->right->right) >= height(current->right->left)) {
            return leftrotation(current);
        }
        else {
            return leftrotation(rightrotation(current->right));
        }
    }
    return current;
}
void firorder(Node* node) {//先序遍历
    if (node != NULL) {
        printf("%d\n", node->data);
        firorder(node->left);
        firorder(node->right);
    }
}
int main() {
    int arry[7] = { 6,3,8,2,5,1,7 };
    Tree tree;
    tree.root = NULL;
    //printf("d%\n" + height(tree.root));
    printf("%d\n" , height(tree.root));
    for (int i = 0; i < 7; i++) {
    addnode(&tree, arry[i]);
    }
    firorder(tree.root);
    printf("--------\n");
    denode(tree.root, 7);
    firorder(tree.root);
    printf("--------\n");
    //printf("d%\n" + height(tree.root));
    printf("%d\n" , height(tree.root));
    addnode(&tree, 15);
    addnode(&tree, 17);
    addnode(&tree, 19);
    //printf("d%\n" + height(tree.root));
    printf("%d\n" , height(tree.root));
    printf("--------\n");
    balance(tree.root);
    firorder(tree.root);
    printf("--------\n");
    //printf("d%\n" + height(tree.root));
    printf("%d\n" , height(tree.root));