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

admin2018-07-17 23

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

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

学硕统考专业

从五四运动至新中国成立前这一时期，在中国社会经济生活中占优势地位的是()。

关于戊戌变法的历史意义，表述正确的是()①反映了时代的需求和民族精神②唤醒近代中国的民族意识③促进了资产阶级革命的到来④显示了民族资产阶级的弱势

世界天文史上最早实地测量子午线的记录是由谁进行的?()

关于德意志宗教改革的说法不正确的是()

《道威斯计划》的实施所产生的直接结果是()。

最早在中国传播马克思主义的是()。

简述美、苏争霸的三个阶段及特点。

1628年出版了《心血运动论》一书，论证了血液在全身的循环运动，使生理学发展为科学的是()。

加尔文教传播到法国后，其信仰者被称为()。

路面基层完工后应按时浇洒透层油或铺筑下封层，透层油透入深度不小于()。

某公司所进口货物在5月13日(星期四)到达口岸，并于同日填发税费缴纳证，该公司应于何日前缴清税费款?()

在中国境内禁止外汇()。

强光刺眼会引起瞳孔收缩，这是一种()

请选出以下程序的输出结果______。#include＜stdio.h＞sub(x,y,z)intx,y,z；{z=y-x;}main(){inta

Choosethecorrectletter,A,BorC.Bobbychoosesfootballasprojecttopicbecause

WhichofthefollowingEnglishsoundsisNOTbilabial?

计算机408

学硕统考专业

从五四运动至新中国成立前这一时期，在中国社会经济生活中占优势地位的是()。

关于戊戌变法的历史意义，表述正确的是()①反映了时代的需求和民族精神②唤醒近代中国的民族意识③促进了资产阶级革命的到来④显示了民族资产阶级的弱势

世界天文史上最早实地测量子午线的记录是由谁进行的?()

关于德意志宗教改革的说法不正确的是()

《道威斯计划》的实施所产生的直接结果是()。

最早在中国传播马克思主义的是()。

简述美、苏争霸的三个阶段及特点。

1628年出版了《心血运动论》一书，论证了血液在全身的循环运动，使生理学发展为科学的是()。

加尔文教传播到法国后，其信仰者被称为()。

路面基层完工后应按时浇洒透层油或铺筑下封层，透层油透入深度不小于()。

某公司所进口货物在5月13日(星期四)到达口岸，并于同日填发税费缴纳证，该公司应于何日前缴清税费款?()

在中国境内禁止外汇()。

强光刺眼会引起瞳孔收缩，这是一种()

请选出以下程序的输出结果______。#include＜stdio.h＞sub(x,y,z)intx,y,*z；{*z=y-x;}main(){inta

Choosethecorrectletter,A,BorC.Bobbychoosesfootballasprojecttopicbecause

WhichofthefollowingEnglishsoundsisNOTbilabial?

请选出以下程序的输出结果______。#include＜stdio.h＞sub(x,y,z)intx,y,z；{z=y-x;}main(){inta