PTA练习4.2 平衡二叉树的根 (25 分)

这篇具有很好参考价值的文章主要介绍了PTA练习4.2 平衡二叉树的根 (25 分)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题干

将给定的一系列数字插入初始为空的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实现思路
分为四种情况
左单旋,右单旋,左右双旋,右左双旋
各种情况如图

PTA练习4.2 平衡二叉树的根 (25 分)
PTA练习4.2 平衡二叉树的根 (25 分)
PTA练习4.2 平衡二叉树的根 (25 分)
PTA练习4.2 平衡二叉树的根 (25 分)
根据四种情况的图片,对应着进行代码的理解
还是比较明了

存在一个小问题
AVLTree B = T->Right
是重新申请了一个类型为AVLTree的B
另外申请空间实现对旋转结果的复制
这就是为什么T->Left=B->Right;这一句存在的原因
因为并不是在原有平衡树上进行修改
不然就会造成错误
导致新申请的B左右两边出现重复的部分

PTA练习4.2 平衡二叉树的根 (25 分)文章来源地址https://www.toymoban.com/news/detail-403422.html

到了这里,关于PTA练习4.2 平衡二叉树的根 (25 分)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】二叉排序树——平衡二叉树的调整

    参考视频: 懒猫老师-数据结构-(59)平衡二叉树【互动视频】 (1)什么是平衡二叉树 平衡二叉树(Balanced Binary Tree)是一种特殊的二叉查找树,它的目的是保持树的高度尽量平衡,以保证查找、插入、删除等操作的时间复杂度为 O(log n)。 常见的平衡二叉树算法包括 AVL 树、红

    2024年02月04日
    浏览(39)
  • day17 | 110.平衡二叉树、 257. 二叉树的所有路径、 404.左叶子之和

    目录: 题目链接: https://leetcode.cn/problems/balanced-binary-tree/ https://leetcode.cn/problems/binary-tree-paths/ 110. 平衡二叉树 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 示

    2024年02月08日
    浏览(42)
  • 算法刷题Day 17 平衡二叉树+二叉树的所有路径+左叶子之和

    计算左右两棵子树的高度,如果有一个高度是-1(有一棵子树不平衡),直接返回-1,否则计算高度差,判断是否不平衡 使用 回溯 的方法,每次处理一个节点之前要把它push进table里,处理完之后又要把它pop出来 处理一个节点时,要判断它是否是左节点(需要父节点,可以通

    2024年02月15日
    浏览(42)
  • 数据结构——常见二叉树的分类(完全二叉树、满二叉树、平衡二叉树、二叉搜索树、红黑树)

    专业术语 中文 描述 Root 根节点 一棵树的顶点 Child 孩子结点 一个结点含有的子树的根节点称为该结点的子节点 Leaf 叶子结点 没有孩子的节点 Degree 度 一个节点包含子树的数量 Edge 边 一个节点与另外一个节点的连接 Depth 深度 根节点到这个节点经过边的数量 Height 节点高度 从

    2024年02月03日
    浏览(44)
  • Day17|leetcode 110.平衡二叉树、257.二叉树的所有路径、404.左叶子之和

    题目链接:110. 平衡二叉树 - 力扣(LeetCode) 视频链接:后序遍历求高度,高度判断是否平衡 | LeetCode:110.平衡二叉树_哔哩哔哩_bilibili 平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 本题就是求左右子树的高度差,如果差值=1,就是平衡

    2024年02月11日
    浏览(41)
  • 算法训练day17leetcode110平衡二叉树257二叉树的所有路径404左叶子之和

    https://www.bilibili.com/video/BV1GY4y1K7z8/?vd_source=8272bd48fee17396a4a1746c256ab0ae https://programmercarl.com/0404.%E5%B7%A6%E5%8F%B6%E5%AD%90%E4%B9%8B%E5%92%8C.html#%E6%80%9D%E8%B7%AF 采用后序递归遍历,比较左右子树的高度,相差小于等于1 前序,中左右,从根节点到叶子节点,会一直向下遍历下去,不会返回信

    2024年01月19日
    浏览(43)
  • 数据结构课设(五)二叉排序树与平衡二叉树的实现

    假定二叉排序树与平题所处理数据均为整型。分别采用二叉链表和顺序表作存储结构,实现对二叉衡二叉树的操作。具体要求如下: (1)用二叉链表作存储结构: ①读入一个整数序列L(要求该整数序列从磁盘文件读取),生成一棵二叉排序树②对二叉排序树T作中序遍历,输出结果

    2024年02月12日
    浏览(45)
  • 对动态 DP 和全局平衡二叉树的一点补充解释

    说明:最近在帮高中竞赛教练写讲义,这是本人对讲义中动态 DP 内容的补充解释(因为主要是对知识点的理解,不太容易用通用的语言表述,也不适合作为讲义内容供读者阅读,所以用的是补充注释的形式)。 写的比较抽象也比较初等,仅供意会 。 我们先从一般的角度,用

    2024年02月11日
    浏览(33)
  • 二叉树的练习

    单值二叉树,可以使用等式的传递性来解决,根的值和左右子树的值相比较,看是否相等。再比较左右子树。递归求出是否为单值二叉树。 代码如下: 先比比较根,在比较左右子树。 先比较根的左右子树的根。在比较左子树的左和右子树的右,左子树的右和右子树的左 前序

    2024年02月11日
    浏览(30)
  • 二叉树的遍历+基础练习

    前面完全二叉树适合存放数据,又因为它在内存中连续存储,因此用顺序表来实现它,并介绍了堆排序及TOP-K问题。 今天我们了解一下二叉树的遍历问题,并完成几道二叉树基础练习 目录 二叉树的遍历 先序 访问顺序: 图示:  中序 访问顺序: 图示: 后序 访问顺序: 图示

    2024年02月09日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包