检查2个BST是否等于数值

我正在研究一个代码，用于确定2个BST是否在值上相等。检查2个BST是否等于数值

这就是我想出的，但它只是返回true，我真的不知道问题是什么。

public boolean same(BSTree t2) { 
    return sameTree(root, t2); 
    } 

    private boolean sameTree(TreeNode n, BSTree other) {//L-M-R 
    boolean found = false; 
    if (n != null) { 
     sameTree(n.getLeftNode(), other); 

     if (other.search(n.getData())) { 
      found = true; 
     } 
     sameTree(n.getRightNode(), other); 
    } 
    return found; 
}

在主要方法中，我创建了2个BST并在其中插入了值。然后，我打电话给我以下称为方法：

System.out.println("Are the trees the same: " + tree1.same(tree2));

来源

2014-01-24 Scarl

您的逻辑已关闭。以下是它现在正在执行的操作：您遍历每个节点。如果在其他BST中发现它，则代码集合被发现为真，但如果其中一个子代不在其他树中？你递归地调用这个孩子的函数，事实证明这是错误的，但是不会返回任何值。最后，你只检查第一个调用，即根，是否在第二个BST中。

要解决此问题，请在每次调用后查看返回的值是否为假。如果是，则一起退出递归并返回false。

来源

2014-01-24 07:15:29

再次查看我的代码，你是对的，我会尝试再次解决它。谢谢！ – Scarl

有两个问题与此代码：

你忽略了递归调用，以sameTree
它只检查的结果，如果tree1包含在tree2。即使tree2中的节点数多于tree1，它也会返回true。

来源

2014-01-24 07:15:38 Henry

我尝试了不同的方法，这（工作完全正常！）

public boolean same(BST t1,BST t2){ 
     return sameHelper(t1.root,t2.root) 
    } 
    private boolean sameHelper(TreeNode n1,TreeNode n2){ 
     if(n1==n2){ 
      return true; 
     }else if(n1==null||n2==null){ 
      return false; 
     }else{ 
      return ((n1.data==n2.data) && (n1.llink==n2.llink) && (n1.rlink==n2.rlink)); 
     }

就像你们说，我在以前的做法，我只检查了根，并在根在它也会返回true。

来源

2014-01-24 07:32:02 Scarl

这种方法现在检查树是否结构相同。如果它们具有相同的值但结构不同，它将返回false。而且，子树必须是真正相同的对象，而不仅仅是相同的。 – Henry

@henry你是什么意思？ – Scarl

给定两棵树的值1,2,3，它们可以看起来很不相同，例如，可以有一个在根，另外两个。现在你会在这种情况下返回'false'。我解释了原来的问题，以便只有树中的相同值才能被视为“相同”。 – Henry

检查2个BST是否等于数值

回答

相关问题