c++ - 计算一棵树的高度

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

}

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

score 16 · Accepted Answer

但是后序遍历不正是您正在做的吗？假设 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。

score 4 · Accepted Answer

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

// 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);
//...

如果树有两个节点（根和左或右子节点）调用根节点上的方法将不满足第一个条件（至少一个子树是非空的），它将递归调用两个子节点。其中之一是 null，但它仍然会取消引用 null 指针以执行if.

正确的解决方案是Hans在这里发布的解决方案。无论如何，你必须选择你的方法不变量是什么：要么你允许参数为空的调用并且你优雅地处理它，要么你要求参数是非空的，并保证你不调用带有空指针的方法.

如果您不控制所有入口点（该方法在您的代码中是公共的），则第一种情况更安全，因为您不能保证外部代码不会传递空指针。如果您可以控制所有入口点，则第二种解决方案（将签名更改为引用，并使其成为tree类的成员方法）可能更清晰（或不清晰）。

score 2 · Accepted Answer

树的高度不会随着遍历而改变。它保持不变。它是节点的顺序，根据遍历而变化。

score 2 · Accepted Answer

来自维基百科的定义。

预购（深度优先）：

访问根。

遍历左子树。

遍历右子树。

有序（对称）：

遍历左子树。

访问根。

遍历右子树。

后购：

遍历左子树。

遍历右子树。

访问根。

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

在您的实现中，遍历顺序无关紧要，它会给出相同的结果。如果没有指向您的来源的链接，说明postorder 是更喜欢的，真的不能告诉您更多信息。

score 0 · Accepted Answer

这是答案：

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

c++ - 计算一棵树的高度

5 回答 5

Related

Reference