递归创建具有二项式系数的树

Question

我正在尝试用整数递归填充树（如下面的 link 所示）。但是我不明白如何使用递归解决归纳步骤。

PS。我已经创建了递归函数来计算二项式系数

提前致谢！

Answer 1

说明递归步骤的伪代码

TreeNode getRootOfSomeFancyTree(n)
    TreeNode root = new TreeNode()
    if(n == 1) return root
    else for(i = 0; i < n; i++)
        //not sure of correct way to multiply an integer by a tree in your application
        int x = binomialCoefficient(n, i) * i
        //anyway, recurring is easy and safe provided x < n
        TreeNode subTree = getRootOfSomeFancyTree(x)
        //build the tree
        root.addChild(subTree)
    endfor return root

Answer 2

link 图片中的数学符号有点晦涩。但是您想几乎完全实现它。它是这样说的：

Node buildTree(n) {
  Let tree be a new Node (with no children)
  For i from 0 to n - 1
    Let b = binomial(n, i)
    for b times:
      Add buildTree(i) as a child of tree
  return tree
}

晦涩的部分是，在这个“树数学”中乘以某个整数 k 意味着“将图重复 k 次”，而求和意味着“将所有作为子节点添加”到隐式父节点。这个父级是表达式的值。

这里有一个开发提示。在每个节点中存储一个唯一的整数作为标签。一旦你开始工作，然后编写一个打印出 DOT 语言的小树步行器。当我为 n=3 这样做时，我得到：

graph {
0 -- 1
2 -- 3
0 -- 2
4 -- 5
0 -- 4
6 -- 7
0 -- 6
8 -- 9
10 -- 11
8 -- 10
12 -- 13
8 -- 12
0 -- 8
14 -- 15
16 -- 17
14 -- 16
18 -- 19
14 -- 18
0 -- 14
20 -- 21
22 -- 23
20 -- 22
24 -- 25
20 -- 24
0 -- 20
}

您可以使用在线 GraphViz 查看它的外观 here。

递归创建具有二项式系数的树

Recursively creating a tree with binomial coefficient

java

tree

recursion