Baum des Knotens <T> explaination

Question

Ich weiß nicht, ob ich dies nach den Regeln der Website tun darf ... aber ich werde meine Chance nutzen ... bitte ertragen Sie mit mir, ich bin nur ein Student .. . :-)

Ich habe eine College-Aufgabe ... Ich habe schwer zu verstehen, was die Klassen tun sollten ... Ich bin zu meinem Lehrer zu drei verschiedenen Gelegenheiten gegangen und die Antwort, die ich von ihm bekam, nicht Hilfe überhaupt. Wie auch immer die Zuweisungsdetails lauten wie folgt ...

Erstellen Sie eine Klasse namens Tree, die als Container für Knoten fungiert. Die Baumklasse sollte die folgenden Methoden unterstützen.

public void add (Node Eltern, Knoten Kind) {} ​​ - Fügt einen neuen untergeordneten Knoten zu dem übergeordneten Knoten

public void removeChild (Nodeparent, Knoten Kind) {} ​​ - Entfernt einen untergeordneten Knoten von einem übergeordneten Knoten.

öffentlichen Knoten getRootNode() {} - Liefert die Wurzel des Baumes

public void SetRoot (Node root) {} - Setzt den Wurzelknoten des Baumes

public boolean enthält (T data) {} - Sucht den Baum für einen bestimmten Typ

public void dfs (Node Kind) {} ​​ - Führt eine depth-first-Suche des tre e und gibt jeden Knoten (eingekerbte)

public void bfs (Node child) {} ​​ - Führt eine Breadth-First-Suche des Baumes, und gibt jeden Knoten (eingekerbt)

1. Die Baumklasse sollte so parametrisiert sein, dass sie einen generischen Typ T behandelt, wodurch Bäume von Strings, Dateien usw. erzeugt werden können, z Tree<String> tree = new Tree<String>()
2. Der Baum-Klasse sollte die Baumstruktur unter Verwendung eines Adjazenzliste implementieren und in der folgenden Art und Weise definiert werden: Map<Node<T>, List<Node<T>>> tree = new HashMap<Node<T>, List<Node<T>>();

Die Knotenklasse sollte auch einen generischen Typ T und setzen verschiedene Methoden zu behandeln parametriert werden .. .

Jetzt habe ich meine Knoten-Klasse geschrieben, die gut funktioniert ... und um ehrlich zu sein, ich war mir sicher, dass ich eine Knoten-Klasse geschrieben habe, die einen Baum erstellt. Aber nachdem ich die Baumklassenbeschreibung gelesen habe, bin ich verwirrt. Was ich in der Baumkarte speichern sollte. Mir fällt es schwer, das Ganze zu visualisieren.

Vielleicht kann jemand erklären, was Lehrer will und mich in die richtige Richtung bringen. Ich bin NICHT auf der Suche nach dem Code selbst ... will nur verstehen, was ich tun soll.

Meine Knotenklasse

public class Node<T> 
{ 
    private Node<T> root; // a T type variable to store the root of the list 
    private Node<T> parent; // a T type variable to store the parent of the list 
    private T child; 
    private List<Node<T>> children = new ArrayList<Node<T>>(); // a T type list to store the children of the list 

    // default constructor 
    public Node(T child) 
    { 
     setParent(null); 
     setRoot(null); 
     setItem(child); 
    } 

    // constructor overloading to set the parent 
    public Node(Node<T> parent) 
    { 
     this.setParent(parent); 
     //this.addChild(parent); 
    } 

    // constructor overloading to set the parent of the list 
    public Node(Node<T> parent, Node<T> child) 
    { 
     this(parent); 
     this.children.add(child); 
    } 

    /** 
    * This method doesn't return anything and takes a parameter of 
    * the object type you are trying to store in the node 
    * 
    * @param Obj an object 
    * @param 
    **/ 
    public void addChild(Node<T> child) 
    { 
     child.root = null; 
     child.setParent((Node<T>)this); 
     this.children.add(child); // add this child to the list 
    } 

    public void removeChild(Node<T> child) 
    { 
     this.children.remove(child); // remove this child from the list 
    } 

    public Node<T> getRoot() { 
     return root; 
    } 

    public boolean isRoot() 
    { 
     // check to see if the root is null if yes then return true else return false 
     return this.root != null;  
    } 

    public void setRoot(Node<T> root) { 
     this.root = root; 
    } 

    public Node<T> getParent() { 
     return parent; 
    } 

    public void setParent(Node<T> parent) { 
     this.parent = parent; 
    } 

    public T getItem() { 
     return child; 
    } 

    public void setItem(T child) { 
     this.child = child; 
    } 

    public boolean hasChildren() 
    { 
     return this.children.size()>0; 
    } 

    @SuppressWarnings("unchecked") 
    public Node<T>[] children() 
    { 
     return (Node<T>[]) children.toArray(new Node[children.size()]); 
    } 

    @SuppressWarnings({ "unchecked"}) 
    public Node<T>[] getSiblings() 
    { 
     if(this.isRoot()!=false && parent==null) 
     { 
      System.out.println("this is root or there are no siblings"); 
      return null; 
     } 
     else{ 
      List<Node<T>> siblings = new ArrayList<Node<T>>((Collection<? extends Node<T>>) Arrays.asList(new Node[this.parent.children.size()])); 
      Collections.copy(siblings, this.parent.children); 
      siblings.remove(this); 
      return siblings.toArray(new Node[siblings.size()]); 
     } 
    } 
} 

Answer 1

Sie verwenden die Karte für die folgenden:

Der Schlüssel des hashmap ist ein gegebener Knoten, und der Wert des hashmap sind die untergeordneten Knoten für den gegebenen Knoten.

public class Tree<T> { 
    private Node<T> rootNode; 
    private HashMap<Node<T>, List<Node<T>> tree; 

    //and then some kind of function to go through the tree. 
    public void expandNode(Node<T> node) { 
     if (tree.get(node) == null) { 
      System.out.println(node); 
      return; 
     } 
     for(Node<T> n : tree.get(node)) { 
      System.out.println(node); 
      expandNode(n); 
     } 
    } 
} 

Könnte ich klarstellen, wie der Baum funktioniert?

Answer 2

Mit Blick auf die 2 Punkte in der Liste, werde ich vermuten, dass Punkt Nummer 1 am verwirrendsten ist.

Der Baum selbst kann parametriert werden. Der type-Parameter der Baumklasse kann innerhalb einer inneren Klasse verwendet werden, die zum Erstellen der Knoten verwendet wird. Das heißt, für die Zwecke Ihrer Zuweisung sollte die Knotenklasse wahrscheinlich innerhalb der Tree-Klasse sein, damit sie den T-Type-Parameter verwenden kann, der der Tree-Klasse gegeben wird.

Auf diese Weise kann der Baum alles speichern (Strings, Dateien, Doubles usw.). Die Node-Klasse dient einfach dazu, jedes beliebige T-Objekt zu speichern.

Answer 3

Das ist ein bisschen seltsam. Wenn ich dies tun würde und die Aufgabe nicht anders lautete, würde ich wahrscheinlich überhaupt keine Tree-Klasse schreiben; Ich würde einfach Node als rekursive Datenstruktur verwenden und den Wurzelknoten eines Baumes den gesamten Baum repräsentieren.

Da es nicht so aussieht, als ob Sie das tun sollten, könnten Sie einfach Tree<T> eine Wrapperklasse erstellen, die einen Verweis auf ein einzelnes Node<T> Objekt hat. Sie können die Logik für die erforderlichen Methoden in jede Klasse einfügen.

Der Anfang des Codes könnte wie folgt aussehen:

public class Tree<T> { 

    private Node<T> root; 

    public Tree(Node<T> root) { 
     this.root = root; 
    } 

}