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

admin2018-07-17 52

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

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

学硕统考专业

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

1901年6月，发表《立宪法议》，首先提出君主立宪要求的是()。

中共中央通过《关于建国以来党的若干历史问题的决议》的会议是()。

在辛亥革命爆发前，孙中山领导中国同盟会发动的武装起义中影响最大的是()。

“七七”事变是中国全面抗战的开始，对此理解最确切的是()。

论述苏联解体的原因及其教训。

赋税是我国古代国家宏观管理经济的重要手段。据此回答问题：哪位皇帝的即位首次应用了秘密立储制?()

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

IsoonrealizedthatIhadenteredanunusualkindofshop.Therewerenogoodsondisplay;therewasnoshopwindow:nothing【C1

渗出液的原因中致葡萄糖降低最明显的是

放置宫内节育器的适应证是

关于在岩溶地区修筑土石坝，下列说法正确的是()。

产品焊接试板的(　　)试验如不合格，允许复验，对不合格的项目取双倍试样进行复验。

简述社会主义荣辱观的主要内容(八荣八耻)。

对2人以上共同实施违反治安管理行为的责任，《治安管理处罚法》规定(　　)。

[*]

Thelawyertriedhardto______betweenlaborandmanagementinthedispute.

计算机408

学硕统考专业

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

1901年6月，发表《立宪法议》，首先提出君主立宪要求的是()。

中共中央通过《关于建国以来党的若干历史问题的决议》的会议是()。

在辛亥革命爆发前，孙中山领导中国同盟会发动的武装起义中影响最大的是()。

“七七”事变是中国全面抗战的开始，对此理解最确切的是()。

论述苏联解体的原因及其教训。

赋税是我国古代国家宏观管理经济的重要手段。据此回答问题：哪位皇帝的即位首次应用了秘密立储制?()

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

IsoonrealizedthatIhadenteredanunusualkindofshop.Therewerenogoodsondisplay;therewasnoshopwindow:nothing【C1

渗出液的原因中致葡萄糖降低最明显的是

放置宫内节育器的适应证是

关于在岩溶地区修筑土石坝，下列说法正确的是()。

产品焊接试板的( )试验如不合格，允许复验，对不合格的项目取双倍试样进行复验。

简述社会主义荣辱观的主要内容(八荣八耻)。

对2人以上共同实施违反治安管理行为的责任，《治安管理处罚法》规定( )。

[*]

Thelawyertriedhardto______betweenlaborandmanagementinthedispute.

产品焊接试板的(　　)试验如不合格，允许复验，对不合格的项目取双倍试样进行复验。

对2人以上共同实施违反治安管理行为的责任，《治安管理处罚法》规定(　　)。