插入/添加二叉树的方法

Question

我需要帮助实现基于二叉树的文本形式的简单网站结构 - 每个新的“页面”都有一个父节点和两个子节点。从家庭开始，设计是将第一个“页面”添加到左侧节点，然后将以家为父节点的后续页面添加到该节点的右侧节点，所有这些也都链接到家庭作为父节点。子类别相同 - 即添加一个父母“商店”的页面应向左搜索，直到它找到商店页面，然后添加到左侧，如果其第一个从该节点添加到相同父级的后续页面的权利。

下面是目前为节点，网站和页面类的代码。我很确定我的问题在于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（）由教师实施，因此其余部分需要符合其中的addpage调用。

Answer 1

，你会想要一个目录树不是一个二叉搜索树

，如果你组织你的节点像这样

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

    //... 
}