使用“N"个节点，可能有多少种不同的二叉和二叉搜索树? [英] With ' N ' no of nodes, how many different Binary and Binary Search Trees possible?

问题描述

对于二叉树:无需考虑树节点值，我只对具有N"个节点的不同树拓扑感兴趣.

For Binary trees: There's no need to consider tree node values, I am only interested in different tree topologies with 'N' nodes.

对于二叉搜索树:我们必须考虑树节点值.

For Binary Search Tree: We have to consider tree node values.

推荐答案

我推荐这篇文章 由我的同事尼克·帕兰特 (Nick Parlante) 撰写(从他还在斯坦福大学的时候开始).结构不同的二叉树的计数(问题 12)有一个简单的递归解决方案(封闭形式最终是@codeka 的答案已经提到的加泰罗尼亚公式).

I recommend this article by my colleague Nick Parlante (from back when he was still at Stanford). The count of structurally different binary trees (problem 12) has a simple recursive solution (which in closed form ends up being the Catalan formula which @codeka's answer already mentioned).

我不确定结构不同的二叉搜索树(简称 BST)的数量与普通"二叉树的数量有何不同——除了，如果通过考虑树节点值"您的意思是每个节点可能是例如任何与 BST 条件兼容的数字，那么不同(但并非所有 结构 不同！-)BST 的数量是无限的.我怀疑你是这个意思，所以，请举例说明你做的意思！

I'm not sure how the number of structurally different binary search trees (BSTs for short) would differ from that of "plain" binary trees -- except that, if by "consider tree node values" you mean that each node may be e.g. any number compatible with the BST condition, then the number of different (but not all structurally different!-) BSTs is infinite. I doubt you mean that, so, please clarify what you do mean with an example!

这篇关于使用“N"个节点，可能有多少种不同的二叉和二叉搜索树?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！