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

admin2018-07-17 33

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

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://jikaoti.com/ti/WhfjFFFM

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

中国共产党召开七届二中全会的主要目的是()。

中国共产党在民主革命时期的不同阶段实行了不同的土地政策，其主要的根据是()。

对西欧封建社会的说法不正确的是()。

张居正改革期间，调任抗倭名将()镇守蓟门，对安定北方发挥了积极作用。

1925年10月签订《洛迦诺公约》后，法国外长白里安认为：“我国的安全比以往任何时候都更有保障了。”对此说法不正确的一项是()。

把变量引进数学。使解析几何成为数学发展史上转折点的科学家是()。

公元9～13世纪是西欧封建庄园的兴盛时期，典型的庄园采用()的剥削方式。

我国历史上一次有周密计划、经过长期准备并利用宗教形式组织和发动的农民起义是（）。

______abigholeontheroad,thecarwasstopped.

A、黄体囊肿B、多囊卵巢C、黄素囊肿D、浆液性囊腺瘤E、巧克力囊肿与痛经有关的病变是

橡胶产品中，属于特种橡胶的有()。

局域网的拓扑结构主要包括（）。

在世界范围内，严格意义上的学校教育系统基本形成于()

Abilingualpersonissomeonewhospeakstwolanguages.Apersonwhospeaksmorethantwolanguagesiscalled"multilingual"(al

1903年6月，在上海《苏报》发表《驳康有为论革命书》，批驳康有为所谓“中国之可立宪，不可革命”的谬论的资产阶级革命家是（）。

如图1所示，某校园网使用10Gbps的POS技术与CERNET相连，POS接口的帧格式使用SDH。路由协议的选择方案是校园网采用OSPF动态路由协议，校园网与CERNET的连接使用静态路由协议。另外，还要求在路由器R3上配置一个loopback接口，接口的

Paula:Thefutureisdeterminedbytheactionsofthepresentday.Theresponsibilitywehaveforthefuturebeginswhenwe