草庐IT

c++ - 在 BST 中查找交换节点

coder 2024-02-02 原文

我正在尝试编写一个程序来检测和打印 BST 中已交换的两个节点。

在三层树中，我使用这种方法接近了解决方案。

If (!AllSubTreeAreValid())
{
//Nodes swapped on same side of main root node
}
else
{
  int max = getMax(root->left);
  int min = getMin(root->right);
  if(max > root->data || min < root->data )
  {
     //Nodes swapped on different sides of main root node
     //Print max and min values

  }
else 
{
 //No node swappped
}
}

//Helper functions
int GetMaxEle(TreeNode* tree)
{
    while(tree->right!=NULL)
    {
        tree=tree->right;
    }
    return tree->info;
}

int GetMinEle(TreeNode* tree)
{
    while(tree->left!=NULL)
    {
        tree=tree->left;
    }
    return tree->info;
}

但是当我尝试用四层树进行测试时，上述方法失败了。

             20

      15            30

   10    17       25     33

9  16  12  18  22  26  31  34

在根节点 15 的右子树中，12 仍然更大(违规)。

在根节点 15 的左子树中，16 仍然更大(违规)。

因此，16、12 是上述 BST 中的交换元素。我如何通过该程序找到它们？

最佳答案

考虑这个问题的一种方法是利用这样一个事实，即树的有序遍历将按排序顺序生成所有元素。如果您可以在此遍历过程中检测到与排序顺序的偏差，则可以尝试定位错误位置的两个元素。

让我们先看看如何对一个简单的排序数组执行此操作，然后将使用我们的算法来构建适用于树的东西。直觉上，如果我们从一个排序的数组开始，然后交换两个(不相等!)元素，我们将以数组中的一些元素错位而告终。例如，给定数组

1 2 3 4 5

如果我们交换 2 和 4，我们最终得到这个数组:

1 4 3 2 5

我们如何检测到 2 和 4 在这里被交换了？好吧，因为 4 是两个元素中较大的一个并且被向下交换，所以它应该大于它周围的两个元素。同样，因为 2 被交换了，它应该小于它周围的两个元素。由此，我们可以得出结论，2 和 4 被交换了。

但是，这并不总是能正常工作。例如，假设我们交换 1 和 4:

4 2 3 1 5

这里，2 和 1 都小于它们的相邻元素，而 4 和 3 都比它们的相邻元素大。从这里我们可以看出这四个中的两个以某种方式被交换了，但不清楚我们应该交换哪些。但是，如果我们取这些值中的最大值和最小值(分别为 1 和 4)，我们最终会得到被交换的对。

更一般地，要查找序列中交换的元素，您需要查找

  • 数组中最大的局部最大值。
  • 数组中最小的局部最小值。

这两个元素不合适，应该调换。

现在，让我们考虑一下如何将其应用于树木。由于树的有序遍历将产生两个元素乱序的排序序列，因此一种选择是遍历树，记录我们找到的元素的有序序列，然后使用上述算法。例如，考虑您的原始 BST:

              20
         /         \
      15             30
     /   \         /   \ 
   10    17      25     33
  / |   /  \    /  \    |  \
9  16  12  18  22  26  31  34

如果我们将其线性化为一个数组，我们会得到

9 10 16 15 12 17 18 20 22 25 26 30 31 33 34

请注意，16 大于其周围的元素，而 12 小于其周围的元素。这立即告诉我们 12 和 16 被交换了。

因此，解决此问题的一个简单算法是对树进行有序遍历，将其线性化为一个序列，如 vector 或 deque，然后扫描该序列以找到最大的局部最大值和最小的局部最小值。这将在 O(n) 时间内运行，使用 O(n) 空间。一个更棘手但更节省空间的算法是一次只跟踪三个节点——当前节点、它的前任节点和它的后继节点——这将内存使用量减少到 O(1)。

希望这对您有所帮助!

关于c++ - 在 BST 中查找交换节点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7260292/

amp43codesectionprec++algorithmdata-structurestreebinary-search-tree

有关c++ - 在 BST 中查找交换节点的更多相关文章

  1. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  2. ruby - 当使用::指定模块时，为什么 Ruby 不在更高范围内查找类？ - 2

    我刚刚被困在这个问题上一段时间了。以这个基地为例:moduleTopclassTestendmoduleFooendend稍后，我可以通过这样做在Foo中定义扩展Test的类:moduleTopmoduleFooclassSomeTest但是，如果我尝试通过使用::指定模块来最小化缩进:moduleTop::FooclassFailure这失败了:NameError:uninitializedconstantTop::Foo::Test这是一个错误，还是仅仅是Ruby解析变量名的方式的逻辑结果？ 最佳答案 Isthisabug,or

  3. ruby - 查找字符串中的内容类型(数字、日期、时间、字符串等) - 2

    我正在尝试解析一个CSV文件并使用SQL命令自动为其创建一个表。CSV中的第一行给出了列标题。但我需要推断每个列的类型。Ruby中是否有任何函数可以找到每个字段中内容的类型。例如，CSV行:"12012","Test","1233.22","12:21:22","10/10/2009"应该产生像这样的类型['integer','string','float','time','date']谢谢! 最佳答案 require'time'defto_something(str)if(num=Integer(str)rescueFloat(s

  4. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  5. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  6. ruby-on-rails - 在 Rails 中更高效地查找或创建多条记录 - 2

    我有一个应用需要发送用户事件邀请。当用户邀请friend(用户)参加事件时，如果尚不存在将用户连接到该事件的新记录，则会创建该记录。我的模型由用户、事件和events_user组成。classEventdefinvite(user_id,*args)user_id.eachdo|u|e=EventsUser.find_or_create_by_event_id_and_user_id(self.id,u)e.save!endendend用法Event.first.invite([1,2,3])我不认为以上是完成我的任务的最有效方法。我设想了一种方法，例如Model.find_or_cr

  7. ruby - 查找重叠的正则表达式匹配项 - 2

    我想找到给定字符串中的所有匹配项，包括重叠匹配项。我怎样才能实现它？#Example"a-b-c-d".???(/\w-\w/)#=>["a-b","b-c","c-d"]expected#Solutionwithoutoverlappedresults"a-b-c-d".scan(/\w-\w/)#=>["a-b","c-d"],but"b-c"ismissing 最佳答案 在积极的前瞻中使用捕获:"a-b-c-d".scan(/(?=(\w-\w))/).flatten#=>["a-b","b-c","c-d"]参见Rubyde

  8. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

  9. ruby - 在 Ruby 中查找多个正则表达式匹配的模式和位置 - 2

    这应该是一个简单的问题，但我找不到任何相关信息。给定一个Ruby中的正则表达式，对于每个匹配项，我需要检索匹配的模式$1、$2，但我还需要匹配位置。我知道=~运算符为我提供了第一个匹配项的位置，而string.scan(/regex/)为我提供了所有匹配模式。如果可能，我需要在同一步骤中获得两个结果。 最佳答案 MatchDatastring.scan(regex)do$1#Patternatfirstposition$2#Patternatsecondposition$~.offset(1)#Startingandendingpo

  10. += 的 Ruby 方法 - 2

    有没有办法让Ruby能够做这样的事情？classPlane@moved=0@x=0defx+=(v)#thisiserror@x+=v@moved+=1enddefto_s"moved#{@moved}times,currentxis#{@x}"endendplane=Plane.newplane.x+=5plane.x+=10putsplane.to_s#moved2times,currentxis15 最佳答案 您不能在Ruby中覆盖复合赋值运算符。任务在内部处理。您应该覆盖+，而不是+=。plane.a+=b与plane.a=

随机推荐