AVL树中节点的平衡因子

Question

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

balancefactor = leftsubtreeheigh - rightsubtreeheight

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

例如,在给定的图^_1中,根节点40的左子树的高度是4,右子树的高度40是2,因此高度的差是2.

我如何在C++中执行此操作？我不想使用递归,因为它非常令人困惑.使用显式堆栈而不是递归更容易理解.

---

^₁ 该图已从imgur服务器中删除.

Answer 1

节点的深度比它最深的孩子的深度多1倍.

您可以通过递归非常简单地完成此操作.

unsigned int depth(node *n)
{
    if (n == NULL)
        return 0;
    else
        return MAX(depth(n->left), depth(n->right)) + 1;
}

Answer 2

-1,, 0和+1是AVL树的三种平衡状态.

平衡因子是left height - right height树.