1

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

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

4

1 回答 1

2

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

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

希望这可以帮助!

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