基本數組[] Java中的樹數據結構

Question

這是一個家庭作業問題，所以我沒有找到完整的代碼答案。

我一直在考慮一類犬

package lab12; 

import java.io.Serializable; 

public class Dog implements Serializable{ 

    public Dog[] children; 
    public String name; 

    public Dog(String name) 
    { 
     this.name = name; 
    } 

    @Override 
    public String toString() 
    { 
     return name; 
    } 

} 

幷包含有其存儲在陣列兒童根狗現貨數據文件。我需要編寫可打開數據文件的代碼，然後遍歷樹數據結構以查看輸入名稱是否爲根（Spot）的後代。

我很自信我可以打開數據文件。我正在努力創建具有數組作爲鏈接的節點的語法。我們的教科書只包含二叉樹，它可以鏈接到左側或右側，但不包含可變數量的鏈接。我找到了一個使用List方法的通用示例。

public class Tree<T> 
{ 
    private Node<T> root; 

    public static class Node<T> 
    { 
     private T data; 
     private Node<T> parent; 
     private List<Node<T>> children; 
    } 

    public Tree(T rootData) 
    { 
     root = new Node<T>(); 
     root.data = rootData; 
     root.children = new ArrayList<Node<T>>(); 
    } 
} 

因爲我必須使用數據文件，我不能節點的結構改變不是存儲在兒童狗[]以外。我找不到一個使用基本數組來存儲子元素的節點類的例子，我無法弄清楚這樣做的語法。我認爲這會幫助我的理解，在我嘗試學習它之前，先看看它沒有泛型。

這裏是我到目前爲止的代碼：

package lab12; 

public class DogTree 
{ 
    //Start Inner Class 
    private static class Node 
    { 
     private String name; 
     private Node parent; 
     private Node Dog[] children; //This is where I'm confused 
    } 
    //End Inner Class 

    private Node root; 

    public DogTree() 
    { 
     root = null; 
    } 

    public boolean isDescendant(String name) 
    { 
     return isInSubtree(name, root); 
    } 

    private static boolean isInSubtree(String name, Node subTreeRoot) 
    { 
     if(subTreeRoot == null) 
     { 
      return false; 
     } 
     else if(subTreeRoot.name.equals(name)) 
     { 
      return true; 
     } 
     else 
     { 
      //This is where my confusion on the 
      //node design causes implementation problems 
      return isInSubtree(name, subTreeRoot.children); 
     } 
    } 
} 

Answer 1

需要迭代兒童陣列上。

private static boolean isInSubtree(String name, Node subTreeRoot) 
    { 
     if(subTreeRoot == null) 
     { 
      return false; 
     } 
     else if(subTreeRoot.name.equals(name)) 
     { 
      return true; 
     } 
     else 
     { 
      for(int i = 0; i< subTreeRoot.children.length();i++) 
      if(isInSubtree(name, subTreeRoot.children[i])) 
      return true; 
     } 
     return false; 

    } 

Answer 2

這些算法中數組和列表之間的主要區別在於，您的數組容量有限，需要處理項目（小狗）的分配;

如果任務是學習數組，您不應該關注泛型。泛型允許您爲對象的常用功能定義模板。最好是將實現改爲通用時，而不是從它們開始解決具體問題。

你現在有什麼是類這樣的：

class Dog { 

    private String name; 
    private Dog[] puppies 

    public Dog(String name) 
    { 
     this.name = name; 
    } 

} 

你可以做的是具體的方法添加到它會執行一些動作。

class Dog { 

    private final String name; 
    private final Dog[] puppies = new Dog[20]; //We create 20 slots for puppies to fill 
    private int puppiesCount = 0; 

    public Dog(String name) 
    { 
     this.name = name; 
    } 

    public addPuppie(Dog puppie) { 
     this.puppies[puppiesCount] = puppie; //We assign the puppie to this Dog puppies. 
     this.puppiesCount = puppiesCount + 1; //We increment the count of puppies 
    } 

    public Dog[] getPuppies() { 
     return Arrays.copyOf(puppies, puppiesCount); 
    } 

    public boolean isMyPuppie(Dog puppie) { 

     for(int = 0; i < puppiesCount; i++) { 

      if(puppies[i] == puppie) { //We compare the object references to state that are equal 
      return true; 
      } 

     } 

     return false; 
    } 
} 

這是如何轉換成樹的。

由於每個對象都有自己的數組，因此可以將它們嵌套在一起。

Dog max = new Dog("Max"); 

Dog tom = new Dog("Tom"); //childOfRoot; 

Dog barry = new Dog("Barry);"// child of Tom 

要創建一個樹，你需要做這樣的事情。

tom.addPuppie(barry); // We assign barry to tom 
max.addPuppie(tom); // we assign tom to max. 

這個概念應該與你需要引入一個復發的搜索，並從孩子父母的關係可以增加深搜索進行擴展。