什么是平衡二叉树，它与完整的二叉树有何不同？

Question

你能给我解释一下什么是平衡二叉树吗？我看了很多解释还是没明白。完全二叉树是平衡二叉树吗？

根据维基百科：

A balanced binary tree has the minimum possible maximum height (a.k.a. depth) for the leaf nodes, because for any given number of leaf nodes the leaf nodes are placed at the greatest height possible.[clarification needed]

但是我还是不明白这个定义，你能给我解释一下什么是平衡二叉树并给我一些例子吗

Answer 1

A balanced binary tree is one where every leaf is no more than a certain amount further from the root than every other leaf node. For example, an AVL tree 是一棵平衡二叉搜索树，其中：

它的左右子树是平衡的
每个节点的左右子树深度差不超过1

下面是一棵AVL树：

就您最初的问题而言，是的，complete binary tree 是一棵平衡二叉树，但反之则不然。完全二叉树是一棵二叉树，其中除了可能的最后一层外，每一层都被完全填充，并且所有节点都尽可能地靠左。再举个例子：

       r
     /   \
    a     b
   / \   / 
  c   d e

什么是平衡二叉树，它与完整的二叉树有何不同？

what is a balanced binary tree and how does it differ than a complete one?

binary-tree