帶二叉樹的StackOverflowError

對於左側子樹 - 右側兄弟樹有以下插入方法 - 似乎在該方法的專用版本中再次調用addpage的行上導致StackOverflowError。任何人都可以幫助建議如何修復它？對不起，如果之前已經問過。帶二叉樹的StackOverflowError

public PageNode addPage(String PageName) 
{ 
    PageNode ParentNode=new PageNode(); 
    ParentNode.page=currentPage.page; 
    if (this.homePage==null) 
     this.homePage=ParentNode.parent; 
    else 
     ParentNode=this.addPage(PageName,ParentNode.parent); 
    return ParentNode; 
} 
private PageNode addPage(String PageName, PageNode ParentNode) 
{ 
      ParentNode = new PageNode(); 
      ParentNode.page=new Page(PageName); 

    if (this.currentPage.page.compareTo(ParentNode.page)==0) 
    { 
     System.out.println("attempt to insert a duplicate"); 
    } 
    else 
        if (ParentNode.page.compareTo(currentPage.page)<0) 

         if(currentPage.firstchild == null) 
      currentPage.firstchild=ParentNode; 
         else 
          ParentNode = addPage(PageName, ParentNode.firstchild); 
         else if(currentPage.nextsibling == null) 
           currentPage.nextsibling=ParentNode; 
         else 
           ParentNode = addPage(PageName, ParentNode.nextsibling); 
      return ParentNode; 
}

來源

2011-05-22 Matt

考慮修復代碼格式;如果/ else沒有'{}'也會導致細微的難以辨認的錯誤，特別是。當嵌套像那樣。（如果代碼難以閱讀，我會停下來看一個問題）。順便說一下，「查看」導致堆棧溢出的最簡單方法是查看每次調用的傳遞情況以及它如何適應調用堆棧。使用調試器（或那些基本的'println'）。 – 2011-05-22 21:27:52

這應該是什麼語言？考慮適當標記。 – 2011-05-22 21:37:25

您試圖實現二叉查找樹。您應該保證在您的搜索樹中插入/刪除/查找操作需要O(logn)時間。您的addPage方法不會重新平衡樹，因此在最壞的情況下，樹的高度爲O(n)。如果您不熟悉符號，請參閱Big-O notation。瞭解紅黑/ AVL樹。

您正在使用遞歸來添加新節點。由於樹的高度可能大到O(n)，因此您超出了堆棧大小的限制。

我不知道JVM中每個線程堆棧大小的默認上限。

來源

2014-11-20 23:51:35 mostruash

一個好的二叉樹搜索將按照您的建議進行，但僅僅是一個功能性的二叉樹搜索不必。請參閱Knuth以獲取權威性討論和示例算法。 – ddyer 2014-11-21 00:46:08

@ddyer修正措辭以避免混淆。謝謝。 – mostruash 2014-11-21 00:55:29

重寫迭代而不是遞歸的方法。

Java不執行尾遞歸刪除。

來源

2014-11-21 00:44:14 ddyer

帶二叉樹的StackOverflowError

回答

相關問題