已知一棵二叉树采用二叉链表存储，结点构造为 root指向根结点。请编写算法判断该二叉树是否是平衡二叉树，即二叉树中任意结点的左右子树的深度相差不超过1，例如下图所示的二叉树就是一棵平衡二叉树。要求：给出算法的基本设计思想。

admin2018-07-17 27

问题已知一棵二叉树采用二叉链表存储，结点构造为

root指向根结点。请编写算法判断该二叉树是否是平衡二叉树，即二叉树中任意结点的左右子树的深度相差不超过1，例如下图所示的二叉树就是一棵平衡二叉树。

要求：
给出算法的基本设计思想。

选项

答案基本的基本设计思想：设置二叉树的平衡标记balance，以标记返回二叉树bt是否为平衡二叉树，若为平衡二叉树，则返回1，否则返回0；h为二叉树bt的高度。采用前序遍历的递归算法： ①若bt为空，则高度为0，balance=1。 ②若bt仅有根结点，则高度为1，balance=1。 ③否则，对bt的左、右子树执行递归运算，返回左、右子树的高度和平衡标记，bt的高度为最高子树的高度加1。若左、右子树的高度差大于1，则balance=0；若左、右子树的高度差小于 1，且左、右子树都平衡时，balance=1，否则balance=0。

解析

转载请注明原文地址:https://kaotiyun.com/show/jfRi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

以下关于阿兹特克文化的叙述，不正确的是()。

在欧盟发展历史上，促使欧盟正式成立的文件是()。

改革开放以后，我国农村产业结构巨大的转变表现在()。

材料一从波罗的海斯德丁(什切青)到亚得里亚海边的里亚斯特，一幅横贯欧洲大陆的铁幕已经降落下来……无一不处在苏联的势力范围之内。

利玛窦与徐光启合作翻译的()，介绍了曾经流行于欧洲的欧几里得平面几何的系统理论，大大地丰富了中国古代几何学的内容。

有一个仓库，可以存放A和B两种产品，但要求：(1)每次只能存入一种产品(A或B)；(2)-N＜A产品的数量-B产品的数量＜M。其中，N和M是正整数。试用P，V操作描述产品A与产品B的入库过程。

已知4位有效信息为1010，试根据下列要求进行编码。(1)按配偶原则将其编码为扩展的海明码，要求能发现两位错并纠正一位错。(2)将其编码为循环冗余校验码，生成多项式G(x)=1011。

给定单链表的结点结构typedefstructnode*link；structnode{intitem，linknext；)；将两个升序单链表归并为一个升序单链表。

在网络中计算机接收的信号是()。

IEEE754标准规定的64位浮点数格式中，符号位为1位，阶码为11位，尾数为52位。则它所能表示的最小规格化负数为()。

关于流行性脑脊髓膜炎预后的描述，正确的是

下列不属于直接引入法造影的是

关于感光效应与管电压的关系，正确的叙述是

下列哪条叙述是错误的

下列关于承诺的说法中，不正确的是()。

[1997年第092题，1995年第113题]高层建筑物内的观众厅、展览厅、餐厅、商场营业厅等，由厅内任何一点至最近的疏散出口直线距离，下列哪条是正确的?

某建材超市允许个人购买建材时分12个月付清款项，这种做法对应的信用形式为()。

城市社区建设的基本原则是()。

姜某使用伪造、变造的金融票据，在签订履行合同的过程中，骗取对方当事人的信任，并骗得其财物，数额较大。下述关于对姜某行为认定的表述不正确的是()。