метод вставки / добавления для двоичного дерева - PullRequest
Новая
       27

метод вставки / добавления для двоичного дерева

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

Мне нужна помощь в реализации простой структуры сайта в текстовой форме, основанной на двоичном дереве - каждая новая «страница» имеет родительский узел и двух дочерних элементов. Начиная с дома, дизайн состоит в том, что первая «страница» добавляется к левому узлу, а затем к правому узлу этого и т. Д. Добавляются последующие страницы с домом в качестве родителя, и все также ссылаются на дом в качестве родителя. То же самое для подкатегорий - то есть добавление страницы с родительскими "магазинами" должно вести поиск влево до тех пор, пока не будет найдена страница магазинов, а затем добавлена ​​влево, если она будет добавлена ​​первой справа от этого узла для последующих страниц с тем же родителем.

Вот код для классов узлов, сайтов и страниц. Я почти уверен, что моя проблема заключается в нерекурсивности метода addpage, так как до сих пор при выполнении кода создается домашняя страница с двумя дочерними узлами магазинов и новостей, но тогда все остальные узлы равны нулю. Кроме того, действительно новости должны быть добавлены в правый узел магазинов, а не Оме, но я немного озадачен, как это сделать .... 

public class Site
{

public class PageNode
{

    private Page page;
    private PageNode firstchild;
    private PageNode parent;
    private PageNode nextsibling;

public PageNode()
{
    this.firstchild = null;
    this.parent = null;
    this.nextsibling = null;
}

public PageNode(String PageName)
{
    this.firstchild = null;
    this.parent = null;
    this.nextsibling = null;
}

public String toString()
{
    return ""+page;
}

}
private PageNode currentPage;
private PageNode homePage;

public Site()
{
    this.homePage=new PageNode();
    this.homePage.page=new Page("Home");
    this.currentPage=this.homePage;

    PageNode shops=addPage("Shops",this.homePage);
    addPage("News",this.homePage);
    PageNode products=addPage("Products",this.homePage);

    addPage("Paisley",shops);
    addPage("Hamilton",shops);

    PageNode kitchen=addPage("Kitchen",products);
    addPage("Bedroom",products);

    addPage("Kettles",kitchen);
    addPage("Cookers",kitchen);
    addPage("Toasters",kitchen);
}

public PageNode addPage(String PageName)
{
            this.currentPage=new PageNode();
            this.currentPage.page=new Page(PageName);

    PageNode ParentNode=new PageNode();
    ParentNode.page=currentPage.page;
    if (this.homePage==null)
        this.homePage=ParentNode;
    else
        ParentNode=this.addPage(PageName,ParentNode);
    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;
                            ParentNode.firstchild = new PageNode();
                            ParentNode.firstchild.page = new Page(PageName);
                        }
                            else if(currentPage.nextsibling == null)
                            {
                                currentPage.nextsibling=ParentNode;                        
                                ParentNode.nextsibling = new PageNode();
                                ParentNode.nextsibling.page = new Page(PageName);
                            }
            return ParentNode;
}

public void displayCurrentPage()
{
                if (this.homePage!=null)
    {
        this.displayBranches(this.homePage);
    }
    else
        System.out.println("tree is empty");
    }
    private void displayBranches(PageNode ParentNode)
    {
    if (ParentNode!=null)
    {
        System.out.println(ParentNode.page+"  ");
        System.out.print("    left:  ");
        if (ParentNode.firstchild!=null)
            System.out.println(ParentNode.firstchild.page);
        else
            System.out.println("null");
        System.out.print("    right: ");
        if (ParentNode.nextsibling!=null)
            System.out.println(ParentNode.nextsibling.page);
        else
            System.out.println("null");
                    displayBranches(ParentNode.firstchild);
        displayBranches(ParentNode.nextsibling);
    }
}

и класс страницы 

public class Page implements Comparable
{
private String page;

public Page (String PageName)
{
    page = PageName;
}

public String getPage()
{
    return page;
}

public int compareTo(Object otherObject)
{
int result=((Page)otherObject).page.compareTo(this.page);
return result;
}
public String toString()
{
    return ""+page;
}
}

Обратите внимание: public Site () был реализован преподавателем, поэтому остальные должны соответствовать вызовам на этой странице.

1 Ответ

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

вам понадобится директория дерево, а не бинарное дерево поиска

это будет более понятно, если вы структурируете свой узел следующим образом 

public class PageNode
{
    private Page page;
    private PageNode child;
    private PageNode parent;
    private PageNode nextSibling;

    //...
}
...