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

admin2018-07-17 68

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

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

学硕统考专业

汉章帝会群儒于白虎观，讨论经义，由()写成《白虎通德论》(又称《白虎通义》、《白虎通》)一书，这部书系统地吸收了阴阳五行和谶纬之学，形成今文经学派的主要观点。

元朝在中央设置中书省、地方则设置行中书省，其目的是()。

“文化大革命”结束后，在纠正“文化大革命”错误的过程中，整个过程受到()的严重阻碍。

新石器时代的房屋建筑根据环境的不同形成了不同的类型，()地区多为干栏式建筑。

西周的官僚制度已经相当完备，官僚机构庞杂，职官名目繁多。周王室的官僚机构分为两大系统，分别是()。

1984年，《中共中央关于经济体制改革的决定》中强调，商品经济的充分发展是社会经济发展不可逾越的阶段，市场调节的辅助性作用不可缺少，并指出要有步骤地逐步缩小指令性计划的范围。这表明当时我国()

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

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

以下有关抗结核治疗，说法正确的是

肝、脾损伤后可能发生的主要危险是

建筑工程使用的燃气管用于室内时，应使用以下哪种管材?[2007-059]

(2008)如图6—15所示，已知承压含水层的厚度t=7．5m，用完全井进行抽水试验，在半径r1=6m、r2=24m处，测得相应的水头降落s1=0．76m、s2=0．44m，井的出流量Q=0．01m3／s，则承压含水层的渗流系数k为()m／s[R为

政府采购的所有信息都应当在政府采购监督管理部门指定的媒体上及时向礼会公开发布。()

持有公司5%以上股份的股东属于内幕信息的知情人。（）

政府债券具有安全性高、流通性强、收益稳定和享受免税待遇的特点。(　　)

视觉上对彩色的感觉有三个特征，反映人眼所感到的明亮程度的叫(156)；反映颜色种类的特征叫(157)，反映颜色深浅程度的叫(158)，二者有时通称为(159)。彩数(color　depth)是指(160)，其单位为bpp。

Thedancersfortheballetwereselectedforsimilarityofheightandbuildsothattheymightpresenta(an)______appearance.

Betteraccesstohealthcaredatahelpslocalgovernmentsimprovepreventivehealthpoliciesaimedatreducingoverallmedicalc

计算机408

学硕统考专业

汉章帝会群儒于白虎观，讨论经义，由()写成《白虎通德论》(又称《白虎通义》、《白虎通》)一书，这部书系统地吸收了阴阳五行和谶纬之学，形成今文经学派的主要观点。

元朝在中央设置中书省、地方则设置行中书省，其目的是()。

“文化大革命”结束后，在纠正“文化大革命”错误的过程中，整个过程受到()的严重阻碍。

新石器时代的房屋建筑根据环境的不同形成了不同的类型，()地区多为干栏式建筑。

西周的官僚制度已经相当完备，官僚机构庞杂，职官名目繁多。周王室的官僚机构分为两大系统，分别是()。

1984年，《中共中央关于经济体制改革的决定》中强调，商品经济的充分发展是社会经济发展不可逾越的阶段，市场调节的辅助性作用不可缺少，并指出要有步骤地逐步缩小指令性计划的范围。这表明当时我国()

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

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

以下有关抗结核治疗，说法正确的是

肝、脾损伤后可能发生的主要危险是

建筑工程使用的燃气管用于室内时，应使用以下哪种管材?[2007-059]

(2008)如图6—15所示，已知承压含水层的厚度t=7．5m，用完全井进行抽水试验，在半径r1=6m、r2=24m处，测得相应的水头降落s1=0．76m、s2=0．44m，井的出流量Q=0．01m3／s，则承压含水层的渗流系数k为()m／s[R为

政府采购的所有信息都应当在政府采购监督管理部门指定的媒体上及时向礼会公开发布。()

持有公司5%以上股份的股东属于内幕信息的知情人。（）

政府债券具有安全性高、流通性强、收益稳定和享受免税待遇的特点。( )

视觉上对彩色的感觉有三个特征，反映人眼所感到的明亮程度的叫(156)；反映颜色种类的特征叫(157)，反映颜色深浅程度的叫(158)，二者有时通称为(159)。彩数(color depth)是指(160)，其单位为bpp。

Thedancersfortheballetwereselectedforsimilarityofheightandbuildsothattheymightpresenta(an)______appearance.

Betteraccesstohealthcaredatahelpslocalgovernmentsimprovepreventivehealthpoliciesaimedatreducingoverallmedicalc

政府债券具有安全性高、流通性强、收益稳定和享受免税待遇的特点。(　　)

视觉上对彩色的感觉有三个特征，反映人眼所感到的明亮程度的叫(156)；反映颜色种类的特征叫(157)，反映颜色深浅程度的叫(158)，二者有时通称为(159)。彩数(color　depth)是指(160)，其单位为bpp。