输入关键字序列(16,3,7,11,9,26,18,14,15),给出构造一棵平衡二叉树的过程。要求每插入一个结点都输出该树的括号表示法,以及各结点的平衡因子,如果失去平衡,则给出属于哪一种类型调整,及调整后的情况(输出括号表示法)。最后再删除指定结点后,恢复平衡,再输出平衡二叉树的情况

时间: 2023-12-10 15:02:47 浏览: 74
好的,我会根据您的要求逐步构建这棵平衡二叉树。 首先,我们需要将给定的关键字序列进行排序,以便于构建平衡二叉树。排序后的序列为:3,7,9,11,14,15,16,18,26。 接下来,我们将序列的中间元素 14 插入作为树的根节点。此时,树为空,根节点的平衡因子为 0。 ``` [14(0)] ``` 接着,我们依次将剩下的元素插入二叉树中。插入 3,树的状态如下: ``` [14(1)] / \ [3(0)] [null] ``` 插入 7,树的状态如下: ``` [14(1)] / \ [3(0)] [7(0)] ``` 插入 9,树的状态如下: ``` [14(2)] / \ [7(1)] [null] / \ [3(0)] [9(0)] ``` 插入 11,树的状态如下: ``` [14(2)] / \ [7(1)] [null] / \ [3(0)] [11(0)] / \ [9(0)] [null] ``` 插入 15,树的状态如下: ``` [14(2)] / \ [7(1)] [15(0)] / \ \ [3(0)] [11(0)] [18(0)] / \ [9(0)] [null] ``` 插入 16,树的状态如下: ``` [14(-1)] / \ [7(0)] [15(-1)] / \ / \ [3(0)] [11(-1)] [18(0)] [16(0)] / \ [9(0)] [null] ``` 插入 18,树的状态如下: ``` [14(-2)] / \ [7(0)] [15(-1)] / \ / \ [3(0)] [11(-1)] [18(1)] [16(0)] / \ [9(0)] [null] ``` 插入 26,树的状态如下: ``` [14(-2)] / \ [7(0)] [18(0)] / \ / \ [3(0)] [11(-1)] [15(0)] [26(0)] / \ [9(0)] [16(0)] ``` 目前,这棵平衡二叉树已经完成构建。接下来,我们尝试删除结点 11。 从根节点开始查找 11,发现它是 7 的右子节点的左子节点。因此,我们需要以 11 为根节点做一次右旋操作,得到以下状态: ``` [14(-2)] / \ [7(0)] [18(0)] / \ / \ [3(0)] [11(0)] [15(0)] [26(0)] / \ [9(0)] [16(0)] ``` 此时,平衡二叉树已经恢复平衡。

相关推荐

最新推荐

recommend-type

Java面试笔试资料大全

3、编写一个截取字符串的函数,输入为一个字符串和字节数,输出为按字节截取的字符串,但要保证汉字不被截取半个,如“我ABC”,4,应该截取“我AB”,输入“我ABC汉DEF”,6,应该输出“我ABC”,而不是“我ABC+汉...
recommend-type

通过 Matlab 测试共轭和双共轭梯度算法.zip

通过 Matlab 测试共轭和双共轭梯度算法.zip
recommend-type

基于卡尔曼估计温湿度的MATLAB程序-带交互-真实值可自己输入

背景:一维卡尔曼滤波的MATLAB例程,​背景为温度估计。 代码介绍:运行程序后,可以自己输入温度真实值 滤波前的值和滤波后的值分别于期望值(真实值)作差,可以得到​误差​曲线图 更多介绍:https://blog.csdn.net/callmeup/article/details/139374191
recommend-type

固件固件固件固件固件固件固件固件固件.txt

固件固件固件固件固件固件固件固件
recommend-type

毕业设计 - 基于JAVA的银行柜员业务绩效考核系统的设计与实现

业务绩效考核系统主要目的是使绩效考核信息管理清晰化,基本功能包括:权限处理模块、输入模块、处理模块、统计输出模块、维护模块等。本系统结构如下: 系统功能模块: 1.权限处理模块:管理员与普通柜员,管理员进入的是管理员页面,普通柜员进入普通柜员的界面。 2.输入模块 2.1 普通柜员用户注册:普通柜员通过输入用户名(工号即用户名),名字,密码进行注册,获得进入本系统权限。 2.2 柜员选择柜员身份登入:柜员进入后可以查看本人工作情况的信息。 2.3 管理员界面:登入后,记录柜员工作情况:输入柜员工号,柜员名字,记录业务笔数,最后一栏并记录柜员员工加减分情况(笔数处于10的整数部分为加减分情况,以10分为上限)。除此之外,管理员还能对普通柜员的权限进行修改,删除不必要的用户。 2.4 对管理员输入数据进行处理:比如工号只能为7位,开头必须是882;加分减分的值不能大于10等等。 3.处理模块 3.1 查询:输入柜员工号,可以查询到该柜员的工作情况以及加分减分情况及薪酬情况;按日期查询,可以查询到该日期本合作银行每位柜员的工作情况及加减分情况。 3.2
recommend-type

zigbee-cluster-library-specification

最新的zigbee-cluster-library-specification说明文档。
recommend-type

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire
recommend-type

MATLAB柱状图在信号处理中的应用:可视化信号特征和频谱分析

![matlab画柱状图](https://img-blog.csdnimg.cn/3f32348f1c9c4481a6f5931993732f97.png) # 1. MATLAB柱状图概述** MATLAB柱状图是一种图形化工具,用于可视化数据中不同类别或组的分布情况。它通过绘制垂直条形来表示每个类别或组中的数据值。柱状图在信号处理中广泛用于可视化信号特征和进行频谱分析。 柱状图的优点在于其简单易懂,能够直观地展示数据分布。在信号处理中,柱状图可以帮助工程师识别信号中的模式、趋势和异常情况,从而为信号分析和处理提供有价值的见解。 # 2. 柱状图在信号处理中的应用 柱状图在信号处理
recommend-type

hive中 的Metastore

Hive中的Metastore是一个关键的组件,它用于存储和管理Hive中的元数据。这些元数据包括表名、列名、表的数据类型、分区信息、表的存储位置等信息。Hive的查询和分析都需要Metastore来管理和访问这些元数据。 Metastore可以使用不同的后端存储来存储元数据,例如MySQL、PostgreSQL、Oracle等关系型数据库,或者Hadoop分布式文件系统中的HDFS。Metastore还提供了API,使得开发人员可以通过编程方式访问元数据。 Metastore的另一个重要功能是跟踪表的版本和历史。当用户对表进行更改时,Metastore会记录这些更改,并且可以让用户回滚到
recommend-type

JSBSim Reference Manual

JSBSim参考手册,其中包含JSBSim简介,JSBSim配置文件xml的编写语法,编程手册以及一些应用实例等。其中有部分内容还没有写完,估计有生之年很难看到完整版了,但是内容还是很有参考价值的。