C-数据结构-平横二叉树

平衡二叉树（Balanced Binary Tree）是一种二叉树，其中任意节点的两棵子树的高度差不超过 1。也可以说是一棵空树或者左右子树高度差不超过 1 的二叉树。

特点和性质

1. 高度平衡：平衡二叉树是一种高度平衡的二叉树，任意节点的左右子树高度差不超过 1。
2. 高度复杂度：由于平衡性质，平衡二叉树的高度复杂度为 O(log n)，其中 n 是树中节点的数量。
3. 插入和删除操作效率高：由于平衡性质，插入和删除操作的平均时间复杂度也是 O(log n)。
4. 查找操作效率高：在平衡二叉树中查找元素的时间复杂度也是 O(log n)。
5. 常见实现：AVL 树和红黑树是常见的平衡二叉树实现。

平衡因子

在平衡二叉树中，每个节点的平衡因子是其左子树高度和右子树高度之差。平衡因子的取值范围通常为 {-1, 0, 1}，表示左右子树的高度差为 -1、0 或 1。

平衡操作

当向平衡二叉树中插入或删除节点时，可能会破坏树的平衡性质，此时需要通过旋转操作来恢复平衡。常见的旋转操作包括左旋和右旋，以及它们的组合操作。

应用

平衡二叉树广泛用于需要高效的插入、删除和查找操作的场景，例如数据库索引、缓存实现等。

‘’’
下面代码实现了二叉树的平衡
以及删除 查找 4种遍历 draw
‘’’

main.c

#include<stdio.h>
#include<stdlib.h>#include<queue.h>	//已经被封装成动态库#define NAMESIZE	32struct score_st
{int id;char name[NAMESIZE];int math;int chinese;
};struct node_st
{struct score_st data;struct node_st *l,*r;
};static struct node_st *tree = NULL;//把tree提升到全局变量,当前文件static void print_s(struct score_st *d)
{printf("%d %s %d %d\n",d->id,d->name,d->math,d->chinese);
}int insert(struct node_st **root,struct score_st *data)
{struct node_st *node;if(*root == NULL){node = malloc(sizeof(*node));if(node == NULL)return -1;node->data = *data;node->l = NULL;node->r = NULL;*root = node;return 0;}if(data->id <= (*root)->data.id)return insert(&(*root)->l,data);elsereturn insert(&(*root)->r,data);
}
struct score_st *find(struct node_st *root,int id)
{if(root == NULL)return NULL;if(id == root->data.id)return &root->data;if(id < root->data.id)return find(root->l,id);elsereturn find(root->r,id);
}
void draw_(struct node_st *root,int level)
{int i;if(root == NULL)return ;draw_(root->r,level+1);for(i = 0;i<level;i++)printf("    ");print_s(&root->data);draw_(root->l,level+1);
}
void draw(struct node_st *root)
{draw_(root,0);printf("\n\n");//getchar();//相当于暂停
}static int get_num(struct node_st *root)
{if(root == NULL)return 0;return get_num(root->l) +1 +get_num(root->r);}static struct node_st *find_min(struct node_st *root)
{if(root->l == NULL)return root;return find_min(root->l);
}static void turn_left(struct node_st **root)
{struct node_st *cur = *root;*root = cur->r;cur->r = NULL;find_min(*root)->l = cur;//draw(tree);//测试语句
}static struct node_st *find_max(struct node_st *root)
{if(root->r == NULL)return root;return find_max(root->l);
}static void turn_right(struct node_st **root)
{struct node_st *cur = *root;*root = cur->l;cur->l = NULL;find_max(*root)->r = cur;//draw(tree);//测试语句
}void balance(struct node_st **root)//函数实现 先把伪代码写出来 ，梳理清楚整个的逻辑关系
{int sub;if(*root == NULL)return ;while(1){sub = get_num((*root)->l) -get_num((*root)->r);if(sub >= -1 && sub <=1)break;if(sub < -1)turn_left(root);elseturn_right(root);}balance(&(*root)->l);balance(&(*root)->r);
}void detele(struct node_st **root,int id)//删除一个节点 左边顶上来
{struct node_st **node = root;struct node_st *cur = NULL;while(*node != NULL && (*node)->data.id != id){if(id < ((*node)->data.id))&node = (*node)->l;else&node = (*node)->r;}if(*node == NULL)return ;cur = *node;if(cur->l == NULL)*node = cur->r;else{*node = cur->l;find_max(cur->l)->r = cur->r;}free(cur);
}#if 0
void travel(struct node_st *root)//先序遍历 根 左 右  中序遍历 左 根 右 后序遍历 后序遍历 左 右 根
{if(root == NULL)return ;print_s(&root->data);//travel(root->l);  	 //travel(root->l);travel(root->l);	//print_s(&root->data);  //travel(root->r);travel(root->r);	//travel(root->r);		 //print_s(&root->data)
}
#elsevoid travel(struct node_st *root)//借助之前封装好的queue库 
{int ret;QUEUE *qu;struct node_st *cur;qu = queue_create(sizeof(struct node_st *));if(qu == NULL)return ;queue_en(qu,&root);/*if error*/while(1){ret = queue_de(qu,&cur);if(ret == -1)break;print_s(&cur->data);if(cur->l !=NULL)queue_en(qu,&cur->l);if(cur->r !=NULL)queue_en(qu,&cur->r);}queue_deatroy(qu);
}#endifint main()
{int arr[] = {1,2,3,7,6,5,9,8,4};int i;struct score_st tmp,*datap;struct node_st *tree = NULL;for(i = 0;i<sizeof(arr)/sizeof(*arr);i++){tmp.id = arr[i];snprintf(tmp.name,NAMESIZE,"stu%d",arr[i]);tmp.math = rand()%100;tmp.chinese = rand()%100;insert(&tree,&tmp);}draw(tree);balance(&tree);draw(tree);travel(tree);#if 0	int tmpid = 5;delete(&tree,tmpid);draw(tree);
#endif#if 0
//测试语句int tmpid = 2;datap = find(tree,tmpid);if(datap == NULL)printf("can not find the id %d\n",tmpid);elseprint_s(datap);
#endifexit(0);
}

gcc main.c -lqueue -lllist -o main
./main

补充说明

对于 这样的函数参数 struct node_st **root

您的理解基本上是正确的，但是有一个小的修正。让我详细解释一下：

• *root 是指向 struct node_st * 类型的指针。它存储了一个指向 struct node_st 类型的指针的地址。
• 因此，**root 是一个 struct node_st 类型的结构体，因为它解引用了 *root，得到了一个指向 struct node_st 类型的指针，然后再次解引用这个指针，得到了 struct node_st 类型的实际结构体。

因此，root 是一个指向指针的指针，可以用来修改指针指向的内容，从而改变原始指针的值。这在函数中经常用于修改指针的指向，例如在函数中分配内存并将其地址存储在指针中。