含有4个元素值均不相同的结点的二叉排序树有多少种,怎么算?_百度...
发布网友
发布时间：2024-09-26 12:02
共1个回答
热心网友
时间：2024-10-04 13:37
含有4个元素各不相同的节点的二叉树，共有14种。
只要画出所有含有4个节点的二叉树，对每一个二叉树，对它进行中序遍历时，按4个元素值升序的序列进行填入，所得的二叉树，就是一种所求的二叉排序树，因为节点数较少，所以可以穷举画出，共有14种。
当元素个数为0，1，2，3，......时相应的二叉排序树的数目组成的这个序列，就是一个“卡塔兰数”序列。
对此感兴趣的朋友，可以网上查阅相关资料，很方便的。因为内容较多，且推导需要较多的数学知识，就不作详细推导了。它可以有几个不同的递推公式进行计算的。
卡特兰数又称卡塔兰数，英文名Catalan number，是组合数学中一个常出现在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名，其前几项为（从第零项开始） : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...
