平衡二叉 20，平衡二叉树是二叉排序树吗？

平衡二叉树不一定是二叉排序树，平衡二叉树是一棵旨在避免二叉排序树高度增长过快而降低二叉排序树性能的树。

首先，平衡二叉树是一种特殊的二元排序树，其节点元素之间存在偏阶关系。 其次，与一般的二叉排序树相比，平衡二叉树左右子树之间的深度差也存在不超过一层的约束，因此平衡树是同一元素序列情况下深度最小的二叉排序树，可以降低二叉树元素搜索的深度，提高平均搜索效率。

应用。 时间复杂度和空间复杂度低于“2-3树”，在一系列操作中始终保持平衡以完成集合，为大型数据库的组织和索引提供了新的途径。

二叉排序树可以是空树，也可以是具有以下属性的二叉树：

1）如果左边的子树不为空，则左边子树上所有节点的值都小于其根节点的值。

2）如果右子树不为空，则右子树中所有节点的值都大于或等于其根节点的值。

3）左子树和右子树也分别是二元排序树。

平衡二叉树。

前提]此树是二叉排序树。

条件]任何节点的左右子树高度差的绝对值不大于1（每个分支节点都必须满足这个条件，顺便说一下，根节点也是一个分支节点） [结论] 那么这个二叉排序树就是一个平衡二叉树。

平衡二叉树的定义是基于二叉排序树，然后是限定条件，所以它必须是二叉排序树。

二叉排序树的每个节点都满足：

左子节点值 此节点值 右子节点的值。

平衡一棵二叉树的前提必须是一棵二叉排序树，并且每个节点的平衡因子绝对值小于2。 更重要的是，二叉排序树的关键字不会重复。

平衡二叉树的定义：

它是一棵空树或左右子树之间高度差的绝对值不超过1，左右子树都是平衡二叉树，同时平衡二叉树必须是二叉搜索树，反之亦然。

问题 1：将升序数组转换为平衡二叉树

对二叉搜索树进行中阶遍历可以得到一个升序数组，然后数组的中值为root，然后将数组分为左子树和右子树，通过继续递归可以得到结果。

问题 2：给出一个二叉树并确定它是否是平衡树

首先编写计算二叉树高度的函数。

树的高度 = max（左子树的高度，右子树的高度）+ 1

得到高度后，可以递归求解每个节点左右子树之间的高度差，如果高度大于1，则返回false