要从给定的前序遍历构造BST，如果我尝试按照预先给定的顺序插入BST，我会获得BST . 那么，我们不是通过对元素进行排序或执行任何其他算法来创建有序的？
有没有一个例子表明只是插入元素就无法构建树？
你是对的......你可以按照前序遍历给出的顺序插入节点来重建树 .
插入的第一个节点必须放在正确的位置，因为它是根，并且前序遍历总是先放置根 . 前序遍历中的后续内容是左子树的前序布局，后跟右子树 . 当插入左子树节点时，它们通过从根向左移动插入，然后在该子树上递归地应用相同的过程 . 正确的子树以相同的方式重建 . 使用归纳法，如果您愿意，可以正式证明这一点 .
希望这可以帮助！
1 回答
你是对的......你可以按照前序遍历给出的顺序插入节点来重建树 .
插入的第一个节点必须放在正确的位置，因为它是根，并且前序遍历总是先放置根 . 前序遍历中的后续内容是左子树的前序布局，后跟右子树 . 当插入左子树节点时，它们通过从根向左移动插入，然后在该子树上递归地应用相同的过程 . 正确的子树以相同的方式重建 . 使用归纳法，如果您愿意，可以正式证明这一点 .
希望这可以帮助！