C++ 计算树的高度
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2279147/
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
Calculate height of a tree
提问by Sandeep
I am trying to calculate height of a tree. I am doint with the code written below.
我正在尝试计算树的高度。我不知道下面写的代码。
#include<iostream.h>
struct tree
{
int data;
struct tree * left;
struct tree * right;
};
typedef struct tree tree;
class Tree
{
private:
int n;
int data;
int l,r;
public:
tree * Root;
Tree(int x)
{
n=x;
l=0;
r=0;
Root=NULL;
}
void create();
int height(tree * Height);
};
void Tree::create()
{
//Creting the tree structure
}
int Tree::height(tree * Height)
{
if(Height->left==NULL && Height->right==NULL)
{return 0;
}
else
{
l=height(Height->left);
r=height(Height->right);
if (l>r)
{l=l+1;
return l;
}
else
{
r=r+1;
return r;
}
}
}
int main()
{
Tree A(10);//Initializing 10 node Tree object
A.create();//Creating a 10 node tree
cout<<"The height of tree"<<A.height(A.Root);*/
}
It gives me corret result. But in some posts(googled page) It was suggested to Do a Postorder traversal and use this height method to calculate the Height. Any specific reason?
它给了我正确的结果。但是在某些帖子（谷歌搜索页面）中，建议进行后序遍历并使用此高度方法来计算高度。有什么具体原因吗？
回答by Hans W
But isn't a postorder traversal precisely what you are doing? Assuming left and right are both non-null, you first do height(left), then height(right), and then some processing in the current node. That's postorder traversal according to me.
但是，后序遍历不正是您正在做的吗？假设 left 和 right 都非空，你首先做height(left)，然后height(right)，然后在当前节点中进行一些处理。根据我的说法，这是后序遍历。
But I would write it like this:
但我会这样写：
int Tree::height(tree *node) {
if (!node) return -1;
return 1 + max(height(node->left), height(node->right));
}
Edit: depending on how you define tree height, the base case (for an empty tree) should be 0 or -1.
编辑：根据您定义树高的方式，基本情况（对于空树）应为 0 或 -1。
回答by David Rodríguez - dribeas
The code will fail in trees where at least one of the nodes has only one child:
该代码将在至少一个节点只有一个子节点的树中失败：
// code snippet (space condensed for brevity)
int Tree::height(tree * Height) {
if(Height->left==NULL && Height->right==NULL) { return 0; }
else {
l=height(Height->left);
r=height(Height->right);
//...
If the tree has two nodes (the root and either a left or right child) calling the method on the root will not fulfill the first condition (at least one of the subtrees is non-empty) and it will call recursively on both children. One of them is null, but still it will dereference the null pointer to perform the if.
如果树有两个节点（根和左或右孩子），则在根上调用该方法将不满足第一个条件（至少一个子树非空），它将在两个孩子上递归调用。其中之一为空，但它仍然会取消引用空指针以执行if.
A correct solution is the one posted by Hanshere. At any rate you have to choose what your method invariants are: either you allow calls where the argument is null and you handle that gracefully or else you require the argument to be non-null and guarantee that you do not call the method with null pointers.
正确的解决方案是Hans在这里发布的解决方案。无论如何，您必须选择您的方法不变量是什么：要么允许在参数为空的情况下调用并优雅地处理它，要么要求参数为非空并保证不使用空指针调用该方法.
The first case is safer if you do not control all entry points (the method is public as in your code) since you cannot guarantee that external code will not pass null pointers. The second solution (changing the signature to reference, and making it a member method of the treeclass) could be cleaner (or not) if you can control all entry points.
如果您不控制所有入口点（该方法在您的代码中是公共的），则第一种情况更安全，因为您无法保证外部代码不会传递空指针。tree如果您可以控制所有入口点，则第二种解决方案（将签名更改为引用，并使其成为类的成员方法）可能更清晰（或不清晰）。
回答by marklai
The height of the tree doesn't change with the traversal. It remains constant. It's the sequence of the nodes that change depending on the traversal.
树的高度不会随着遍历而改变。它保持不变。它是根据遍历而改变的节点的顺序。
回答by Mizipzor
Definitions from wikipedia.
来自维基百科的定义。
Preorder (depth-first):
- Visit the root.
- Traverse the left subtree.
- Traverse the right subtree.
Inorder (symmetrical):
- Traverse the left subtree.
- Visit the root.
- Traverse the right subtree.
Postorder:
- Traverse the left subtree.
- Traverse the right subtree.
- Visit the root.
预购（深度优先）：
- 访问根。
- 遍历左子树。
- 遍历右子树。
中序（对称）：
- 遍历左子树。
- 访问根。
- 遍历右子树。
后序：
- 遍历左子树。
- 遍历右子树。
- 访问根。
"Visit" in the definitions means "calculate height of node". Which in your case is either zero (both left and right are null) or 1 + combined height of children.
定义中的“访问”是指“计算节点高度”。在您的情况下，它要么为零（左右均为空）或 1 + 儿童的组合高度。
In your implementation, the traversal order doesn't matter, it would give the same results. Cant really tell you anything more than that without a link to your source stating postorder is to prefer.
在您的实现中，遍历顺序无关紧要，它会给出相同的结果。如果没有指向您的来源的链接，说明 postorder 是更喜欢的，就不能真正告诉您更多信息。
回答by Sdembla
Here is answer :
这是答案：
int Help :: heightTree (node *nodeptr)
{
if (!nodeptr)
return 0;
else
{
return 1 + max (heightTree (nodeptr->left), heightTree (nodeptr->right));
}
}
