StackOverflowError с бинарным деревом - PullRequest
Новая
       4

StackOverflowError с бинарным деревом

0 голосов
/ 23 мая 2011

Имеется следующий метод вставки для левого потомка - дерева правого брата - кажется, что вызывается StackOverflowError в строке, которая снова вызвала addpage в закрытой версии метода. Может кто-нибудь помочь посоветовать, как это можно исправить? Извините, если об этом уже спрашивали. 

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;
}

Ответы [ 2 ]

0 голосов
/ 21 ноября 2014

переписать методы для итерации вместо рекурсии.

Java не реализует удаление хвостовой рекурсии.

0 голосов
/ 21 ноября 2014

Вы пытаетесь реализовать двоичное дерево поиска. Вы должны гарантировать, что операции вставки / удаления / поиска занимают O(logn) время в вашем дереве поиска. Ваш метод addPage не восстанавливает баланс дерева, поэтому в худшем случае высота вашего дерева равна O(n). См. Big-O обозначение , если вы не знакомы с обозначением. Узнайте о красно-черных / AVL деревьях.

Вы используете рекурсию для добавления новых узлов. Поскольку высота дерева может достигать O(n), вы превышаете ограничение на размер стека.

Я не знаю верхнюю границу по умолчанию для размера стека на поток в JVM.

...