二叉树的 StackOverflowError

Question

对于左子树（右同级树）使用以下插入方法似乎会在该方法的私有版本中再次调用 addpage 的行处导致 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;
}

Answer 1

重写方法以迭代而不是递归。

Java 没有实现尾递归删除。

Answer 2

您正在尝试实现二叉搜索树。您应该保证插入/删除/查找操作在搜索树中花费 O(logn) 时间。您的 addPage 方法不会重新平衡树，因此在最坏的情况下，树的高度为 O(n)。如果您不熟悉该表示法，请参阅Big-O 表示法。了解红黑/AVL 树。

您正在使用递归来添加新节点。由于树的高度可能达到O(n)，因此超出了堆栈大小的限制。

我不知道 JVM 中每个线程的堆栈大小的默认上限。