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

admin2018-07-17 48

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

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

学硕统考专业

中国共产党在过渡时期总路线的主要内容是“一化三改造”，其中“一化”是指()。

明朝后期，与中国发生联系的欧洲殖民者不包括()。

16世纪英国国王推行宗教改革的根本目的是()

开皇五年，文帝规定每年正月五日县令出查，令百姓五党三党为一团，根据标准定户等上下，从轻制定税额，并将各户应纳税额写成定簿，是为()。

1543年发表解剖学专著《人体结构论》的是()。

火的使用，是人类在征服自然的进程中所取得的伟大成果。人类开始使用天然火是在()。

周王室的两大官僚系统是()。

现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(el，e2，…，em)；i=1；while(所剩边数>=顶点数){从图中删去ei；若图不再连通。则恢复ei；i=

下图中的顶点表示村庄，有向边代表交通路线，若要建立一家医院，试问建在哪一个村庄能使各村庄总体交通代价最小?

治疗血瘀证，常酌配补气、行气药物，其机理是

应用染色体易位技术辅助NHL分型，下列选项中，错误的是

未经细菌侵入的创口属于虽然细菌侵入，但未引起化脓性炎症的创口属于

施工企业进行施工组织、成本管理、经济核算和投标报价的重要依据是()

对于不动产和股权类的抵债资产，商业银行应当自取得之日起()内予以处置。

固定制造费用的能量差异是()。

你是学生会的成员．学校让你调查本校学生当家教的情况，你怎么保证调查的真实性和有效性?

半导体是导电性能介于金属和绝缘体之间的物质。按这个定义，下面说法错误的是()。

Theswingingsinglelifestyleofthestereotypeismostpossibleforurban,educatedprofessionalandtechnicalpeople.Onlythe