檢查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是否等於數值

回答

相關問題