草庐IT

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

Mai___ 2023-04-23 原文

题干

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




根据四种情况的图片，对应着进行代码的理解
还是比较明了

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

练习PTAspanclasstoken

有关PTA练习4.2 平衡二叉树的根 (25 分)的更多相关文章

  1. ruby - 为什么 4.1%2 使用 Ruby 返回 0.0999999999999996？但是 4.2%2==0.2 - 2

    为什么4.1%2返回0.0999999999999996？但是4.2%2==0.2。 最佳答案 参见此处:WhatEveryProgrammerShouldKnowAboutFloating-PointArithmetic实数是无限的。计算机使用的位数有限(今天是32位、64位)。因此计算机进行的浮点运算不能代表所有的实数。0.1是这些数字之一。请注意，这不是与Ruby相关的问题，而是与所有编程语言相关的问题，因为它来自计算机表示实数的方式。 关于ruby-为什么4.1%2使用Ruby返

  2. ruby - 匹配未转义的平衡定界符对 - 2

    如何匹配未被反斜杠转义的平衡定界符对(其本身未被反斜杠转义)(无需考虑嵌套)？例如对于反引号，我试过了，但是转义的反引号没有像转义那样工作。regex=/(?!$1:"how\\"#expected"how\\`are"上面的正则表达式不考虑由反斜杠转义并位于反引号前面的反斜杠，但我愿意考虑。StackOverflow如何做到这一点？这样做的目的并不复杂。我有文档文本，其中包括内联代码的反引号，就像StackOverflow一样，我想在HTML文件中显示它，内联代码用一些spanMaterial装饰。不会有嵌套，但转义反引号或转义反斜杠可能出现在任何地方。

  3. 牛客网专项练习30天Pytnon篇第02天 - 2

    1.在Python3中，下列关于数学运算结果正确的是:（B）a=10b=3print(a//b)print(a%b)print(a/b)A.3，3，3.3333...B.3，1，3.3333...C.3.3333...，3.3333...，3D.3.3333...，1，3.3333...解析：    在Python中，//表示地板除（向下取整），%表示取余，/表示除（Python2向下取整返回3）2.如下程序Python2会打印多少个数:（D）k=1000whilek>1:    print(k)k=k/2A.1000 B.10C.11D.9解析：    按照题意每次循环K/2，直到K值小于等

  4. ruby - 在 Ruby 中实现二叉树 - 2

    我一直在尝试在Ruby中实现BinaryTree类，但我得到了stackleveltoodeep错误，尽管我似乎没有在该特定代码段中使用任何递归:1.classBinaryTree2.includeEnumerable3.4.attr_accessor:value5.6.definitialize(value=nil)7.@value=value8.@left=BinaryTree.new#stackleveltoodeephere9.@right=BinaryTree.new#andhere10.end11.12.defempty?13.(self.value==nil)?true:

  5. ruby-on-rails - Rails 4.1 和 4.2 之间 ActiveRecord Setter 的区别？ - 2

    我们将我们的应用程序从Rails4.1.14升级到4.2.5.1并遇到了以下问题:string="SomeString"ar_model=SomeArModel.newar_model.some_attribute=string#nextlineistruefor4.1,butfailsfor4.2ar_model.some_attribute.object_id==string.object_id显然，对象setter会复制每个对象(如果我有一个数组，里面的每个对象也会被复制)，我想知道，这是不是有意为之并且是某些新安全功能的一部分？更新我将ruby​​-2.2.2p95用于两个ra

  6. ruby-on-rails - Ruby On Rails 4.2 的可视化日志查看器 - 2

    我以前在Laravel4上工作过，它有一个很棒的日志查看器工具laravellogviewer查看demo我正在寻找与Rubyonrails4.2非常相似的东西，如果你们知道Rails4.2的任何好的可视化日志记录GEM，请告诉我..从代码我需要记录不同的日志级别，这个工具应该直观地组织我的日志，谢谢.. 最佳答案 这应该可以帮助您入门https://github.com/shadabahmed/logstasher如其所说Thisgemisheavilyinspiredfromlograge,butit'sfocusedonone

  7. ruby-on-rails - Rails 4.2 Action Controller :BadRequest custom error message - 2

    如果验证失败或参数丢失，我想从我的Controller返回400-错误请求。所以在我的Controller中如果有ifparams["patch"].nil?thenraiseActionController::BadRequest.new("TheJsonbodyneedstobewrappedinsidea\"Patch\"key")end我在我的应用程序Controller中发现了这个错误:rescue_fromActionController::BadRequest,with::bad_requestdefbad_request(exception)renderstatus:4

  8. ruby - 检查字符串是否有平衡括号 - 2

    我目前正在做一个Ruby问题测验，但我不确定我的解决方案是否正确。运行检查后，它显示编译成功，但我只是担心这不是正确的答案。问题:AstringSconsistingonlyofcharacters'('and')'iscalledproperlynestedif:Sisempty,Shastheform"(U)"whereUisaproperlynestedstring,Shastheform"VW"whereVandWareproperlynestedstrings.Forexample,"(()(())())"isproperlynestedand"())"isn't.Write

  9. ruby - 开始使用 MacRuby 和 Xcode 4.2 - 2

    我最近想开始使用MacRuby。我已经安装了Xcode4.2和MacRuby，但显然我遗漏了一些东西。到目前为止，在我发现的每个教程中都说，我必须从Xcode模板中选择“MacRuby应用程序”……但是没有这样的条目可用。我试过0.10和几天前发布的每晚版本。我查看了MacRuby的安装位置，我找到了Xcode3.0的模板……我必须使用这些模板吗？如何将它们导入Xcode4.2？在开始之前，我还想知道，从MacRuby开始是否安全？乍一看，我认为"is"，因为有新的MacRuby书籍可用——但MacRuby网站上似乎没有太多事件(去年3月的最后一篇博客文章？)……根据我的经验，这可能是

  10. ruby-on-rails - 在 Rails 4.2 中有许多 'finder_sql' 替换 - 2

    我有一个关联需要一些连接/自定义查询。当试图弄清楚如何实现它时，重复的响应是finder_sql。但是在Rails4.2(及更高版本)中:ArgumentError:Unknownkey::finder_sql我执行连接的查询如下所示:'SELECTDISTINCT"tags".*'\'FROM"tags"'\'JOIN"articles_tags"ON"articles_tags"."tag_id"="tags"."id"'\'JOIN"articles"ON"article_tags"."article_id"="articles"."id"'\'WHEREarticles"."u

随机推荐