/*
 * 二叉树的简单实现
 */
#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 *);

#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);
}

/*
 * 逆时针旋转 90 度打印二叉树
 */
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);
}

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

int main() {
    int i; // 循环索引值
    btree *tree = NULL;
    stuinfo stu_st, *stu_ptr; // 操作中的学生信息
    int id = 7; // 要查找的学号
    // 二叉树中的学生学号
    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);
    /* 查找二叉树中的指定结点 */
    stu_ptr = btree_find(tree, id);
    if (stu_ptr == NULL) {
        printf("没有找到任何数据！\n");
    } else {
        /* 显示二叉树中的结点 */
        printf("查找到的学生信息：");
        node_display(stu_ptr);
    }
    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
查找到的学生信息：7 stu7 90 59 63