AVL Tree节点平衡因子

Question

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

balancefactor = leftsubtreeheigh - rightsubtreeheight

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

例如，在给定的图中^₁，根节点 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树的三种平衡状态。

平衡因子是树的左高-右高。