可视化平衡树

Visualizing a balanced tree

根据之前的 Whosebug 回答，二叉树是平衡的，当且仅当其两个子树的高度相差不超过一 (Complete binary tree definitions)。

这是否等同于：一棵二叉树是平衡的，当且仅当每条根到叶路径上的边数最多相差一个？

我正在尝试可视化二叉树与非二叉树的外观，并且正在努力思考这个概念。

谢谢。

几乎，除非其中一个子树为空：

*
 \
  *
   \
    *

你引用的定义有点问题，因为空树实际上没有高度，但如果你定义空树的高度为 -1，它就可以工作。上面的树是不平衡的，因为（空的）左子树的高度为 -1 而右子树的高度为 1。但是，您的定义将声明树是平衡的：只有一个根到叶的路径，因此可以与其他此类路径不匹配。

然而，平衡性与二元性仅部分相关。二进制只是意味着没有节点有两个以上的子节点。这是一个平衡的非二叉树的例子：

   *
  /|\
 * * *

但是，树的数量（子节点数量的限制）会影响其平衡性。下面这棵树如果声明为二叉树就是平衡的（只有两棵子树，高度为1和0），如果声明为三叉树就是不平衡的（根的中间有一个子树，而且是空的） :

    *
   / \
  *   *
 /
*

二叉树应该只有每个节点最多有两个孩子。我找到了一个显示不同数据结构的 site（你可以玩它们，它们是动画的）。

如果你对self-balancing树感兴趣，看看AVL树，你就会明白为什么二叉树可以是不平衡的。祝你好运！