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

admin2018-07-17 63

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

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://www.kaotiyun.com/show/jfRi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

下列关于古日耳曼人的社会状况的叙述中，不正确的是()。

隋唐时期实行租庸调制，其中“庸”所起的作用是()

第一次提出“毛泽东思想”这一概念的人是()。

洋务派创办军事工业的方式是()。

1951年底到1952年春，中国共产党在党政机构工作人员中开展运动的内容是()。

中国共产党在敌后战场上开创的第一块根据地是()。

改革开放以后，我国农村产业结构巨大的转变表现在()。

论述“二战”后苏联体制表现的主要弊端及其改革。

结合先秦史，如何理解《诗．大雅．板》所云“大邦维屏，大宗维翰”?

发生于结肠的疾病有

Q—CDMA(IS-95)系统工作于()MHz频段。

输卵管外侧端的开口部位在【】

Wegener肉芽肿主要导致

实行终身负责制的工程包括()。

对于个人汽车贷款贷前调查的表述，错误的是()。

399题版MMPI是为()。

1923年6月中共三大的召开标志着国共第一次合作的正式形成。()

利润转化为平均利润的过程，就是

设a＝(1，－1，2)T，β＝(2，1，1)T，A＝αβT，则An＝______．