Binary search tree这道题什么意思?


How many structurally different BSTs can you form with 4 distinct element?
如题,在一个网站上看到这么一个问题,不太理解题目想表达的意思,这道题的原意和解答是什么呢?为什么?

二叉树 数据结构

枫鸟院花月 10 years, 2 months ago

就是问你给你4个不同的元素,能够构造出多少个不同的二叉搜索树吧?
比如元素1,2,3,4,这四个元素按不同的先后顺序读入并建立二叉搜索树(假设不考虑平衡问题)得到的结果可能一样也可能不一样。比如,按照1,3,2,4和1,3,4,2的顺序建立的二叉搜索树就是相同的,而1,2,3,4和1,2,4,3就不同。
现在就是问有多少个不同的二叉搜索树。
当然,这题还有一种解释:structurally different——如果不管树中节点的大小,只按树的形态来算。比如1,4,2,3和1,4,3,2虽然建立的树的具体节点值不一样,但是树的形态却一样,计算有多少种形态的树就可以了。

sola7 answered 10 years, 2 months ago

4个节点可以组成多少个不同的二叉树

答案是14种,节点数可以通过公式算出来。
具体过程可以搜索
卡特兰数.

soso君 answered 10 years, 2 months ago

Your Answer