遞歸搜索二叉樹問題

我寫下面的代碼遞歸搜索二叉樹。即使我的system.out語句正在執行，return語句不會返回整個遞歸，因此此方法不會返回true。遞歸搜索二叉樹問題

任何人都可以建議如何退出整個遞歸。

public static boolean isElementinTree(int num, BinaryTreeNode root) 
{ 
    if (root != null) 
    { 
     int rootVal = root.getData(); 
     BinaryTreeNode left = root.getLeft(); 
     BinaryTreeNode right = root.getRight(); 
     if (left != null) 
     { 
      isElementinTree(num,left); 

     } 
     if (right != null) 
     { 
      isElementinTree(num,right); 
     } 
     if (num == rootVal) 
     { 
      System.out.println("------ MATCH -----");    
      return true; 
     }   
    } 
    return false; 
}

來源

2012-08-07 Manish

我覺得你應該先檢查是否在通過節點的匹配且僅當它沒有數據，就應該移動到左邊或右邊子樹。 – 2012-08-07 13:52:16

這就是問題所在：

if (left != null) 
{ 
    isElementinTree(num,left); 

} 
if (right != null) 
{ 
    isElementinTree(num,right); 
}

你調用的方法在那些情況下 - 但忽略結果。我懷疑你只是想改變每個那些立即返回，如果它的發現：

if (left != null && isElementinTree(num, left)) 
{ 
    return true; 
} 
if (right != null && isElementinTree(num, right)) 
{ 
    return true; 
}

或者使整個事情更聲明，你可以做到這一點更簡單：

public static boolean isElementinTree(int num, BinaryTreeNode root) 
{ 
    return root != null && (root.getData() == num || 
          isElementInTree(num, root.getLeft()) || 
          isElementInTree(num, root.getRight())); 
}

它的優良使用空的第二個參數調用isElementInTree，因爲您已經通過第一部分保護了這一點。

來源

2012-08-07 13:52:01

那永遠不會在樹的右半部分返回'true' – Claudiu 2012-08-07 13:52:35

那隻會搜索第一個分支，還是我錯過了什麼？ – pcalcao 2012-08-07 13:52:43

正在修復 - 現在檢查:) – 2012-08-07 13:54:11

您需要檢查該值是否在其中一個分支中，並保存該結果。

初始化變量boolean found = false;。

當你做遞歸調用，你需要做的是這樣的：在右側

found = isElementinTree(num,left)

同樣的事情。

最後，而不是返回false，檢查值樹枝上找到，只是return found;

另外，如果你正在尋找的號碼是第一次檢查不是節點本身，而不是首先搜索每個分支。只需切換if的順序。

來源

2012-08-07 13:52:02 pcalcao

如果你發現你正在尋找一個在左邊或右邊子樹，你需要返回這個事實回升到主叫方的元素：

if (left != null) 
    { 
     if(isElementinTree(num,left)) return true; 
    } 
    if (right != null) 
    { 
     if(isElementinTree(num,right)) return true; 
    }

只有當你發現它沒有左樹，右樹和當前節點是否最終會落到最後的return false。

來源

2012-08-07 13:58:51

遞歸解決方案：

boolean isElementinTree (int num, BinaryTreeNode root) 
{ 
    if(root == null) 
    return false; 

    if(root.value == num) 
    return true; 

    boolean n1 = isElementinTree(num,root.getLeft()); 
    boolean n2 = isElementinTree(num,root.getRight()); 

    return n1 ? n1 : n2; 

}

來源

2013-08-01 00:57:52

遞歸搜索二叉樹問題

回答

相關問題