在BST中查找交换的节点 [英] Find swapped nodes in a BST

问题描述

我正在尝试编写一个程序，该程序可以检测并打印已交换的BST中的两个节点.

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

I am trying to write a program that can detect and print two nodes in BST that have been swapped.

In a three level tree, I reached near to the solution using this approach.

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;
}

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

but the above approach failed when I tried to test with four level tree.

             20

      15            30

   10    17       25     33

9  16  12  18  22  26  31  34

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

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

因此，16，12是上述BST中交换的元素.如何通过程序找到它们?

Being in root node 15''s right subtree, 12 is still greater (violation).

Being in root node 15''s left subtree, 16 is still greater (violation).

So, 16, 12 are the swapped elements in the above BST. How do I find them through the program?

推荐答案

使用^ ] .该列表将被排序，但两个交换的元素除外.他们中的第一个后面将有一个较小的数字.

Convert the tree to a list using an in-order traversal[^]. The list will be sorted, except for the two swapped elements. The first of them will be followed by a smaller number; the second one will be preceded by a larger number.

9 10 16 <- next number is smaller 15 12 <- prior number is larger 17 18 20 22 25 26 30 31 33 34

不错的游戏:

Nice game:

#pragma once
#include <stdio.h>
#include <tchar.h>

class TreeNode;
class vWalkTree
{
public: // vWalkTree
  virtual  int  Enter(TreeNode* p) = 0;
  virtual  int  Leave(TreeNode* p) = 0;
};

class TreeNode
{
public:
  TreeNode(const int v,TreeNode* l=0,TreeNode* r=0){ value=v; left=l; right=r; }
  ~TreeNode(){ if(left) delete left; if(right) delete right; }

  int        get(){ return value; }

  TreeNode*  most_left();
  TreeNode*  most_right();
  int        compare(TreeNode* with){ return value-with->value; }
  void      swap(TreeNode* p){ int v=value; value=p->value;  p->value=v; }
  void      walk(vWalkTree& w);

private:
  TreeNode*  left;
  TreeNode*  right;
  int        value;
};

void TreeNode::walk(vWalkTree& w)
{
  if(w.Enter(this))
  {
    if(left) left->walk(w);
    if(right) right->walk(w);
    w.Leave(this);
  }
}

TreeNode*  TreeNode::most_left()
{
  TreeNode* r;
  TreeNode* l;
  l = left  ? left ->most_right():0;
  if(l && (0>compare(l))) swap(l);
  r = right ? right->most_left ():0;
  if(r && (0<compare(r))) swap(r);
  return left?left->most_left():this;
}

TreeNode*  TreeNode::most_right()
{
  TreeNode* r;
  TreeNode* l;
  l = left  ? left ->most_right():0;
  if(l && (0>compare(l))) swap(l);
  r = right ? right->most_left ():0;
  if(r && (0<compare(r))) swap(r);
  return right?right->most_right():this;
}

int _tmain(int argc, _TCHAR* argv[])
{
  /*
             20
 
      15            30
 
   10    17       25     33
 
9  16  12  18  22  26  31  34
  */
  TreeNode  root
  (
    20,
    new TreeNode
    (
      15,
      new TreeNode(10,new TreeNode(9),new TreeNode(16)),
      new TreeNode(17,new TreeNode(12),new TreeNode(18))
    ),
    new TreeNode
    (
      30,
      new TreeNode(25,new TreeNode(22),new TreeNode(26)),
      new TreeNode(33,new TreeNode(31),new TreeNode(34))
    )
  );
  
  class PrintTree : public vWalkTree
  {
  public: // vWalkTree
    int    Enter(TreeNode* p)
    {
      if(reached==level){ ++done; _tprintf(__T("%i "),p->get()); }
      ++reached;
      return 1;
    }
    int  Leave(TreeNode* p)
    {
      --reached;
      return 1;
    }
    PrintTree(){ level=0; reached=0; done=0; }
  public:
    unsigned int  level;
    unsigned int  done;
  private:
    unsigned int  reached;
  };

  PrintTree  walk;
  _tprintf(__T("--- before ---\r\n"));
  walk.level = 0;
  do{ walk.done=0; root.walk(walk); ++walk.level; _tprintf(__T("\r\n")); }while(walk.done);
  root.most_left();
  _tprintf(__T("--- after ---\r\n"));
  walk.level = 0;
  do{ walk.done=0; root.walk(walk); ++walk.level; _tprintf(__T("\r\n")); }while(walk.done);
  _gettch();
  return 0;
}

问候.

这篇关于在BST中查找交换的节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！