Binary search tree这道题什么意思?
How many structurally different BSTs can you form with 4 distinct element?
如题,在一个网站上看到这么一个问题,不太理解题目想表达的意思,这道题的原意和解答是什么呢?为什么?
枫鸟院花月
10 years, 2 months ago
Answers
就是问你给你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