基本的な配列[] 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; 
    } 

} 

そして、配列に格納されたその子を持つルートの犬のスポットを含むデータ・ファイルを与えられています。私は、データファイルを開くことができるコードを記述し、ツリー名のデータ構造を調べて、入力名がルート（子孫）の子孫であるかどうかを調べる必要があります。

私はデータファイルを開くことができると確信しています。私はリンクとして配列を持つノードを作成する構文に苦労しています。私たちの教科書は、左右にリンクするバイナリツリーのみをカバーしますが、可変数のリンクには該当しません。 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>>(); 
    } 
} 

私はデータファイルを使用する必要があるので、ノードの構造をDog []に格納する以外に変更することはできません。私は子供を格納するために基本配列を使ってノードクラスの例を見つけることができず、これを行うための構文を理解することはできません。私はそれを学ぶ前にジェネリック医薬品なしでそれを見ることが私の理解に役立つだろうと思う。ここで

は、これまでの私のコードです：

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

これをツリーにどのように転送しますか。

すべてのオブジェクトにはis selfの配列があるため、それらをネストすることは可能です。

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. 

この概念は、あなたがrecurrency検索を導入する必要があり、深い検索で拡張する必要があり、親に子供から関係が追加される可能性があります。