如何实现BST中序遍历？
其实我想知道的不是如何实现BST的中序遍历算法，而是只使用BST的插入、删除和前序遍历算法来实现。
您可以假设您已获得用于插入、删除和前序遍历的标准 BST 算法的实现。
Actually what I want to know is not how to implement the in-order traversal algorithm for a BST but to implement it only using insertion, deletion and pre-order traversal algorithms for a BST.
You can assume that you are given the implementations for standard BST algorithms for insertion, deletion and pre-order traversal.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
嗯...假设我们在根节点有 +，在左节点有 1，在右节点有 2。预订顺序将是
+ 1 2，按顺序将是1 + 2.. 区别在于第一个和第二个已交换，因此如果您有插入和删除时，您可以递归地将每个根节点值与其左节点值交换，然后使用前序遍历树，这将导致中序遍历。我不确定这是否是正确的方法，但我希望它能有所帮助。
Hmmm... Lets say we have + at root and 1 at left node and 2 at right node. The pre-order will be
+ 1 2and in order will be1 + 2.. the difference is that 1st and 2nd have been swapped , so if you have insertion and deletion you can recursively swap each root node value with its left node value and then using pre-order traverse the tree which will return will cause a inorder traversal.I am not sure if this is the way to go, but I hope it does help.
我想我已经找到了解决方案。 :)
我们有前序遍历、插入和删除方法。
假设我们得到了 BST。
我们所做的是，我们提供给定 BST 的前序遍历方法。由于前序遍历总是先到父节点，所以我们递归地删除并插入每个根（因为根是我们遇到的第一个父节点）节点，直到根的左子树为空。
现在您开始删除根，直到没有剩余节点。将这些删除的节点放入数组中或任何您想要的位置。您将获得排序后的节点集。 （即节点将按排序顺序删除。最小的第一个，依此类推......）
I think I have found a solution. :)
we have pre-order traversal, insertion and deletion methods.
Assume that we are given a BST.
what we do is, we provide the pre-order traversal method with the given BST. since pre-order traversal always go to the parent node first, we delete and insert each root(because the root is the first parent we meet) node recursively until the left sub tree of the root is null.
now you start deleting the root until there's no nodes left.Put those deleted nodes in an array or wherever you want. You will get the sorted set of nodes. (i.e. the nodes will be deleted in a sorted order.the smallest first and so on...)