当存在重复项时，在BST中查找交换元素
当存在重复项时，在BST中查找交换元素
提问于 2014-08-17 03:10:18
问题:二进制搜索树(BST)的两个节点被交换。修复(或纠正) BST而不更改其结构。
我搜索了很多，发现大多数解决方案都假定BST没有任何重复的值，这使得查找交换的元素变得非常简单。但是，我的问题是，如果BST中有重复的值，如何找到交换的元素。我找不到任何解决这个问题的方法，希望有人能给出一个算法来解决这个问题。
谢谢。
回答 1
Stack Overflow用户
回答已采纳
发布于 2014-08-28 01:12:21
给定:具有任意两个节点交换的BST
如果给定的树仍然是二进制搜索树，则不可能知道交换了哪些节点(因为，我们没有任何关于树的前一状态的其他信息)。
关键点:交换后，如果BST属性在任意两个点被违反，那么我们可以识别两个交换节点。
我们可以修改算法以找到给定的二叉树bst (使用max方法)来解决这个问题：
DriverFunction (TreeNode *root)
{
TreeNode *swapped1 = NULL
TreeNode *swapped2 = NULL
FindSwapped ( root,
swapped1,
swapped2,
INT_MIN,
INT_MAX)
if (swapped1 && swapped2)
Print Swapped Nodes
// If you also want to correct the BST,
// Swap the data of nodes pointed out by swapped1 & swapped2
}
void FindSwapped (TreeNode *root,
TreeNode *swapped1,
TreeNode *swapped2,
int minval,
int maxval)
1. if (NULL == root)
2. return
3. if (root->data <= minval || root->data > maxval)
4. if (NULL != swapped1)
5. swapped2 = root
6. return
7. else
8. swapped1 = root
9. FindSwapped (root->LC,
swapped1,
swapped2,
minval,
root->data)
10.FindSwapped (root->RC,
swapped1,
swapped2,
root->data,
maxval)它应该对你的问题很有效。如果有任何问题，请让我知道，如果遗漏了什么，我会修改算法。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/25346002
复制相关文章
相似问题
腾讯云开发者
