2015-05-13 287 views
0

我應該從二叉樹搜索給定的相冊並將其返回。這是我到目前爲止有:遞歸搜索二叉樹

public AlbumNode getAlbum(AlbumNode root, String name) { 
    if (root != null) { 
     if(root.left != null) getAlbum(root.left, name); 
     if(root.right != null) getAlbum(root.right, name); 
    } 
    if(root.getName().equals(name)) return root; 

    return null; 
} 

我知道是什麼問題,(我認爲),但我堅持......讓所有的節點的名稱後,將它們與名稱,但它對所有這些都做這件事,並返回最後一個檢查(它始終是二叉樹的根)。我該如何解決?

+0

您是否在二進制搜索樹或二叉樹中檢查名稱? – Rahul

+0

二分查找樹,我希望它在找到匹配項時返回。 – AlldaRage

+0

主要問題是,你搜索左邊的樹,但然後扔掉答案。然後你對正確的樹也一樣。我會請你做一些思考,你怎麼才能真正使用這兩個遞歸搜索的結果,而不是把它們扔掉。不幸的是,一對海報已經爲你做了你的想法,所以太遲了。 – ajb

回答

3

嘗試此代碼:

public AlbumNode getAlbum(AlbumNode node, String name) { 
    if (node == null) {  // this checks the base case 
     return null;  // your original code failed for a null root 
    } else { 
     if (node.getName().equals(name)) { 
      return node; 
     } else { 
      AlbumNode result = getAlbum(node.left, name); 
      if (result != null) { 
       return result; 
      } 
      result = getAlbum(node.right, name); 

      return result; // you need to return the result inside the recursion 
     }     // your original code never returned the recursive calls 
    } 
} 
+1

謝謝,它的工作原理。現在有時間研究這個以及我做錯了什麼。我希望我能很快得到遞歸...... ._。 – AlldaRage

+1

@AlldaRage將它標記爲答案,如果它工作 – Lrrr

+0

@Lrrr它不會讓我,直到它發佈後5-6分鐘左右... – AlldaRage

2

的代碼應該捕獲其具有節點結果爲:

public AlbumNode getAlbum(AlbumNode root, String name) { 
    AlbumNode result; 
    if(root.getName().equals(name)){ 
     return root; 
    } 
    if (root != null) { 
     if(root.left != null) result = getAlbum(root.left, name); 
     if(result != null) { 
      return result; 
     } 
     if(root.right != null) result = getAlbum(root.right, name); 
    } 
    return result; 
} 

Binary Tree的項目的情況下,可以存在多於一次。因此,您可能需要修改此代碼以捕獲所有這些代碼的列表。

+1

Theres這個片段的一個問題,如果搜索找到相冊在左側,結果將被第二個'getAlbum'調用覆蓋 – Toumash

+0

@Toumash我相信你在我編輯時評論:) –

+0

這段代碼也可以工作,只是有初始化結果。 – AlldaRage