由N个节点可以构成多少种二叉树-卡特兰数

孙泽辉

发布于：2021年8月31日

字数：469字

时长：2分钟

次浏览

卡特兰数是组合数学中一种常出现于各种计数问题中的数列。

做题时遇到一题：由四个节点可以构成多少种不同的二叉树？

用手全画出来也太low了点了，百度说用卡特兰数解决，厉害了！

卡特兰数的前几项（从零开始）：

1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790…

书上的题答案给的是14，这不就是在这个数列的第4项吗，然后我手算其他的三个节点、两个节点，都是很巧妙的在数列上。

标准解法是，固定住第1个节点，则剩下还有 n - 1 个节点可以组合。

当 n = 1 时，只有一个根节点，$f(1) = 1$

当 n = 2 时，根节点固定，剩下的一个节点可以放在左子树，也可以放在右子树，这里$f(0)$代表节点为空的情况

$f(2) = f(1)*f(0) +f(0)*f(1)$

当 n = 3 时，根节点固定，剩下 n - 2 个节点可以放左边2个右边0个，也可以放左边1个右边一个，也可以放左边0个，右边2个，即：

$f(3) = f(2)*f(0) + f(1)*f(1)+f(0)*f(2)$

现在可以给出卡特兰数的递归定义了

$f_n=f_0∗f_{n−1}+f_1∗f_{n−2}+…+f_{n−1}f_0 \ \ \text{其中}n≥2$

卡特兰数能干的事还很多，有空再好好学学。

参考资料：

卡特兰(Catalan)数入门详解 - Morning_Glory - 博客园 (cnblogs.com)