1

要从给定的前序遍历构造一个 BST，如果我尝试以与前序中给定的相同顺序插入 BST，我会得到 BST。那么，我们不是通过对元素进行排序或执行任何其他算法来创建有序吗？

有没有一个例子表明不能通过插入元素来构造树？

4

1 回答 1

2

你是对的......你可以按照前序遍历给出的顺序插入节点来重建树。

插入的第一个节点必须放在正确的位置，因为它是根，并且前序遍历总是将根放在第一位。在前序遍历中遵循的是左子树的前序布局，然后是右子树。当插入左子树节点时，它们从根向左插入，然后在该子树上递归地应用相同的过程。以同样的方式重建右子树。如果您愿意，可以使用归纳法正式证明这一点。

希望这可以帮助！

于 2013-10-28T16:54:10.180 回答