Basic Array [] Baum Datenstruktur in Java

Question

Dies ist eine Hausaufgabenfrage, daher suche ich nicht nach einer vollständigen Codeantwort.

Ich habe eine Klasse Hund

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

} 

und eine Daten-Datei gegeben worden, die eine Wurzel Hund-Punkt enthält, die ihre Kinder in einem Array gespeichert hat. Ich muss Code schreiben, der die Datendatei öffnen kann, und dann durch die Baumdatenstruktur gehen, um zu sehen, ob ein Eingabe-Name ein Nachkomme des Stammes (Spot) ist.

Ich bin ziemlich zuversichtlich, ich kann die Datendatei öffnen. Ich kämpfe mit der Syntax der Erstellung von Knoten, die ein Array als Link haben. Unser Lehrbuch behandelt nur binäre Bäume, die entweder nach links oder rechts verlinken, aber nicht zu einer variablen Anzahl von Links. Ich habe ein Beispiel für eine generische Version gefunden, die einen List-Ansatz verwendet.

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

Da ich die Daten-Datei verwenden, kann ich nicht die Struktur des Knoten auf etwas anderes als ändern, um die Kinder in einem Hund zu speichern []. Ich kann kein Beispiel für eine Knotenklasse finden, die ein Basisarray zum Speichern der untergeordneten Elemente verwendet, und ich kann die Syntax dafür nicht herausfinden. Ich denke, es würde meinem Verständnis helfen, es ohne Generika zu sehen, bevor ich versuche, es zu lernen.

Hier ist mein Code so weit:

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

Sie über das Array von Kindern zu wiederholen brauchen.

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

Der wesentliche Unterschied zwischen Arrays und Array-Liste in diesen Algorithmen ist, dass Sie eine begrenzte Kapazität für Arrays haben und Sie müssen die Zuordnung von Positionen (Welpen) behandeln;

Sie sollten sich nicht auf das generische konzentrieren, wenn die Aufgabe darin besteht, das Array zu lernen. Mit Generisch können Sie eine Vorlage für die allgemeine Funktionalität von Objekten definieren. Es ist besser, die Implementierung zu ändern, wenn sie in eine generische Form gebracht wird, als von einer konkreten Lösung auszugehen.

Was Sie jetzt haben, ist die Klasse wie folgt:

class Dog { 

    private String name; 
    private Dog[] puppies 

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

} 

Was Sie tun können, ist die spezifische Methode, um es hinzuzufügen, dass eine Aktion durchführen wird.

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

Wie diese Übertragung in einen Baum.

Da jedes Objekt ein Array von sich selbst besitzt, ist es möglich, sie zu verschachteln.

Dog max = new Dog("Max"); 

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

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

Um einen Baum zu erstellen, müssen Sie so etwas tun.

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

Dieses Konzept sollte mit tiefer Suche erweitert werden, in dem Sie hinzugefügt werden eine Rezidivs Suche und eine Beziehung von Kind zu Eltern einzuführen brauchen könnten.