2

要计算 AVL 树中节点的平衡因子,我们需要找到其左子树的高度和其右子树的高度。然后我们用左子树的高度减去右子树的高度:

balancefactor = leftsubtreeheigh - rightsubtreeheight

我的问题是:如何计算左子树或右子树的高度?

例如,在给定的图1中,根节点 40 的左子树的高度为 4,而 40 的右子树的高度为 2,因此高度差为 2。

我如何在 C++ 中做到这一点?我不想使用递归,因为它非常令人困惑。使用显式堆栈而不是递归更容易理解。


1 该图已从 imgur 服务器中删除。

4

2 回答 2

6

节点的深度比其最深子节点的深度多 1。

您可以通过递归非常简单地做到这一点。

unsigned int depth(node *n)
{
    if (n == NULL)
        return 0;
    else
        return MAX(depth(n->left), depth(n->right)) + 1;
}
于 2009-12-31T19:40:13.607 回答
5

-1, 0, 和+1是 A​​VL 树的三个平衡状态。

平衡因子是left height - right height树的。

于 2012-01-15T04:21:31.403 回答