-
21-09-2019 - |
题
我正在尝试计算一棵树的高度。我不喜欢下面写的代码。
#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);*/
}
它给了我正确的结果。但在 一些帖子(谷歌页面)建议进行后序遍历并使用此高度方法来计算高度。有什么具体原因吗?
解决方案
但不是后序遍历正是你在做什么?假设左右都是非空,你先做height(left)
,然后height(right)
,然后一些处理当前节点。这是根据我的后序遍历。
不过,我会写这样的:
int Tree::height(tree *node) {
if (!node) return -1;
return 1 + max(height(node->left), height(node->right));
}
编辑:取决于你如何定义树高,基体的情况下(对于空树)应为0或-1
。其他提示
该代码将在树失败其中节点中的至少一个只有一个子:
// 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
。
一个正确的解决方案是一个张贴由汉斯此处。无论如何你要选择什么样的方法不变量:要么你允许调用其中的参数为空,你处理的是优雅的,否则你所需要的参数为非空和你不来电与空指针的方法保证
在第一种情况下是安全的,如果你不控制所有入口点(该方法是公开在你的代码),因为你不能保证外部代码将无法通过空指针。第二种解决方案(改变签名参考,并使其成为tree
类的成员方法)可以是清洁器(或不)如果可以控制所有入口点。
树的高度不与遍历改变。它保持不变。它是变化取决于遍历的节点的顺序。
定义来自 维基百科.
预购(深度优先):
- 访根。
- 遍历左子树。
- 遍历右子树。
中序(对称):
- 遍历左子树。
- 访根。
- 遍历右子树。
邮购:
- 遍历左子树。
- 遍历右子树。
- 访根。
定义中的“访问”意味着“计算节点的高度”。在您的情况下,它要么为零(左侧和右侧均为空),要么为 1 + 孩子的组合高度。
在您的实现中,遍历顺序并不重要,它会给出相同的结果。如果没有指向您的来源的链接,表明后序是更喜欢的,我真的不能告诉您更多的事情。
下面是答案:
int Help :: heightTree (node *nodeptr)
{
if (!nodeptr)
return 0;
else
{
return 1 + max (heightTree (nodeptr->left), heightTree (nodeptr->right));
}
}
不隶属于 StackOverflow