2. 考研
  3. 已知一棵二叉树采用二叉链表存储，结点构造为 root指向根结点。请编写算法判断该二叉树是否是平衡二叉树，即二叉树中任意结点的左右子树的深度相差不超过1，例如下图所示的二叉树就是一棵平衡二叉树。 要求： 根据设计思想，采用C或C++语言描述算法，关键之

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

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

root指向根结点。请编写算法判断该二叉树是否是平衡二叉树，即二叉树中任意结点的左右子树的深度相差不超过1，例如下图所示的二叉树就是一棵平衡二叉树。

要求：
根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
选项
答案算法的实现加下： void Judge_AVL(BjiTree bt，int &balance，int&h){ int bl，br，hl，hr； ／／左、右子树的平衡标记和高度 if，(bt==NULL){ ／／空树，高度为0 h=0， balance=1； } else if(p—>ichild==NULL&&p—>rchild==NULL){／／仅有根结点，则高度为1 h=1； balance=1； } else{ Judge_AVL(bt—>lchild，bl，hi)； ／／递归判断左子树 Judge_AVL(bt—>rchild，br，hr)， ／／递归判断右子树 h=(hl＞hr?hl：hr)+1， if(abs(hl，hr)＜2) ／／若高度绝对值小于2，则看左、右子树是否都平衡 balance=bl&br； ／／&为逻辑与，即左、右子树都平衡时，二叉树平衡 else balance=0； } }
解析
转载请注明原文地址:https://www.kaotiyun.com/show/kfRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)