题干
将给定的一系列数字插入初始为空的AVL树,请你输出最后生成的AVL树的根结点的值。
输入格式: 输入的第一行给出一个正整数N(≤20),随后一行给出N个不同的整数,其间以空格分隔。
输出格式: 在一行中输出顺序插入上述整数到一棵初始为空的AVL树后,该树的根结点的值。
输入样例1: 5 88 70 61 96 120
输出样例1: 70
输入样例2: 7 88 70 61 96 120 90 65
输出样例2: 88
首先什么是平衡二叉树呢?
平衡二叉树又被叫做AVL树,它具有这样的性质
任何一个结点左右两个子树的高度差的绝对值不超过1
为什么需要构造这样的树呢?
它可以很好地解决二叉查找树退化成链表的问题
比如说当你按自然递增递减的顺序往二叉查找树中输入结点数值时
这棵二叉查找树就是一个链表,显然有问题
所以通过各种不同的情况,对二叉查找树进行旋转
把插入、查找、删除的时间复杂度最好最坏情况都维持在O(logN)
这是我理解的平衡二叉树的意义
代码如下
#include <stdio.h>
#include <malloc.h>
typedef struct BiTNode {
int Data;
struct BiTNode *Left;
struct BiTNode *Right;
}*AVLTree;
AVLTree SingleLeftRotation(AVLTree T) {//左单旋
AVLTree B=T->Left;
T->Left=B->Right;
B->Right=T;
return B;
}
AVLTree SingleRightRotation(AVLTree T) {//右单旋
AVLTree B=T->Right;
T->Right=B->Left;
B->Left=T;
return B;
}
AVLTree DoubleLeftRightRotation(AVLTree T) {//左右双旋
T->Left=SingleRightRotation(T->Left);
return SingleLeftRotation(T);
}
AVLTree DoubleRightLeftRotation(AVLTree T) {//右左双旋
T->Right=SingleLeftRotation(T->Right);
return SingleRightRotation(T);
}
AVLTree Insert(AVLTree T,ElemType X) {
int GetHeight(AVLTree T);
if(!T) {
T=(AVLTree)malloc(sizeof(AVLTree));//申请空间插入
T->Data=X;
T->Left=NULL;
T->Right=NULL;
} else {
if(X>T->Data) {
T->Right=Insert(T->Right,X);
if(GetHeight(T->Right)-GetHeight(T->Left)==2) {
if(X<T->Right->Data) {
T=DoubleRightLeftRotation(T);
} else T=SingleRightRotation(T);
}
} else if(X<T->Data) {
T->Left=Insert(T->Left,X);
if(GetHeight(T->Left)-GetHeight(T->Right)==2) {
if(X>T->Left->Data) {
T=DoubleLeftRightRotation(T);
} else T=SingleLeftRotation(T);
}
}
}
return T;
}
int GetHeight(AVLTree T) {
if(!T)
return 0;
int hl=GetHeight(T->Left);
int hr=GetHeight(T->Right);
return (hl>hr?hl:hr)+1;
}
int main() {
int n,x,i;
scanf("%d",&n);
AVLTree T=NULL;
for(i=0; i<n; i++) {
scanf("%d",&x);
T=Insert(T,x);
}
printf("%d",T->Data);
return 0;
}
首先想要构建一个平衡二叉树
肯定是输入结点、寻找结点插入位置、插入结点这三个必须的步骤
然后在寻找到结点插入顺序之后
对树进行平衡的判断
不平衡就进行调整,平衡就继续下一个结点的插入
大体思路就是这样
所以说整个函数
应该包括插入函数insert
判断结点左右高度差函数GetHeight
以及四种不平衡情况的调平函数rotation
Insert函数的实现思路
将输入的结点值从根结点开始一一进行比对
大于根结点的值就往根结点的右子树通过递归继续寻找插入位置
小于根结点同理
递归的出口就是通过不断地比对之后寻找到插入的空位置
创建空间将新结点插入
然后利用递归的栈特点
从距离新插入结点最近的结点开始
从下往上进行平衡的检测
不平衡就进行旋转
存在一个问题
T->Right=Insert(T->Right,X);
为什么需要用T->Right=Insert
脑子秀逗了
因为每次新申请的结点你不插入就相当于啥都没干
GetHeight实现思路
对结点进行递归处理
当结点不为空
将其左右子树作为新结点进行递归
直到左右子树为空时结束递归
不断比对左右子树高度的值
得出结点的最大高度
rotation实现思路
分为四种情况
左单旋,右单旋,左右双旋,右左双旋
各种情况如图
根据四种情况的图片,对应着进行代码的理解
还是比较明了文章来源:https://www.toymoban.com/news/detail-403422.html
存在一个小问题
AVLTree B = T->Right
是重新申请了一个类型为AVLTree的B
另外申请空间实现对旋转结果的复制
这就是为什么T->Left=B->Right;这一句存在的原因
因为并不是在原有平衡树上进行修改
不然就会造成错误
导致新申请的B左右两边出现重复的部分
文章来源地址https://www.toymoban.com/news/detail-403422.html
到了这里,关于PTA练习4.2 平衡二叉树的根 (25 分)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!