查找树的直径

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

在一个定向的，有根的树中，任何一对节点之间总是最多有一条路径，并且任何节点的最长路径总是从根开始。由此可见，diameter仅仅是整个树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; - > return 0; and return max（lheight + rheight + 1，max（ldiameter，rdiameter））; - > return max（lheight + rheight + 2，max（ldiameter，rdiameter））;

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