從二叉樹刪除葉子

public void deleteLeaves(BSTNode<T> p){      //deletes leaves 
    if(p.left != null){ 
     if(isLeaf(p.left)) 
     p.left = null; 
    } 
    else if(p.right != null){ 
     if(isLeaf(p.right)) 
     p.right = null; 
    } 
    else{ 
     deleteLeaves(p.right); 
     deleteLeaves(p.left); 
    } 
    }

我似乎無法弄清楚爲什麼它不能正確刪除樹葉。它似乎只刪除樹的最後一片葉子。任何建議，幫助將非常感激。從二叉樹刪除葉子

來源

2011-10-20 Bill

你的if語句有點搞砸了;只有一個的分支機構將被採取。考慮一下如果neder p.left或p.right爲空，會發生什麼。

如果我正確理解你的數據結構，我可能會寫這樣的：

// If there is something to the left... 
if (p.left != null) 
    if (isLeaf(p.left)) 
     p.left = null;    // delete it if it's a leaf... 
    else 
     deleteLeaves(p.left);  // else recurse. 

// If there's something to the right... 
if (p.right != null) 
    if (isLeaf(p.right)) 
     p.right = null;   // delete it if it's a leaf... 
    else 
     deleteLeaves(p.right);  // else recurse.

來源

2011-10-20 17:20:40 aioobe

非常感謝，幫助了很多！ – Bill

沒問題。別客氣。 – aioobe

這個答案解決了我對同一問題的一個問題： http://stackoverflow.com/questions/28313390/removing-leaves-from-binary-tree-not-being-represented-properly/28313612#28313612 –

此刻，如果p.left != null那麼它甚至不會檢查p.right。 else-if應該只是一個if。另外，如果兩個相鄰節點都爲空，那麼就調用deleteLeaves()，這是沒有意義的，因爲它們是空的。重組您的代碼; @aioobe有一個很好的建議

來源

2011-10-20 17:26:36

要正確使用遞歸，它必須在同一種控制語句中。您不應該在if中檢查條件，然後在else if中執行實際的遞歸。

來源

2011-10-20 17:27:54 SetSlapShot

我看到在條件塊內部遞歸沒有問題。 – aioobe

Appologies如果它是這樣讀的，我的意思是遞歸應該在相同的條件塊中完成，以確定是否需要遞歸/如何實現。 – SetSlapShot

從二叉樹刪除葉子

回答

相關問題