大门|大门CS模拟2018 |第2组|问题45

二叉搜索树的后序遍历由2,7,6,10,9,8,15,17,20,19,16,12给出。 那么这棵树的预序遍历是：

（A） 2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20 （B） 7, 6, 2, 10, 9, 8, 15, 16, 17, 20, 19, 12 （C） 7, 2, 6, 8, 9, 10, 20, 17, 19, 15, 16, 12 （D） 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20 答复: （D） 说明： 由于给定的树是二叉树，所以按序遍历将始终按顺序排序，即2、6、7、8、9、10、12、15、16、17、19、20。 现在我们可以使用给定的后序和顺序遍历来绘制二叉搜索树。最后一棵树将是：

因此，前序遍历将是：12、8、6、2、7、9、10、16、15、19、17、20。

选项（D）是正确的。 这个问题的小测验