7.9、平衡二叉树(Balanced Binary Tree)
简称平衡树(AVL树)—— 树上任一结点的左子树和右子树的高度只差不会超过1
结点的平衡因子 = 左子树高度 – 右子树高度
得到:平衡二叉树的结点的平衡因子只能为\(-1、0、1\)
最小不平衡树(LL)
最小不平衡树(RR)
最小不平衡树(LR)
最小不平衡树(RL)
左旋和右旋操作
代码实现
#include <stdio.h>
#include <stdlib.h>
#define ElemType int
#define boolean int
#define true 1
#define false 0
//建立一个平衡二叉树的结构体
typedef struct AVLNode{
ElemType data;//数据
int heigth;//高度
struct AVLNode *lchild,*rchild;
}AVLNode ,*AVLTree;
int GetHeight(AVLNode *node){
return node == NULL ? 0:node->heigth;
}
int GetMax(int a,int b){
return a > b ? a : b;
}
//右旋操作
void llRotation(AVLNode *node,AVLNode **root){
AVLNode *p = node->lchild;
node->lchild = p->rchild;
p->rchild = node;
node->heigth = GetMax(GetHeight(node->lchild),GetHeight(node->rchild)) + 1;
p->heigth = GetMax(GetHeight(p->lchild),GetHeight(p->rchild)) + 1;
*root = p;
}
//左旋操作
void rrRotation(AVLNode *node,AVLNode **root){
AVLNode *p = node->rchild;
node->rchild = p->lchild;
p->lchild = node;
node->heigth = GetMax(GetHeight(node->lchild),GetHeight(node->rchild))+1;
p->heigth = GetMax(GetHeight(p->lchild),GetHeight(p->rchild))+1;
*root = p;
}
//建立一颗平衡二叉树
boolean AVL_Insert(AVLTree *T,ElemType e){
if(*T == NULL){
*T = (AVLTree)malloc(sizeof(AVLNode));
if(*T == NULL) return false;
(*T)->data = e;
(*T)->rchild = (*T)->lchild = NULL;
(*T)->heigth = 0;
}else if((*T)->data > e){
//小于往左走
AVL_Insert(&(*T)->lchild,e);
//拿到当前左右子树的高度
int lHeight = GetHeight((*T)->lchild);//左子树高度
int rHeight = GetHeight((*T)->rchild);//右子树高度
//判断高度差
if(lHeight - rHeight == 2){
//当前结点插入到该结点的左边;只有两种情况LL,LR
if((*T)->lchild->data > e){//插入到左边
//LL
llRotation(*T,T);//右旋
}else{
//LR
rrRotation((*T)->lchild,&(*T)->lchild);//左孩子的右孩子左旋
llRotation(*T,T);//左孩子右旋
}
}
}else if((*T)->data < e){
//大于往右走
AVL_Insert(&(*T)->rchild,e);
//拿到当前左右子树的高度
int lHeight = GetHeight((*T)->lchild);//左子树高度
int rHeight = GetHeight((*T)->rchild);//右子树高度
//判断高度差
if(rHeight - lHeight == 2){
//当前结点插入到该结点的右边;只有两种情况RR,RL
if((*T)->rchild->data < e){//插入到左边
//RR
rrRotation(*T,T);//左旋
}else{
//RL
llRotation((*T)->rchild,&(*T)->rchild);//右孩子的左孩子右旋
rrRotation(*T,T);//右孩子左旋
}
}
}else{
//等于返回插入失败
printf("插入的结点的值存在,插入失败\n");
return false;
}
//修改结点的高度
(*T)->heigth = GetMax(GetHeight((*T)->lchild),GetHeight((*T)->rchild)) + 1;
return true;
}
//访问结点
void Vist(AVLNode *node){
printf("%d , ",node->data);
}
//先序遍历
void PreOrder(AVLTree T){
if(T != NULL){
Vist(T);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
int main(){
AVLTree T = NULL;
int nums[5] = {5,4,3,2,1};
for(int i = 0;i < 5;i++){
AVL_Insert(&T,nums[i]);
}
PreOrder(T);
return 0;
}
//结果:
4 , 2 , 1 , 3 , 5 ,
原文地址:http://www.cnblogs.com/shuisanya/p/16849432.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性