计算树的高度

Question

我正在尝试计算一棵树的高度。我不喜欢下面写的代码。

#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);*/

}

它给了我正确的结果。但在 一些帖子（谷歌页面）建议进行后序遍历并使用此高度方法来计算高度。有什么具体原因吗？

Answer 1

但不是后序遍历正是你在做什么？假设左右都是非空，你先做height(left)，然后height(right)，然后一些处理当前节点。这是根据我的后序遍历。

不过，我会写这样的：

int Tree::height(tree *node) {
    if (!node) return -1;

    return 1 + max(height(node->left), height(node->right));
}

编辑：取决于你如何定义树高，基体的情况下（对于空树）应为0或-1

。

Answer 2

该代码将在树失败其中节点中的至少一个只有一个子：

// 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类的成员方法）可以是清洁器（或不）如果可以控制所有入口点。

Answer 3

树的高度不与遍历改变。它保持不变。它是变化取决于遍历的节点的顺序。

Answer 4

定义来自 维基百科.

预购（深度优先）：

1. 访根。
2. 遍历左子树。
3. 遍历右子树。

中序（对称）：

1. 遍历左子树。
2. 访根。
3. 遍历右子树。

邮购：

1. 遍历左子树。
2. 遍历右子树。
3. 访根。

定义中的“访问”意味着“计算节点的高度”。在您的情况下，它要么为零（左侧和右侧均为空），要么为 1 + 孩子的组合高度。

在您的实现中，遍历顺序并不重要，它会给出相同的结果。如果没有指向您的来源的链接，表明后序是更喜欢的，我真的不能告诉您更多的事情。

Answer 5

下面是答案：

int Help :: heightTree (node *nodeptr)
{
    if (!nodeptr)
        return 0;
    else
    {
        return 1 + max (heightTree (nodeptr->left), heightTree (nodeptr->right));
    }
}