c++ - 求一棵树的直径

Question

我已经编写了用于查找二叉树直径的代码。但我无法弄清楚哪里出了问题。我编写的两个函数及其定义如下：-

    int btree::diameteroftree(node* leaf)
    { 
     if (leaf==NULL) 
     return 0;

     int lheight = hieghtoftree(leaf->left);
     int rheight = hieghtoftree(leaf->right);

     int ldiameter = diameteroftree(leaf->left);
     int rdiameter = diameteroftree(leaf->right);

     return max(lheight + rheight + 1,max(ldiameter,rdiameter));
   }


   int btree::hieghtoftree(node* leaf)
   {
    int left=0,right=0;
    if(leaf==NULL)
    return -1;
    else
    {
     left=hieghtoftree(leaf->left);
     right=hieghtoftree(leaf->right);
     if(left > right)
     return left +1;
     else
     return right+1;   
    }
   }

我无法弄清楚我在哪里出错了。谁能告诉我...

Answer 1

您想返回最长路径上的节点数。因此，您的算法中的问题是这一行：

return max(lheight + rheight + 1,max(ldiameter,rdiameter));

在哪里

rootDiameter = lheight + rheight + 1

是从左树最深节点到右树最深节点的路径长度。但是，这个计算是不正确的。单个节点返回高度为 0，因此不会被计算在内。你有两个选择：

1. 更改hieghtoftree以返回最深路径上的节点数，而不是“跳数”
2. 在你的总结中解决这个问题

.

return max(lheight + rheight + 3,max(ldiameter,rdiameter));

Answer 2

在有向根树中，任何一对节点之间总是最多有一条路径，并且到任何节点的最长路径总是从根开始。由此可见，直径就是整棵树的高度height(root)，可以用递归来计算。

height(leaf) = 0
height(node) = max(height(node.left), height(node.right)) + 1

编辑：您在评论中链接到的页面描述了无向树的直径。您需要不同的树表示，例如邻接矩阵。

Answer 3

考虑一个具有根 R 和 2 个叶子 L1、L2 的 3 节点树。然后 heightoftree(L1) == heightoftree(L2) == -1。因此，Diameteroftree(R) 将是 (-1)+(-1)+1 = -1 ?!?

我建议返回-1；--> 返回 0；并返回 max(lheight + rheight + 1,max(ldiameter,rdiameter)); --> return max(lheight + rheight + 2,max(ldiameter,rdiameter));

结果将是路径上的边数。如果您计算节点数，则根据您的需要从最终结果中加一或减一。