计算一棵树的高度

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

}

我得到了正确的结果。

但在一些帖子（谷歌页面）中建议进行后序遍历，并使用此高度方法来计算高度。有特定的原因吗？

- Sandeep

---

提示：代码必须至少缩进4个空格，否则板子无法识别它为代码。 - Matteo Italia

你能否发布该页面的链接？ - dirkgently

啊，我花了几分钟的时间试图找出代码哪里出了问题。然后我看到了问题的结尾，发现了“它给了我正确的结果”的备注。> . < - Mizipzor

@Sandeep：我刚刚为你修复了缩进/格式。你的编辑撤销了整个更改。请确保保留有用的编辑。 - dirkgently

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。

- Hans W

---

那么你认为如果我改变顺序，先计算右子树高度再计算左子树高度（递归），结果会不同吗？ - Sandeep

@Sandeep：改变顺序不会改变结果。改变空节点高度的定义会改变结果。 - Mizipzor

Steve314：在递归调用之前，我的函数要做什么工作？ - Hans W

@Hans - 它检查它是否在实际节点上，或者你只是递归到了一个空指针。我认为这是否真的遍历了可能节点还有争议，因为它只看指针，而不是它指向的内容，但对于我来说，进入递归调用就是进入下一个节点的步骤，因此嵌套调用之前的任何代码都是对该节点进行遍历。如果我感到非常追求严谨，我甚至会包括读取子节点指针，这显然必须首先完成，以便将其作为参数传递给嵌套调用。 - user180247

@Hans - 当我考虑遍历时，通常会使用某种迭代器类，因此当“next”方法退出并引用节点状态时，该节点就会被“遍历”。这基本上是访问者模式中抽象的分离。对于简单的递归遍历，这种分离是不存在的，但我想我有点奇怪。 - user180247

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。

正确的解决方案是由Hans在此处发布的解决方案。在任何情况下，您都必须选择您的方法不变量：要么允许参数为空的调用并优雅地处理该参数，否则要求参数为非空，并保证您不使用null指针调用该方法。

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

- David Rodríguez - dribeas

---

David，我用3、4、5、6、7进行了测试，结果为4。你认为问题出在哪里？ - Sandeep

假设您有两个节点，Root和右侧的一个节点。您在Root中调用高度，因为right不为空，它进入else分支，该分支将调用l=height(Height->left);。该递归调用接收到一个空指针，并尝试在if语句中对其进行解引用以检查Height->left是否为空。解引用空指针（递归调用中的Height为空）会产生未定义的行为，在大多数情况下会导致应用程序崩溃。 - David Rodríguez - dribeas

Answer 3

树的高度在遍历过程中不会改变，保持不变。而遍历顺序则根据不同的遍历方式而改变。

- marklai

Answer 4

来自维基百科的定义。

前序遍历（深度优先）：

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

中序遍历（对称）：

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

后序遍历：

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

在这些定义中，“访问”意味着“计算节点的高度”。在您的情况下，节点的高度为零（左右子树都为空）或者是1+子节点高度的总和。

在您的实现中，遍历顺序并不重要，它会给出相同的结果。除非有一个指向您的源代码的链接表明后序遍历更好，否则不能告诉您更多信息。

- Mizipzor

---

我看不出使用这种后序遍历的具体原因。也许用户只是认为后序遍历是默认值，如果不确定的话？或者他觉得“进行遍历”太模糊了？ - Mizipzor

Answer 5

这里是答案：

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

- Sdembla