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.
问问题
418 次
2 回答
0
我想我已经找到了解决办法。:)
我们有前序遍历、插入和删除方法。
假设我们得到了一个 BST。
我们所做的是，我们提供具有给定 BST 的前序遍历方法。由于前序遍历总是先到父节点，所以我们递归删除并插入每个根（因为根是我们遇到的第一个父）节点，直到根的左子树为空。
现在你开始删除根，直到没有节点离开。把那些删除的节点放在一个数组或任何你想要的地方。您将获得已排序的节点集。（即节点将按排序顺序删除。最小的在前，依此类推...）
于 2011-10-21T06:54:39.967 回答
0
嗯...假设我们在根节点有+，在左节点有1，在右节点有2。预购+ 1 2顺序将是1 + 2.. 不同之处在于第一个和第二个已交换，因此如果您有插入和删除操作，您可以递归地将每个根节点值与其左节点值交换，然后使用预购遍历将返回的树将导致中序遍历。
我不确定这是否是要走的路，但我希望它会有所帮助。
于 2011-10-18T05:46:45.353 回答