让有一棵无向树T，让：T.leaves - 所有的叶子（每个v使得d(v) = 1）。我们知道：|T.leaves|和distance between u and v for each u,v in T.leaves。
换句话说：我们有一棵无向树，我们知道它有多少叶子，以及每两片树叶之间的距离。
我们需要找到how many inside vertices (d(v)>1) are in the tree。
注意：在构建完整的树是不可能的，因为如果我们只有2叶，但它们之间的距离为2^30，这将花费太长时间......
我试图从最短距离开始，怎么算许多顶点都在它们之间，然后添加最接近它们的顶点，但是为此我需要一些公式f（leaves_counted，next_leaf），但是我无法找到那个...
有什么想法吗？找到一棵树，给定它的叶子上的数据
继续在评论中进行讨论。这是如何检查一个特定的（压缩的）边缘，以查看是否可以将新顶点连接到其中间的某个位置，而无需迭代距离。
好了，你需要找到三个号码：l（的附着点在问题边缘的左节点的距离），x（在新的节点从连接点的距离）和r（对称l。）
显然，对于在集L每个节点y（树的左边部分），其对A距离必须从它的距离由相同数量的不同而不同n（让调用它dl whi ch必须等于l + x）。如果情况并非如此，那么这种特殊边缘就没有解决方案。 R中的节点分别为dr和r + x。
如果上述成立，那么你有三个等式：
l + x = dl
r + x = dr
r+l = dist(A,B)
三个方程，三个数字。如果这有一个解决方案，那么你找到了正确的边缘。
在最坏的情况，你需要重复上述的每一个角落，但我认为它可以被优化 - 对L和R的距离检查可能排除进一步搜索树的部分之一。也可以以某种方式获得节点的数量，而不构建树。
我会尽力实施它今天/明天，并回来了解这个答案的反馈。谢谢！ – amit 2011-04-02 06:31:58
@amit gr：请注意，可能有优化的空间。这只是为了展示一个有用的想法，而不是完整的最优算法。 – 2011-04-02 18:50:08
完美地工作，但有一些评论，如果有人在将来尝试它：dist（A，B）= r + l-1（因为有一个单一顶点被计数两次），每一步我们需要添加min {对于树中已经存在的每两个顶点（A，B），x}。这个问题在O（n^3）中以这种方式解决，我相信可以通过优化来找到min {x}小于O（n^2）[以每个顶点的适当添加顺序]。 – amit 2011-04-04 09:13:22
如果您的二叉树具有L叶，那么无论树的形状如何，它都有L-1个内部顶点。
您可以很容易证明这一点：从只有一个节点（根）节点的树开始。然后取任何叶子，并添加两个后代，将叶子转换为内部顶点并添加到树叶。这将删除一个叶节点（旧节点），并添加一个内部节点和两个叶节点，即网络为+1内部节点和+1叶节点。因为你从一个叶子和0个内部节点开始，你总是|离开| = |内部节点| +1 - 这个过程可以产生任何树形状。所有的树木两个形状与4个叶
下面的例子（除了微不足道的左右对称性）：
o o
o L o o
o L L L L L
L L
内部顶点的数量总是3.
它不一定是二叉树。 – amit 2011-04-02 06:31:10
实际上，你可以建立这个树。只保留非分支路径压缩（存储一个边+其长度）并根据需要添加内部节点。因此，两个节点2^31相距仅2个节点加上一个标记为2^31的物理边缘。不知道你是否真的需要*，但你可以。 – 2011-04-01 08:50:01
@Rafal：但是当你试图添加另一个顶点时，你需要检查所有的可能性（除非我错过了某些东西），并且你需要迭代这个距离。 – amit 2011-04-01 08:52:35
gr：不一定，您可以像解析距离一样求解方程。 – 2011-04-01 09:36:29