如果给出了数据的数量，我试图找出可用树的数量。例如）如果有 8 个不同的数据，可以制作多少棵树？
问问题
144 次
1 回答
0
这个问题并不完全清楚。我假设您想要具有恰好 n 个叶子的完整二元（或三元）树的数量（如果您更愿意总共寻找 n 个节点，您将能够从我的结果中找到它；如果您想要可以存储一组给定的n个不同数据的树的数量，即考虑到将数据存储在这样的树中的所有方式，那么您也应该能够轻松获得它）。
让我们考虑完全二叉树的情况。如果你想要 n 个叶子，你可以调用 k 左子树中的叶子数，你会在右边有 nk。这些子树分别有 N(k) 和 N(nk) 种可能性，那么你有N(n)=sum(N(k)*N(n-k), k=1..n-1). N(1)=1。
这是加泰罗尼亚数字的（a？）定义：https ://en.wikipedia.org/wiki/Catalan_number
N(n)=C(n-1)
你可以为三元树做类似的事情
于 2017-04-12T14:41:50.020 回答