1、btree.h 文件
/*
* 平衡二叉树的实现
*/
#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
2、btree.c 文件
#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);
}
3、main.c 文件
#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);
}
4、Makefile 文件
CC=gcc
CFLAGS+=-c -Wall -g
btree:$(OBJS)
$(CC) $^ -o $@
%.o:%.c
$(CC) $^ $(CFLAGS) -o $@
clean:
$(RM) *.o btree -r
执行效果:
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
Copyright © 2005-2023 by www.ricensoftwares.com.cn All Rights Reserved.