/*
 * 平衡二叉树的实现
 */
#ifndef BTREE_H__
#define BTREE_H__

// 宏定义
#define NAMESIZE 32

/*
 * 学生信息
 */
typedef struct stuinfo_st {
    int id; // 学号
    char name[NAMESIZE]; // 姓名
    int chinese; // 语文
    int math; // 数学
    int english; // 英语
}stuinfo;

/*
 * 二叉树
 */
typedef struct node_st {
    struct stuinfo_st data; // 数据结点
    struct node_st *lchild, *rchild; // 左子结点，右子结点
}btree;

/*
 * 添加二叉树结点
 */
int btree_insert(btree **, stuinfo *);

/*
 * 查找二叉树结点
 */
stuinfo * btree_find(btree *, int);

/*
 * 打印二叉树结点信息
 */
void node_display(stuinfo *);

/*
 * 打印二叉树
 */
void btree_display(btree *);

/*
 * 平衡二叉树
 */
void balance(btree **);

/*
 * 删除二叉树结点
 */
void delete(btree **, int);

/*
 * 先序遍历
 */
void preorderTravel(btree *);

/*
 * 中序遍历
 */
void inorderTravel(btree *);

/*
 * 后序遍历
 */
void postorderTravel(btree *);
#endif

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

#include "btree.h"

/*
 * 添加二叉树结点
 */
int btree_insert(btree **ptr, stuinfo *data) {
    btree *node; // 要添加的二叉树结点
    if (*ptr == NULL) {
        // 空树，根不存在
        node = malloc(sizeof(*node));
        if (node == NULL) {
            return -1;
        }
        // 给结点赋值
        node->data = *data;
        // 左子树
        node->lchild = NULL;
        // 右子树
        node->rchild = NULL;
        // 要添加的结点设为根
        *ptr = node;
        // 成功添加根结点
        return 0;
    }
    // 非空树，存在根
    if (data->id <= (*ptr)->data.id) {
        // 左子结点
        return btree_insert(&(*ptr)->lchild, data);
    } else {
        // 右子结点
        return btree_insert(&(*ptr)->rchild, data);
    }
}

/*
 * 查找二叉树结点
 */
stuinfo * btree_find(btree *ptr, int id) {
    if (ptr == NULL) {
        // 空树
        return NULL;
    }
    // 非空树
    if (id == ptr->data.id) {
        // 找到结点
        return &ptr->data;
    }
    if (id < ptr->data.id) {
        // 到左子结点查找
        return btree_find(ptr->lchild, id);
    } else {
        // 到右子结点查找
        return btree_find(ptr->rchild, id);
    }
}

/*
 * 打印二叉树结点信息
 */
void node_display(stuinfo *data) {
    printf("%d %s %d %d %d\n", data->id, data->name, data->chinese, data->math, data->english);
}

/*
 * 打印二叉树
 */
void draw_btree(btree *ptr, int level) {
    int i; // 循环索引值
    if (ptr == NULL) {
        // 空树
        return; // 无返回值
    }
    // 非空树
    // 打印右子结点
    draw_btree(ptr->rchild, level+1);
    for (i = 0; i < level; i++) {
        printf("\t");
    }
    // 打印结点信息
    node_display(&ptr->data);
    // 打印左子结点
    draw_btree(ptr->lchild, level+1);
}

/*
 * 打印二叉树
 */
void btree_display(btree *ptr) {
    draw_btree(ptr, 0);
}

/*
 * 获取结点数
 */
static int get_num(btree *ptr) {
    if (ptr == NULL) {
        // 空树
        return 0;
    }
    // 左子树总结点数 + 根结点 + 右子树总结点数
    return get_num(ptr->lchild) + 1 + get_num(ptr->rchild);
}

/*
 * 查找最左边的结点
 */
static btree * find_min(btree *ptr) {
    if (ptr->lchild == NULL) {
        return ptr;
    }
    return find_min(ptr->lchild);
}

/*
 * 向左旋转
 */
static void rotate_left(btree **ptr) {
    btree *node = *ptr; // 保存旧的根结点
    // 右子结点作为新的根结点
    *ptr = node->rchild;
    // 原右子结点置空
    node->rchild = NULL;
    /*
     * 旧的根结点作为新的根结点的左子结点
     * 由于新的根结点可能存在左子树，
     * 因此，旧的根结点应该成为左子树的最左子结点
     */
    find_min(*ptr)->lchild = node;
}

/*
 * 查找最右边的结点
 */
static btree * find_max(btree *ptr) {
    if (ptr->rchild == NULL) {
        return ptr;
    }
    return find_max(ptr->rchild);
}

/*
 * 向右旋转
 */
static void rotate_right(btree **ptr) {
    btree *node = *ptr; // 保存旧的根结点
    // 左子结点作为新的根结点
    *ptr = node->lchild;
    // 原左子结点置空
    node->lchild = NULL;
    /*
     * 旧的根结点作为新的根结点的右子结点
     * 由于新的根结点可能存在右子树，
     * 因此，旧的根结点应该成为右子树的最右子结点
     */
    find_max(*ptr)->rchild = node;
}

/*
 * 平衡二叉树
 */
void balance(btree **ptr) {
    int sub; // 左子树与右子树的结点总数差值
    if (*ptr == NULL) {
        // 空树
        return; // 无返回值
    }
    
    while(1) {
        sub = get_num((*ptr)->lchild) - get_num((*ptr)->rchild);
        if (sub >= -1 && sub <= 1) {
            // 达到平衡
            break;
        }
        if (sub < -1) {
            // 向左旋转
            rotate_left(ptr);
        } else {
            // 向右旋转
            rotate_right(ptr);
        }
    }
    // 平衡左子树
    balance(&(*ptr)->lchild);
    // 平衡右子树
    balance(&(*ptr)->rchild);
}

/*
 * 删除二叉树结点
 */
void delete(btree **ptr, int id) {
    btree **node = ptr; // 保存旧的根结点
    btree *cur = NULL; // 要删除的结点
    while (*node != NULL && (*node)->data.id != id) {
        if (id < (*node)->data.id) {
            // 往左子树方向查找
            node = &(*node)->lchild;
        } else {
            // 往右子树方向查找
            node = &(*node)->rchild;
        }
    }
    if (*node == NULL) {
        // 没有找到
        return; // 无返回值
    }
    cur = *node; // 得到要删除的结点
    if (cur->lchild == NULL) {
        // 要删除结点的左子树为空
        // 把右子树挂到当前结点的位置
        *node = cur->rchild;
    } else {
        // 要删除的结点存在左子树
        // 把左子树挂到当前结点的位置
        *node = cur->lchild;
        // 把右子树挂到左子树的最右边结点上
        find_max(cur->lchild)->rchild = cur->rchild;
    }
    // 释放掉删除的结点
    free(cur);
}

/*
 * 先序遍历
 */
void preorderTravel(btree *ptr) {
    if (ptr == NULL) {
        return;
    }
    // 根
    node_display(&ptr->data);
    // 左
    preorderTravel(ptr->lchild);
    // 右
    preorderTravel(ptr->rchild);
}

/*
 * 中序遍历
 */
void inorderTravel(btree *ptr) {
    if (ptr == NULL) {
        return;
    }
    // 左
    inorderTravel(ptr->lchild);
    // 根
    node_display(&ptr->data);
    // 右
    inorderTravel(ptr->rchild);
}

/*
 * 后序遍历
 */
void postorderTravel(btree *ptr) {
    if (ptr == NULL) {
        return;
    }
    // 左
    postorderTravel(ptr->lchild);
    // 右
    postorderTravel(ptr->rchild);
    // 根
    node_display(&ptr->data);
}

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

int main() {
    int i; // 循环索引值
    btree *tree = NULL;
    stuinfo stu_st; // 操作中的学生信息
    int id = 5; // 要删除的学号
    // 二叉树中的学生学号
    int stu_id[] = {2, 5, 8, 1, 7, 0, 3, 9, 6, 4};
    /* 往二叉树中添加 7 条随机数据 */
    printf("依次往二叉树中添加结点：\n");
    for (i = 0; i < sizeof(stu_id)/sizeof(*stu_id); i++) {
        stu_st.id = stu_id[i];
        snprintf(stu_st.name, NAMESIZE, "stu%d", stu_id[i]);
        stu_st.chinese = rand() % 100;
        stu_st.math = rand() % 100;
        stu_st.english = rand() % 100;
        node_display(&stu_st);
        btree_insert(&tree, &stu_st);
    }
    /* 打印二叉树 */
    printf("平衡前的二叉树：\n");
    btree_display(tree);
    /* 平衡二叉树 */
    balance(&tree);
    /* 打印二叉树 */
    printf("平衡后的二叉树：\n");
    btree_display(tree);
    /* 删除结点 */
    delete(&tree, id);
    /* 打印二叉树 */
    printf("删除结点后的二叉树：\n");
    btree_display(tree);
    /* 先序遍历 */
    printf("执行先序遍历：\n");
    preorderTravel(tree);
    /* 中序遍历 */
    printf("执行中序遍历：\n");
    inorderTravel(tree);
    /* 后序遍历 */
    printf("执行后序遍历：\n");
    postorderTravel(tree);
    exit(0);
}

OBJS=main.o btree.o
CC=gcc
CFLAGS+=-c -Wall -g
btree:$(OBJS)
    $(CC) $^ -o $@
%.o:%.c
    $(CC) $^ $(CFLAGS) -o $@
clean:
    $(RM) *.o btree -r

root@RicenOS:~# make
gcc main.c -c -Wall -g -o main.o
gcc btree.c -c -Wall -g -o btree.o
gcc main.o btree.o -o btree
root@RicenOS:~# ./btree
依次往二叉树中添加结点：
2 stu2 83 86 77
5 stu5 15 93 35
8 stu8 86 92 49
1 stu1 21 62 27
7 stu7 90 59 63
0 stu0 26 40 26
3 stu3 72 36 11
9 stu9 68 67 29
6 stu6 82 30 62
4 stu4 23 67 35
平衡前的二叉树：
            9 stu9 68 67 29
        8 stu8 86 92 49
            7 stu7 90 59 63
                6 stu6 82 30 62
    5 stu5 15 93 35
            4 stu4 23 67 35
        3 stu3 72 36 11
2 stu2 83 86 77
    1 stu1 21 62 27
        0 stu0 26 40 26
平衡后的二叉树：
        9 stu9 68 67 29
    8 stu8 86 92 49
        7 stu7 90 59 63
            6 stu6 82 30 62
5 stu5 15 93 35
            4 stu4 23 67 35
        3 stu3 72 36 11
    2 stu2 83 86 77
        1 stu1 21 62 27
            0 stu0 26 40 26
删除结点后的二叉树：
                9 stu9 68 67 29
            8 stu8 86 92 49
                7 stu7 90 59 63
                    6 stu6 82 30 62
        4 stu4 23 67 35
    3 stu3 72 36 11
2 stu2 83 86 77
    1 stu1 21 62 27
        0 stu0 26 40 26
执行先序遍历：
2 stu2 83 86 77
1 stu1 21 62 27
0 stu0 26 40 26
3 stu3 72 36 11
4 stu4 23 67 35
8 stu8 86 92 49
7 stu7 90 59 63
6 stu6 82 30 62
9 stu9 68 67 29
执行中序遍历：
0 stu0 26 40 26
1 stu1 21 62 27
2 stu2 83 86 77
3 stu3 72 36 11
4 stu4 23 67 35
6 stu6 82 30 62
7 stu7 90 59 63
8 stu8 86 92 49
9 stu9 68 67 29
执行后序遍历：
0 stu0 26 40 26
1 stu1 21 62 27
6 stu6 82 30 62
7 stu7 90 59 63
9 stu9 68 67 29
8 stu8 86 92 49
4 stu4 23 67 35
3 stu3 72 36 11
2 stu2 83 86 77