我正在尝试计算树的高度。我不知道下面写的代码。
#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);*/
}
它给了我正确的结果。
但是在 some posts (googled page) 中建议做一个后序遍历并使用这种高度方法来计算高度。有什么具体原因吗?
最佳答案
但是,后序遍历不正是您正在做的吗?假设 left 和 right 都非空,您首先执行 height(left)
,然后 height(right)
,然后在当前节点中进行一些处理。根据我的说法,这是后序遍历。
但我会这样写:
int Tree::height(tree *node) {
if (!node) return -1;
return 1 + max(height(node->left), height(node->right));
}
编辑:根据您定义树高的方式,基本情况(对于空树)应为 0 或 -1。
关于c++ - 计算树的高度,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/2279147/