C++ AVL树中节点的平衡因子
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1986821/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Balance factor of nodes in AVL Tree
提问by Zia ur Rahman
To calculate the balance factor of a node in an AVL tree we need to find the height of its left subtree and the height of its right subtree. Then we subtract the height of right subtree from the height of its left subtree:
要计算 AVL 树中节点的平衡因子，我们需要找到其左子树的高度和右子树的高度。然后我们从左子树的高度减去右子树的高度：
balancefactor = leftsubtreeheigh - rightsubtreeheight
balancefactor = leftsubtreeheigh - rightsubtreeheight
My question is: How do I calculate the height of the left subtree or the right subtree?
我的问题是：如何计算左子树或右子树的高度？
For example in the given figure1the height of the left subtree of the root node 40 is 4 and the height of the right subtree of 40 is 2 so the difference of the heights is 2.
例如在给定的图1 中，根节点 40 的左子树的高度为 4，而 40 的右子树的高度为 2，因此高度差为 2。
How do I do this in C++? I don't want to use recursion because it's very confusing. Using an explicit stack instead of recursion is much more understandable.
我如何在 C++ 中做到这一点？我不想使用递归，因为它很混乱。使用显式堆栈而不是递归更容易理解。
1The figure has been deleted from the imgur servers.
1该图已从imgur 服务器中删除。
回答by R Samuel Klatchko
The depth of a node is 1 more then the depth of it's deepest child.
一个节点的深度比它最深的孩子的深度多 1。
You can do this quite simply with recursion.
你可以很简单地用递归来做到这一点。
unsigned int depth(node *n)
{
if (n == NULL)
return 0;
else
return MAX(depth(n->left), depth(n->right)) + 1;
}
回答by pintu
-1, 0, and +1are the three balance state of an AVL tree.
-1, 0, 和+1是 AVL 树的三个平衡状态。
The balance factor is left height - right heightof the tree.
平衡因子是left height - right height树的。
