2

我试图找出一个函数 f(x) 来计算 k-ary 树中的叶子数。例如，假设我们创建了一个以根 4 开头的树，有 3 个子节点，每个子节点分别为 -1、-2、-3。我们的叶子只会是 0 值，而不是空值。在过去的一天里，我一直在试图找出一个函数，但似乎我所做的一切都没有朝着正确的方向发展。

前任：

              4
         /    |     \
        3     2      1
     /  |\   /|     /  
    2   1 0 1 0    0  
   /|  /   /
  1 0 0   0
 /
0

7片叶子。

任何帮助将不胜感激！谢谢！

为了澄清，我需要一个数学方程，如果我递归遍历树，它会得出与代码相同的答案。

更多示例：{4,7}{5,13}{6,24}{7,44}{8,81}{9,149}{10,274}{11,504}{12,927}{13,1705}{14,3136} {15,5768}{16,10609}{17,19513}{18,35890}{19,66012}{20,121415}

 public int numleaves(TreeNode node) {
    if (node == null)
        return 0; 
    else if (node.getLeft() == null && node.getMiddle() == null && node.getRight() == null)
        return 1; 
    else
        return numleaves(node.getLeft()) + numleaves(node.getMiddle()) + numleaves(node.getRight());
}
4

4 回答 4

2

我无法回答你的问题，但它有一个解决方案。我只能概述孩子数量k等于 的情况2。该案例k=3导致具有两个复数和一个实数解的三次多项式，我在这里缺乏以非数值方式推导它们的工具。

但是让我们看看这个案例k=2。有趣的是，这个问题与斐波那契数密切相关，只是边界条件不同。

写下递归公式很容易：

a(n) = a(n-1) + a(n-2)

有边界条件a(1)=1和a(0)=1。它的特征多项式是

x^2 = x + 1

与解决方案x1 = 1/2 + sqrt(5)/2和x2 = 1/2 - sqrt(5)/2。代表着

a(n) = u*x1^n + v*x2^n

对于某些人来说u，andv是我们正在寻找的序列的显式公式。放入我们得到的边界条件

u = (sqrt(5)+1)/(2*sqrt(5))
v = (sqrt(5)-1)/(2*sqrt(5))

IE

a(n) = (sqrt(5)+1)/(2*sqrt(5))*(1/2 + sqrt(5)/2)^n + (sqrt(5)-1)/(2*sqrt(5))*(1/2 - sqrt(5)/2)^n

为k=2.

于 2013-11-04T19:55:58.373 回答
1

您的代码似乎正在计算具有起始值和的Tribonacci 序列。这是来自整数序列在线百科全书的序列 A000073，从该序列的第三个条目而不是第一个条目开始。百科全书页面的评论部分给出了一个明确的公式：由于这是具有 3 次特征多项式的线性递推关系，因此就该多项式的根而言，存在一个封闭形式的解。下面是一小段 Python 2 代码，它基于产生前几个值的给定公式。（请参阅下面的编辑以进行简化。）112

from math import sqrt

c = (1 + (19 - 3 * sqrt(33))**(1/3.) + (19 + 3 * sqrt(33))**(1/3.)) / 3.
m = (1 - c) / 2
p = sqrt(((3*c - 5)*(c+1)/4))
j = 1/((c-m)**2 + p**2)
b = (c - m) / (2 * p*((c - m)**2 + p**2))
k = complex(-j / 2, b)
r1 = complex(m, p)

def f(n):
    return int(round(j*c**(n+2) + (2*k*r1**(n+2)).real))

for n in range(0, 21):
    print n, f(n)

和输出：

0 1
1 1
2 2
3 4
4 7
5 13
6 24
7 44
8 81
9 149
10 274
11 504
12 927
13 1705
14 3136
15 5768
16 10609
17 19513
18 35890
19 66012
20 121415

编辑：上面的代码是不必要的复杂。通过该运算，可以省略roundin 中的第二项（它随着增加而收敛到零），并且可以简化第一项的公式。这是一些生成相同输出的更简单的代码。f(n)n

s = (19 + 297**0.5)**(1/3.)
c = (1 + s + 4/s)/3
j = 3 - (2 + 1/c)/c
for n in range(0, 32):
    print n, int(round(c**n / j))
于 2013-11-04T21:08:19.370 回答
0

我情不自禁，但我在其中看到了二叉树。http://en.wikipedia.org/wiki/Binomial_heap

我认为好的近似值可能是第 k 行帕斯卡三角形的总和，其中 k 代表根节点的数量。

于 2013-11-04T19:16:40.967 回答
0

这不是更容易理解吗：

我们将 tribonacci 序列的起始值设置为一个名为 result 的列表。然后我们将这些值放入 3 个变量中。我们根据 tribonacci 公式更改变量内容（新 a 是 a+b+c，新 b 是旧 a，新 c 是旧 b）。然后我们计算我们想要达到的任何 tribonacci 数，并将每个结果存储到我们的结果列表中。最后，我们读出了索引列表。

result=[1,1,2]
a,b,c=result[-1],result[-2],result[-3]
for i in range(40):
    a,b,c=a+b+c,a,b
    result.append(a)
for e,f in enumerate(result):
    print e,f
于 2018-12-10T05:03:31.267 回答