檢查二叉樹是否具有相同的結構

我應該檢查一個二叉樹是否與使用遞歸的另一個樹具有相同的結構。我遇到麻煩的部分是搞清楚如何在每個級別檢查是否存在左側或右側並將其與其他樹進行比較。任何形式的幫助，將不勝感激謝謝。檢查二叉樹是否具有相同的結構

public boolean hasSameStructureAs(BinaryTree tree){ 
    //If left and right are null they are still similar 
    if(leftChild == null && rightChild == null); 
     return true; 
    if (leftChild == null && rightChild != null) 
     return false; 
    if (leftChild != null && rightChild == null){ 
     return false;

//我有下面的代碼的遞歸部分的麻煩，我想我有這部分正確

if (!tree.equals(rightChild.left,leftChild.left)) return false; 
    if (!tree.equals(rightChild.right, leftChild.right)) return false; 

    return true;

下面是一些構造函數和get/set方法。

public class BinaryTree { 
private String data; 
private BinaryTree leftChild; 
private BinaryTree rightChild; 

public BinaryTree(String d) { 
    data = d; 
    leftChild = null; 
    rightChild = null; 
} 

public BinaryTree(String d, BinaryTree left, BinaryTree right) { 
    data = d; 
    leftChild = left; 
    rightChild = right; 
} 

public String getData() { 
    return data; 
} 

public BinaryTree getLeftChild() { 
    return leftChild; 
} 

public BinaryTree getRightChild() { 
    return rightChild;}

來源

2014-03-30 user3450909

您的BinaryTree是遞歸數據結構，因此您可以在編寫遞歸函數時按照常用方法遞歸執行檢查 - 假定它已經寫入。

以下是我的意思：想象一下，您的BinaryTree類有一個工作hasSameStructureAs方法，您只能在子節點上使用該方法。你將如何檢查當前節點？

檢查tree.getLeftChild()的左側子樹再次this.leftChild;如果hasSameStructureAs返回false，則返回false。如果兩個左子樹null，繼續檢查
檢查的tree.getRightChild() agains this.rightChild右子樹;如果hasSameStructureAs返回false，則返回false。如果兩個右子樹null，或hasSameStructureAs返回true，返回true爲好。

這就是它 - 你做！你所要做的全部方法是null檢查它的左右子樹，並且在它們上面調用hasSameStructureAs。

來源

2014-03-30 00:57:08 dasblinkenlight

感謝使它很清楚，你很不錯！ – user3450909

我需要看到你的.equals方法是絕對肯定的，但它會顯示你沒有遞歸執行它。如果你希望它是遞歸的，如果兩棵樹都有一個左邊的孩子，或者兩個都有一個正確的孩子（或者兩者都有）遞歸地返回該方法，那麼將這些孩子作爲新的「根」來檢查他們的孩子。

如果他們不匹配的任何一點，返回false。如果你已經達到所有孩子都是葉子的地步（無效孩子），那麼返回true。

除此之外，它是作爲製作方法預購遞歸一樣簡單。（訪問家長 - >訪問左邊的孩子，如果有的話 - >訪問正確的孩子，如果有的話，每次訪問孩子重複過程）。

來源

2014-03-30 00:52:22 Gurgadurgen

假設你沒有覆蓋等於，這樣的：你想要什麼

if (!tree.equals(rightChild.left,leftChild.left)) return false;

不會做。 equals（）的默認實現返回（this == other），並且只有當它們是完全相同的對象（即在內存中的相同位置）時纔是如此。

你居然沒有任何遞歸呢。遞歸意味着函數自己調用。考慮左右兒童也是樹木。你已經有了一個方法hasSameStructureAs，那完成後，對於等結構的樹將返回true。因此，你的解決方案應該在兩棵樹的左邊和右邊的孩子上合併調用hasSameStructureAs（），並且組合從每個「邊」獲得的值。

一般而言，遞歸問題的策略是將其分解爲遞歸情況和一個或多個基本情況。用樹結構，你的基本情況將涉及葉子。樹中的葉子是子鏈接爲空的節點。

想象一下，您有一個布爾值用於臨時存儲左側是否相等。

如果this.leftChild和other.leftChild都爲null，leftEq是真的
如果只是其中之一爲null，leftEq是假
否則leftEq是this.leftChild.hasSameStructure（other.leftChild ）

你會這樣做rightEq然後返回leftEq和rightEq。

就我個人而言，我認爲讓這個棘手的問題考慮的事情之一是，你的hasSameStructure是從其中一棵樹的角度寫的。也許想想如何用外部方法hasSameStructure(treeA, treeB)來解決它，然後將其轉化爲實際要求的內容。

來源

2014-03-30 01:22:36 johncip

線索＃1：你的方法被稱爲「hasSameStructureAs」。爲了遞歸，它需要調用「hasSameStructureAs」。線索＃2：你的代碼被傳遞了一個名爲「tree」的參數，但你甚至沒有看它。建議：將BinaryTree重命名爲Node（因爲它是一個有孩子的節點，而不是樹），並將「tree」參數重命名爲「that」，然後明確使用「this」訪問「this 「對象，這樣就可以看到什麼是屬於‘本’與‘說’：

public boolean hasSameStructureAs(Node that) 
    { 
    // first, only bother to check if the children are different at all 
    // (if they are both null, for example, then they will be equal) 
    if (this.leftChild != that.leftChild) 
     { 
     // second, since we already know that they are unequal, if either 
     // one of them is null, then the data structure is unequal 
     if (this.leftChild == null || that.leftChild == null) 
      { 
      return false; 
      } 

     // third, since neither one is null, let's recursively ask them if 
     // they are the same 
     if (!this.leftChild.hasSameStructureAs(that.leftChild)) 
      { 
      return false; 
      } 
     } 
    // and so on ..

而且，因爲這可能是一個家庭作業，你真的需要學習的身影一些它在你的擁有。

來源

2014-03-30 02:12:54 cpurdy

對分配同樣的問題，這是我做的，可能不是最有效的，但結果是準確的

public boolean hasSameStructureAs(BinaryTree tree){ 


    if(tree.getLeftChild() == null && this.getLeftChild() == null) { 
     if(tree.getRightChild() == null && this.getRightChild() == null) { 
      return true;}} 

    if(tree.getLeftChild() == null && this.getLeftChild() == null) { 
     if(tree.getRightChild() != null && this.getRightChild() != null) { 
      return this.getRightChild().hasSameStructureAs(tree.getRightChild());}} 

    if(tree.getLeftChild() != null && this.getLeftChild() != null) { 
     if(tree.getRightChild() != null && this.getRightChild() != null) { 
      return this.getRightChild().hasSameStructureAs(tree.getRightChild()) && this.getLeftChild().hasSameStructureAs(tree.getLeftChild());}} 

    if(tree.getLeftChild() != null && this.getLeftChild() != null) { 
     if(tree.getRightChild() == null && this.getRightChild() == null) { 
      return this.getLeftChild().hasSameStructureAs(tree.getLeftChild());}} 


    return false; 



}

來源

2014-03-31 17:53:59

檢查二叉樹是否具有相同的結構

回答

相關問題