大门| 2008年大门|问题69

二进制搜索树（BST）存储37到573之间的值。考虑下面的键序列。

I.  81, 537, 102, 439, 285, 376, 305
II. 52, 97, 121, 195, 242, 381, 472
III. 142, 248, 520, 386, 345, 270, 307
IV. 550, 149, 507, 395, 463, 402, 270 

假设BST搜索273键失败。上面哪些序列按我们在搜索中可能遇到的顺序列出节点？ （A） 仅限II和III （B） 只有我和我 （C） 仅限III和IV （D） 仅限III 答复: （D） 说明： 要搜索的密钥273：

• 一） 81、537、102、439、285、376、305不正确 我们不能从285到376，因为273比285小。
• 二） 52、97、121、195、242、381、472不正确。 我们不能从381到472，因为273比381小。
• 三） 142248520386345270307是正确的
• 550、149、507、395、463、402、270不正确。 我们不能从395到463去寻找273

下面给出了二进制搜索树的表示形式。

这个问题的小测验