只需按相同顺序插入节点即可从Preorder获得BST [英] BST from Preorder by just inserting the nodes in same order

问题描述

要从给定的遍历遍历构造BST，如果我尝试以与预给定顺序相同的顺序插入BST，则会得到BST. 因此，我们不是通过对元素进行排序来创建顺序还是执行任何其他算法?

To construct a BST from the preorder traversal given, if I try to insert in the BST in the same order as given in preorder, I get the BST. So, we don't to create the in-order by sorting of the elements or perform any other alogrithm?

是否有一个示例显示不能仅通过插入元素来构造树?

Is there an example which shows that tree can't be constructed by just inserting the elements ?

推荐答案

您是正确的...您可以按照预先遍历给出的顺序插入节点以重建树.

You're correct... you can just insert the nodes in the order given by a preorder traversal to rebuild the tree.

插入的第一个节点必须放在正确的位置，因为它是根，并且预遍历始终将根放在第一位.在预遍历遍历中，遵循的是左子树的预排序布局，后跟右子树.插入左子树节点时，它们将从根向左插入，然后在该子树上递归应用相同的过程.正确的子树以相同的方式重建.使用归纳法，您可以根据需要正式证明这一点.

The first node inserted must be placed at the right place, since it's the root and a preorder traversal always places the root first. What follows in the preorder traversal is the preorder layout of the left subtree followed by the right subtree. As the left subtree nodes are inserted, they are inserted by going left from the root, then recursively applying the same procedure on that subtree. The right subtree is rebuilt the same way. Using induction, you can formally prove this if you like.

希望这会有所帮助！

这篇关于只需按相同顺序插入节点即可从Preorder获得BST的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！