要计算 AVL 树中节点的平衡因子,我们需要找到其左子树的高度和右子树的高度。然后我们用它的左子树的高度减去右子树的高度:
balancefactor = leftsubtreeheigh - rightsubtreeheight
我的问题是:如何计算左子树或右子树的高度?
例如在给定的图中1根节点40的左子树的高度是4,40的右子树的高度是2所以高度差为 2。
我如何在 C++ 中执行此操作?我不想使用递归,因为它很困惑。使用显式堆栈而不是递归更容易理解。
1 该图已从 imgur 服务器中删除。
最佳答案
节点的深度比它最深的子节点的深度多 1。
您可以通过递归非常简单地做到这一点。
unsigned int depth(node *n)
{
if (n == NULL)
return 0;
else
return MAX(depth(n->left), depth(n->right)) + 1;
}
关于c++ - AVL树中节点的平衡因子,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1986821/