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

admin2018-07-17 42

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

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

学硕统考专业

《四库全书》编成后，纪昀等又写成()200卷，把每本书的渊源、版本、内容都作了提纲性的介绍，是一部重要的目录学著作。

西南军阀跟随孙中山拥护护法运动的目的是()。

下列关于国际联盟及其活动的叙述，正确的是()。

毛泽东明确提出“中国革命斗争的胜利要靠中国同志了解中国情况”论断的著作是()。

巴黎和会上，英美主张把原德国在山东的权利转让给日本，华盛顿会议又表示支持中国让日本归还山东的要求，英美态度发生变化的根本原因是()。

“一战”后，协约国与奥地利签订的确认奥匈帝国解体的文件是()。

年鉴学派开创了总体史研究方法，其代表人物马克·布洛赫研究中世纪的代表作是()

尚书一职，秦置于宫禁；西汉沿置，为皇帝收发文书，传达记录诏命章奏；东汉置尚书台，“出纳王命，赋政四海，权尊势重”，成为朝廷的政务中心。这一过程反映了()

某定点机字长8位(含1位符号位)，现该机中一个寄存器的内容为43H，则将其算术左移一位、算术右移一位的结果分别为()。

在下图的网络配置中，总共有()个广播域、()个冲突域。

Java中定义常量的保留字是（）。

级别是反映公务员哪些方面的综合标志?

患者男，27岁。急起烦躁不安，口干、脸红2个小时入院。体查：患者神志模糊，瞳孔缩小，对光反射存在，双前臂可见很多注射瘢痕。仔细追问病史，发现患者既往有吸食海洛因的病史。对此患者目前的处理正确的是

在起重作业中，（）斜拉、斜吊和起吊地下埋设或凝结在地面上的重物。

当采用碳素钢丝、钢绞线及热处理钢筋作预应力结构时，混凝土的强度等级不应低于()。

国际航空运输中，国际航班的国内段只能适用国内航空法，不能适用华沙体制。()

我国法的制定的基本原则之一是()。