带二叉树的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

回答

相关问题