一棵有n个不同素的二叉查找树有多少种不同形态？ 素给定的二叉查找树有很多种构建方式，那么应该如何计算所有可能的形态数目？ 二叉查找树[1]或者是一棵空树，或者是具有下列性质的二叉树： 1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 3. 它的左、右子树也分别为二叉查找树。 因此二叉查找树中的素一定是互不相同的。一旦二叉查找树的形态固定，其中的素所在的位置也将确定下来。 假如包含
这 个素的二叉查找树的形态是这样：
那么我们便可以知道这颗二叉查找树只可能长这样：
因此问 ，等价于问 。 答案就是卡特兰数 . 具体推导过程可以参考这篇文章：游客：n个顶点的二叉树的异构数 因此前面的例子中包含 这 个素的二叉查找树有 种形态：
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/60976.html
