可视化一棵平衡的树 [英] Visualizing a balanced tree

问题描述

根据先前的StackOverflow答案，如果二叉树的两个子树的高度绝不会相差一个以上，则二叉树是平衡的(

According to a previous StackOverflow answer, a binary tree is balanced iff the heights of its two subtrees never differ by more than one (Complete binary tree definitions).

这是否等于说:如果每个根到叶路径上的边数最多相差一个，则二叉树是平衡的?

Is this the same as saying: a binary tree is balanced iff the number of edges on every root-to-leaf path at most differs by one?

我试图形象化二叉树与非二叉树的模样，并为将概念包裹住头而苦苦挣扎.

I'm trying to visualize what a binary tree vs. a non-binary tree looks like, and am struggling with wrapping my head around the concept.

谢谢.

推荐答案

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

Almost, except if one of the subtrees are empty:

*
 \
  *
   \
    *

您引用的定义有点问题，因为空树实际上没有高度，但是如果您将空树定义为高度-1，它就可以工作.上面的树是不平衡的，因为(空)左子树的高度为-1，右子树的高度为1.但是，您的定义将声明该树为平衡的:只有一条从根到叶的路径，因此可以不会与其他此类路径不匹配.

The definition you cite is a little problematic because an empty tree doesn't really have a height, but it works if you define empty trees to have height -1. The above tree is unbalanced, since the (empty) left subtree has height -1 and the right subtree has height 1. However, your definition would declare the tree to be balanced: there's only one root-to-leaf path, so there can't be any mismatch with other such paths.

但是，平衡仅与二进制具有部分关系.二进制只是意味着没有一个节点有两个以上的子节点.这是一个平衡的非二叉树的示例:

However, balancedness is only partially related to binary-ness. Being binary simply means that no node has more than two children. Here's an example of a non-binary tree that is balanced:

   *
  /|\
 * * *

但是，树的稀疏度(子节点数的限制)会影响其平衡性.如果您声明下面的树为二叉树(只有两个高度为1和0的子树)，则下面的树是平衡的；如果声明为三元树，则下面的树为不平衡的(根的中间有一个子树，并且为空) :

However, the arity (the limit on the number of child nodes) of a tree can affect its balancedness. The following tree is balanced if you declare it to be binary (there are only two subtrees, of height 1 and 0), and unbalanced if you declare it to be ternary (there is a middle subtree of the root, and it is empty):

    *
   / \
  *   *
 /
*

这篇关于可视化一棵平衡的树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！