Wie implementiere ich eine Baumdatenstruktur in Java? [geschlossen]

496

Gibt es eine Standard-Java-Bibliotheksklasse zur Darstellung eines Baums in Java?

Insbesondere muss ich Folgendes darstellen:

  • Der Unterbaum an jedem Knoten kann eine beliebige Anzahl von untergeordneten Elementen haben
  • Jeder Knoten (nach dem Stamm) und seine untergeordneten Knoten haben einen Zeichenfolgenwert
  • Ich muss alle untergeordneten Elemente (eine Art Liste oder ein Array von Zeichenfolgen) eines bestimmten Knotens und seinen Zeichenfolgenwert abrufen (dh eine Methode, die einen Knoten als Eingabe verwendet und alle Zeichenfolgenwerte des untergeordneten Knotens als Ausgabe zurückgibt).

Gibt es dafür eine verfügbare Struktur oder muss ich meine eigene erstellen (wenn ja, wären Implementierungsvorschläge großartig).

ikl
quelle
3
Wenn Sie Java 8 verwenden und Ihre Knoten mit Streams, Filtern usw. durchlaufen möchten; dann möchten Sie vielleicht einen Blick auf Durian github.com/diffplug/durian
Ned Twigg
1
Sie können diese API verwenden: sourceforge.net/p/treeds4j
Mohamed Ennahdi El Idrissi

Antworten:

306

Hier:

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

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

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

Dies ist eine grundlegende Baumstruktur, die für Stringoder jedes andere Objekt verwendet werden kann. Es ist ziemlich einfach, einfache Bäume zu implementieren, um das zu tun, was Sie brauchen.

Alles, was Sie hinzufügen müssen, sind Methoden zum Hinzufügen, Entfernen, Durchlaufen und Konstruieren. Das Nodeist der Grundbaustein der Tree.

jjnguy
quelle
304
Genau genommen ist die TreeKlasse nicht notwendig, weil jeder Nodefür sich als Baum gesehen werden kann.
Joachim Sauer
34
@ Joa, ich mag eine Struktur, die die Wurzel enthält. Sie können der Baumklasse Methoden hinzufügen, die sinnvoller sind, einen Baum als einen einzelnen Knoten aufzurufen.
jjnguy
24
@ Justin: zum Beispiel? Das ist eine ehrliche Frage: Ich kann mir keine einzige Methode vorstellen, die für den gesamten Baum Sinn macht und für einen Teilbaum keinen Sinn ergibt.
Joachim Sauer
22
Ich stimme @Joa zu, dass die Tree-Klasse nicht erforderlich ist. Ich bevorzuge es, die rekursive Natur von Bäumen im Code explizit zu belassen, indem ich keine separate Tree-Klasse hinzufüge und die Node-Klasse konsistent verwende. Stattdessen nenne ich eine Variable 'Baum' oder 'Wurzel', wenn klar sein muss, dass es sich um den Wurzelknoten eines Baumes handelt.
Jvdbogae
89
@Joa Ein vier Jahre älteres Ich stimmt dir vollkommen zu. Nix die Baumklasse.
jjnguy
122

Noch eine Baumstruktur:

public class TreeNode<T> implements Iterable<TreeNode<T>> {

    T data;
    TreeNode<T> parent;
    List<TreeNode<T>> children;

    public TreeNode(T data) {
        this.data = data;
        this.children = new LinkedList<TreeNode<T>>();
    }

    public TreeNode<T> addChild(T child) {
        TreeNode<T> childNode = new TreeNode<T>(child);
        childNode.parent = this;
        this.children.add(childNode);
        return childNode;
    }

    // other features ...

}

Beispielnutzung:

TreeNode<String> root = new TreeNode<String>("root");
{
    TreeNode<String> node0 = root.addChild("node0");
    TreeNode<String> node1 = root.addChild("node1");
    TreeNode<String> node2 = root.addChild("node2");
    {
        TreeNode<String> node20 = node2.addChild(null);
        TreeNode<String> node21 = node2.addChild("node21");
        {
            TreeNode<String> node210 = node20.addChild("node210");
        }
    }
}

BONUS
Siehe vollwertigen Baum mit:

  • Iterator
  • suchen
  • Java / C #

https://github.com/gt4dev/yet-another-tree-structure

Grzegorz Dev
quelle
2
Ich fand Ihre Bibliothek gerade äußerst nützlich. Vielen Dank. Ich möchte jedoch wissen, wie das dynamische Auffüllen der Baumstruktur basierend auf der Referenzbeziehung zwischen Eltern und Kind implementiert werden kann. Das gegebene Beispiel ist, dass ich ein Mitglied1 Sponsor eines anderen Mitglieds2 und Mitglied2 Sponsor Mitglied 3 und so und so für habe. Habe bereits die Beziehung zu Tabellendatensätzen, bin mir aber nicht sicher, ob ich sie mithilfe deiner Bibliothek in einen Baum einfügen kann.
d4v1dv00
1
Ab 2016 enthält der Link keine Quelldateien oder Downloads
Sharon Ben Asher
2
Meiner Ansicht nach ist diese Antwort drei Jahre nach der oben genannten höher bewerteten Antwort die sauberere. Ich würde jedoch die LinkedList durch eine ArrayList für this.children ersetzen.
HopeKing
1
Ich würde ein Set für die Kinder verwenden.
DPM
Ich könnte mich irren, aber es scheint, dass Sie bei dieser Implementierung hasNext()vor jedem Aufruf aufrufen müssen next(), um gültige Ergebnisse zu erhalten. Dies ist nicht Teil der IteratorSpezifikation.
Robert Lewis
97

Im JDK ist tatsächlich eine ziemlich gute Baumstruktur implementiert.

Schauen Sie sich javax.swing.tree , TreeModel und TreeNode an . Sie sind für die Verwendung mit dem konzipiert, JTreePanelaber sie sind in der Tat eine ziemlich gute Baumimplementierung, und nichts hindert Sie daran, sie ohne Swing-Schnittstelle zu verwenden.

Beachten Sie, dass Sie ab Java 9 diese Klassen möglicherweise nicht mehr verwenden möchten, da sie in den 'Kompaktprofilen' nicht vorhanden sind .

Gareth Davis
quelle
5
Ja, ich habe sie in der Vergangenheit benutzt und sie werden alles tun, was Sie von einem Baum wollen. Der einzige Nachteil, den ich mir vorstellen kann, ist die Länge der Namen der jeweiligen implementierenden Klassen: DefaultTreeModel und DefaultMutableTreeNode. Ausführlich, aber nicht, dass es so wichtig ist, denke ich.
Ultimate Gobblement
4
Eine gute Möglichkeit, damit umzugehen, besteht darin, einige statische Methoden newModel () und newNode () zu erstellen und diese dann statisch zu importieren.
Gareth Davis
140
Ich würde es vermeiden, Swing-Bibliotheken für nicht-Swing-bezogene Funktionen zu verwenden. Dies ist eine schlechte Codierungspraxis . Sie wissen nie, wie Swing ihre Bäume implementiert, welche Abhängigkeiten sie haben und wie sich dies in Zukunft ändern könnte. Swing ist keine Utility-Bibliothek, sondern eine UI-Bibliothek.
Jasop
44
Ich denke, schlechte Codierungspraxis ist etwas hart.
Gareth Davis
51
javax.swing.tree.TreeModel ist eine öffentliche Schnittstelle (genau wie java.util.List) und weist keine inkompatiblen Änderungen auf. Ein zusätzlicher Vorteil ist, dass Sie Ihren Baum während der Entwicklung leicht debuggen / visualisieren können.
lbalazscs
45

Was ist damit?

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;

/**
  * @author [email protected] (Yohann Coppel)
  * 
  * @param <T>
  *          Object's type in the tree.
*/
public class Tree<T> {

  private T head;

  private ArrayList<Tree<T>> leafs = new ArrayList<Tree<T>>();

  private Tree<T> parent = null;

  private HashMap<T, Tree<T>> locate = new HashMap<T, Tree<T>>();

  public Tree(T head) {
    this.head = head;
    locate.put(head, this);
  }

  public void addLeaf(T root, T leaf) {
    if (locate.containsKey(root)) {
      locate.get(root).addLeaf(leaf);
    } else {
      addLeaf(root).addLeaf(leaf);
    }
  }

  public Tree<T> addLeaf(T leaf) {
    Tree<T> t = new Tree<T>(leaf);
    leafs.add(t);
    t.parent = this;
    t.locate = this.locate;
    locate.put(leaf, t);
    return t;
  }

  public Tree<T> setAsParent(T parentRoot) {
    Tree<T> t = new Tree<T>(parentRoot);
    t.leafs.add(this);
    this.parent = t;
    t.locate = this.locate;
    t.locate.put(head, this);
    t.locate.put(parentRoot, t);
    return t;
  }

  public T getHead() {
    return head;
  }

  public Tree<T> getTree(T element) {
    return locate.get(element);
  }

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

  public Collection<T> getSuccessors(T root) {
    Collection<T> successors = new ArrayList<T>();
    Tree<T> tree = getTree(root);
    if (null != tree) {
      for (Tree<T> leaf : tree.leafs) {
        successors.add(leaf.head);
      }
    }
    return successors;
  }

  public Collection<Tree<T>> getSubTrees() {
    return leafs;
  }

  public static <T> Collection<T> getSuccessors(T of, Collection<Tree<T>> in) {
    for (Tree<T> tree : in) {
      if (tree.locate.containsKey(of)) {
        return tree.getSuccessors(of);
      }
    }
    return new ArrayList<T>();
  }

  @Override
  public String toString() {
    return printTree(0);
  }

  private static final int indent = 2;

  private String printTree(int increment) {
    String s = "";
    String inc = "";
    for (int i = 0; i < increment; ++i) {
      inc = inc + " ";
    }
    s = inc + head;
    for (Tree<T> child : leafs) {
      s += "\n" + child.printTree(increment + indent);
    }
    return s;
  }
}
MountainX
quelle
5
Wie würde DFS in einem Baum implementiert, der mit diesem Klassenobjekt erstellt wurde?
Leba-Lev
3
Wie würde das Entfernen eines Blattes mit dieser Klasse implementiert?
Ghedas
2
Wofür würde das Kopffeld verwendet?
Acour83
2
Es wäre großartig gewesen, wenn diese Klasse eine Dokumentation hätte. Ich verstehe nicht ganz, was Methoden mögen setAsParentoder getHeadtun, und dies ist die Zeit, in der ich wirklich Hilfe bei Baumdatenstrukturen bekommen könnte. Auch die Originalquelle des Dokuments enthält keine Kommentare.
Disasterkid
23

Ich schrieb eine kleine Bibliothek , dass Griffe generic Bäume. Es ist viel leichter als das Swing-Zeug. Ich habe auch ein Maven-Projekt dafür.

Vivin Paliath
quelle
3
Ich benutze es jetzt, funktioniert hervorragend. Musste die Quelle für meine eigenen Anpassungen erheblich ändern, aber es war ein guter Ausgangspunkt. Danke Vivin!
Jasop
20
public class Tree {
    private List<Tree> leaves = new LinkedList<Tree>();
    private Tree parent = null;
    private String data;

    public Tree(String data, Tree parent) {
        this.data = data;
        this.parent = parent;
    }
}

Natürlich können Sie Dienstprogrammmethoden hinzufügen, um untergeordnete Elemente hinzuzufügen / zu entfernen.

PaulJWilliams
quelle
1
Dies deutet darauf hin, dass das übergeordnete Element eines Baums ein Baum ist. Ich glaube, Sie haben versucht, eine Tree Node-Klasse zu erstellen.
Madhur Bhargava
16

Sie sollten zunächst definieren, was ein Baum ist (für die Domäne). Dies geschieht am besten, indem Sie zuerst die Schnittstelle definieren . Nicht alle Baumstrukturen können geändert werden und können hinzugefügt und entfernt werden Knoten sollte eine optionale Funktion sein. erstellen wir hierfür eine zusätzliche Schnittstelle.

Es ist nicht erforderlich, Knotenobjekte zu erstellen, die die Werte enthalten . Tatsächlich sehe ich dies in den meisten Baumimplementierungen als großen Konstruktionsfehler und Overhead an. Wenn Sie sich Swing ansehen, TreeModelist das frei von Knotenklassen ( DefaultTreeModelnutzt nur TreeNode), da diese nicht wirklich benötigt werden.

public interface Tree <N extends Serializable> extends Serializable {
    List<N> getRoots ();
    N getParent (N node);
    List<N> getChildren (N node);
}

Veränderbare Baumstruktur (ermöglicht das Hinzufügen und Entfernen von Knoten):

public interface MutableTree <N extends Serializable> extends Tree<N> {
    boolean add (N parent, N node);
    boolean remove (N node, boolean cascade);
}

Angesichts dieser Schnittstellen muss sich Code, der Bäume verwendet, nicht viel darum kümmern, wie der Baum implementiert wird. Auf diese Weise können Sie sowohl generische als auch spezialisierte Implementierungen verwenden verwenden, bei denen Sie den Baum realisieren, indem Sie Funktionen an eine andere API delegieren.

Beispiel: Dateibaumstruktur

public class FileTree implements Tree<File> {

    @Override
    public List<File> getRoots() {
        return Arrays.stream(File.listRoots()).collect(Collectors.toList());
    }

    @Override
    public File getParent(File node) {
        return node.getParentFile();
    }

    @Override
    public List<File> getChildren(File node) {
        if (node.isDirectory()) {
            File[] children = node.listFiles();
            if (children != null) {
                return Arrays.stream(children).collect(Collectors.toList());
            }
        }
        return Collections.emptyList();
    }
}

Beispiel: generische Baumstruktur (basierend auf Eltern / Kind-Beziehungen):

public class MappedTreeStructure<N extends Serializable> implements MutableTree<N> {

    public static void main(String[] args) {

        MutableTree<String> tree = new MappedTreeStructure<>();
        tree.add("A", "B");
        tree.add("A", "C");
        tree.add("C", "D");
        tree.add("E", "A");
        System.out.println(tree);
    }

    private final Map<N, N> nodeParent = new HashMap<>();
    private final LinkedHashSet<N> nodeList = new LinkedHashSet<>();

    private void checkNotNull(N node, String parameterName) {
        if (node == null)
            throw new IllegalArgumentException(parameterName + " must not be null");
    }

    @Override
    public boolean add(N parent, N node) {
        checkNotNull(parent, "parent");
        checkNotNull(node, "node");

        // check for cycles
        N current = parent;
        do {
            if (node.equals(current)) {
                throw new IllegalArgumentException(" node must not be the same or an ancestor of the parent");
            }
        } while ((current = getParent(current)) != null);

        boolean added = nodeList.add(node);
        nodeList.add(parent);
        nodeParent.put(node, parent);
        return added;
    }

    @Override
    public boolean remove(N node, boolean cascade) {
        checkNotNull(node, "node");

        if (!nodeList.contains(node)) {
            return false;
        }
        if (cascade) {
            for (N child : getChildren(node)) {
                remove(child, true);
            }
        } else {
            for (N child : getChildren(node)) {
                nodeParent.remove(child);
            }
        }
        nodeList.remove(node);
        return true;
    }

    @Override
    public List<N> getRoots() {
        return getChildren(null);
    }

    @Override
    public N getParent(N node) {
        checkNotNull(node, "node");
        return nodeParent.get(node);
    }

    @Override
    public List<N> getChildren(N node) {
        List<N> children = new LinkedList<>();
        for (N n : nodeList) {
            N parent = nodeParent.get(n);
            if (node == null && parent == null) {
                children.add(n);
            } else if (node != null && parent != null && parent.equals(node)) {
                children.add(n);
            }
        }
        return children;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        dumpNodeStructure(builder, null, "- ");
        return builder.toString();
    }

    private void dumpNodeStructure(StringBuilder builder, N node, String prefix) {
        if (node != null) {
            builder.append(prefix);
            builder.append(node.toString());
            builder.append('\n');
            prefix = "  " + prefix;
        }
        for (N child : getChildren(node)) {
            dumpNodeStructure(builder, child, prefix);
        }
    }
}
Peter Walser
quelle
1
Ich habe ein Problem, wenn ich dieser Struktur folge, wenn ich tree.add ("A", "B") mache. tree.add ("A", "C"); tree.add ("C", "D"); tree.add ("E", "A"); E ist ein Elternteil von A Wie machen wir das?
SaNiks
1
Hallo saNicks, es gab einen Fehler im obigen Code, der dazu führte, dass die letzte Beziehung nicht hinzugefügt wurde. Es ist jetzt behoben, und ich habe auch Nicht-Null-Prüfungen und (noch wichtiger) zyklische Prüfungen hinzugefügt, die verhindern, dass die Baumstruktur verletzt wird (Hinzufügen eines Codes oder eines seiner Vorfahren als Kind zu sich selbst). Danke für den Tipp!
Peter Walser
1
Ich habe den Fehler behoben, wenn jemand nach einer Lösung für diesen Fehler sucht. Sie müssen nur sehen, ob die add-Methode false zurückgibt. Wenn sie falsch ist, erstellen Sie einfach ein temporäres neues LinkedHashSet <N> und klonen Sie die Knotenliste des Baums hinein. Dann können Sie sie löschen Fügen Sie im Baum den übergeordneten Knoten hinzu, der im vorherigen Schritt nicht hinzugefügt wurde, und fügen Sie dann den gesamten tempNode wieder zum übergeordneten Baum hinzu. Vielen Dank für die Struktur!
SaNiks
2
Entfernen Sie einfach diese nutzlosen öffentlichen Modifikatoren von Ihren Schnittstellen.
Hamedz
1
Wie kann ich daraus ein JSON-Array generieren?
Pawan Pandey
12

In keiner Antwort wird ein stark vereinfachter, aber funktionierender Code erwähnt. Hier ist er also:

public class TreeNodeArray<T> {
    public T value;
    public final  java.util.List<TreeNodeArray<T>> kids =  new java.util.ArrayList<TreeNodeArray<T>>();
}
Peenut
quelle
10

Sie können jede XML-API von Java als Dokument und Knoten verwenden. XML ist eine Baumstruktur mit Strings

Raja Nagendra Kumar
quelle
5
ausgezeichnete Idee, wir könnten im Speicher XML-Schema mit dom4j + jaxen xpath verwenden, um Knoten zu suchen.
Ben Rhouma Zied
8

Wenn Sie Whiteboard-Codierung, ein Interview oder einfach nur die Verwendung eines Baums planen, ist die Ausführlichkeit dieser Elemente ein wenig groß.

Es sollte ferner gesagt werden, dass der Grund, warum ein Baum dort nicht vorhanden ist, wie z. B. a Pair(worüber dasselbe gesagt werden könnte), darin besteht, dass Sie Ihre Daten in der Klasse kapseln sollten, die ihn verwendet, und die einfachste Implementierung sieht wie folgt aus:

/***
/* Within the class that's using a binary tree for any reason. You could 
/* generalize with generics IFF the parent class needs different value types.
 */
private class Node {
  public String value;
  public Node[] nodes; // Or an Iterable<Node> nodes;
}

Das ist es wirklich für einen Baum beliebiger Breite.

Wenn Sie einen Binärbaum möchten, ist die Verwendung mit benannten Feldern oft einfacher:

private class Node { // Using package visibility is an option
  String value;
  Node left;
  Node right;
}

Oder wenn Sie einen Versuch wollten:

private class Node {
  String value;
  Map<char, Node> nodes;
}

Jetzt hast du gesagt, du willst

um in der Lage zu sein, alle untergeordneten Elemente (eine Art Liste oder ein Array von Zeichenfolgen) mit einer Eingabezeichenfolge abzurufen, die einen bestimmten Knoten darstellt

Das klingt nach deinen Hausaufgaben.
Aber da ich mir ziemlich sicher bin, dass jetzt eine Frist abgelaufen ist ...

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;

public class kidsOfMatchTheseDays {
 static private class Node {
   String value;
   Node[] nodes;
 }

 // Pre-order; you didn't specify.
 static public List<String> list(Node node, String find) {
   return list(node, find, new ArrayList<String>(), false);
 }

 static private ArrayList<String> list(
     Node node,
     String find,
     ArrayList<String> list,
     boolean add) {
   if (node == null) {
     return list;
   }
   if (node.value.equals(find)) {
     add = true;
   }
   if (add) {
     list.add(node.value);
   }
   if (node.nodes != null) {
     for (Node child: node.nodes) {
       list(child, find, list, add);
     }
   }
   return list;
 }

 public static final void main(String... args) {
   // Usually never have to do setup like this, so excuse the style
   // And it could be cleaner by adding a constructor like:
   //     Node(String val, Node... children) {
   //         value = val;
   //         nodes = children;
   //     }
   Node tree = new Node();
   tree.value = "root";
   Node[] n = {new Node(), new Node()};
   tree.nodes = n;
   tree.nodes[0].value = "leftish";
   tree.nodes[1].value = "rightish-leafy";
   Node[] nn = {new Node()};
   tree.nodes[0].nodes = nn;
   tree.nodes[0].nodes[0].value = "off-leftish-leaf";
   // Enough setup
   System.out.println(Arrays.toString(list(tree, args[0]).toArray()));
 }
}

Dies bringt Sie dazu, wie folgt zu verwenden:

$ java kidsOfMatchTheseDays leftish
[leftish, off-leftish-leaf]
$ java kidsOfMatchTheseDays root
[root, leftish, off-leftish-leaf, rightish-leafy]
$ java kidsOfMatchTheseDays rightish-leafy
[rightish-leafy]
$ java kidsOfMatchTheseDays a
[]
Dlamblin
quelle
7

Schauen Sie sich nach dem Vorbild von Gareths Antwort DefaultMutableTreeNode an . Es ist nicht generisch, scheint aber ansonsten in die Rechnung zu passen. Obwohl es im Paket javax.swing enthalten ist, hängt es nicht von AWT- oder Swing-Klassen ab. Tatsächlich enthält der Quellcode den Kommentar// ISSUE: this class depends on nothing in AWT -- move to java.util?

Kennzeichen
quelle
Lol, wie bist du überhaupt auf diese Klasse gestoßen?
Pacerier
7

In Java gibt es einige Baumdatenstrukturen, z. B. DefaultMutableTreeNode in JDK Swing, Tree im Stanford-Parser-Paket und andere Spielzeugcodes. Aber keines davon ist ausreichend und doch klein genug für den allgemeinen Zweck.

Das Java-Tree- Projekt versucht, eine andere universelle Tree-Datenstruktur in Java bereitzustellen. Der Unterschied zwischen diesem und anderen ist

  • Total frei. Sie können es überall verwenden (außer in Ihren Hausaufgaben: P)
  • Klein aber fein genug. Ich habe die gesamte Datenstruktur in eine Klassendatei eingefügt, damit sie leicht kopiert / eingefügt werden kann.
  • Nicht nur ein Spielzeug. Mir sind Dutzende von Java-Baumcodes bekannt, die nur Binärbäume oder eingeschränkte Operationen verarbeiten können. Dieser TreeNode ist viel mehr als das. Es bietet verschiedene Möglichkeiten zum Besuchen von Knoten, z. B. Vorbestellung, Nachbestellung, Breite zuerst, Blätter, Pfad zur Wurzel usw. Darüber hinaus werden auch Iteratoren bereitgestellt, um die Berechtigung zu gewährleisten.
  • Weitere Utils werden hinzugefügt. Ich bin bereit, weitere Operationen hinzuzufügen, um dieses Projekt umfassend zu gestalten, insbesondere wenn Sie eine Anfrage über github senden.
Yifan Peng
quelle
5

Da in der Frage nach einer verfügbaren Datenstruktur gefragt wird, kann ein Baum aus Listen oder Arrays erstellt werden:

Object[] tree = new Object[2];
tree[0] = "Hello";
{
  Object[] subtree = new Object[2];
  subtree[0] = "Goodbye";
  subtree[1] = "";
  tree[1] = subtree;
}

instanceof kann verwendet werden, um zu bestimmen, ob ein Element ein Teilbaum oder ein Endknoten ist.

Olathe
quelle
2
Ziemlich hässlich. Und funktioniert nicht, wenn Ihre Datenobjekte Arrays bzw. Listen sein können.
user686249
1
Ich stimme zu, dass es hässlich ist. Das Objects wären entweder die Blattobjekte (zum Beispiel Strings) oder Zweige (dargestellt durch Arrays). Und es funktioniert: Dieser Code wird kompiliert und es wird ein kleiner Baum von Strings erstellt.
Olathe
5
public abstract class Node {
  List<Node> children;

  public List<Node> getChidren() {
    if (children == null) {
      children = new ArrayList<>();
    }
    return chidren;
  }
}

So einfach wie es nur geht und sehr einfach zu bedienen. Um es zu verwenden, erweitern Sie es:

public class MenuItem extends Node {
  String label;
  String href;
  ...
}
bretter
quelle
3

Beispielsweise :

import java.util.ArrayList;
import java.util.List;



/**
 * 
 * @author X2
 *
 * @param <T>
 */
public class HisTree<T> 
{
    private Node<T> root;

    public HisTree(T rootData) 
    {
        root = new Node<T>();
        root.setData(rootData);
        root.setChildren(new ArrayList<Node<T>>());
    }

}

class Node<T> 
{

    private T data;
    private Node<T> parent;
    private List<Node<T>> children;

    public T getData() {
        return data;
    }
    public void setData(T data) {
        this.data = data;
    }
    public Node<T> getParent() {
        return parent;
    }
    public void setParent(Node<T> parent) {
        this.parent = parent;
    }
    public List<Node<T>> getChildren() {
        return children;
    }
    public void setChildren(List<Node<T>> children) {
        this.children = children;
    }
}
JAN
quelle
3

In der Vergangenheit habe ich dafür gerade eine verschachtelte Karte verwendet. Dies ist, was ich heute benutze, es ist sehr einfach, aber es passt zu meinen Bedürfnissen. Vielleicht hilft das einem anderen.

import com.fasterxml.jackson.annotation.JsonValue;
import com.fasterxml.jackson.databind.ObjectMapper;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

/**
 * Created by kic on 16.07.15.
 */
public class NestedMap<K, V> {
    private final Map root = new HashMap<>();

    public NestedMap<K, V> put(K key) {
        Object nested = root.get(key);

        if (nested == null || !(nested instanceof NestedMap)) root.put(key, nested = new NestedMap<>());
        return (NestedMap<K, V>) nested;
    }

    public Map.Entry<K,V > put(K key, V value) {
        root.put(key, value);

        return (Map.Entry<K, V>) root.entrySet().stream().filter(e -> ((Map.Entry) e).getKey().equals(key)).findFirst().get();
    }

    public NestedMap<K, V> get(K key) {
        return (NestedMap<K, V>) root.get(key);
    }

    public V getValue(K key) {
        return (V) root.get(key);
    }

    @JsonValue
    public Map getRoot() {
        return root;
    }

    public static void main(String[] args) throws Exception {
        NestedMap<String, Integer> test = new NestedMap<>();
        test.put("a").put("b").put("c", 12);
        Map.Entry<String, Integer> foo = test.put("a").put("b").put("d", 12);
        test.put("b", 14);
        ObjectMapper mapper = new ObjectMapper();
        System.out.println(mapper.writeValueAsString(test));

        foo.setValue(99);
        System.out.println(mapper.writeValueAsString(test));

        System.out.println(test.get("a").get("b").getValue("d"));
    }
}
KIC
quelle
3

Ich habe eine kleine "TreeMap" -Klasse geschrieben, die auf "HashMap" basiert und das Hinzufügen von Pfaden unterstützt:

import java.util.HashMap;
import java.util.LinkedList;

public class TreeMap<T> extends LinkedHashMap<T, TreeMap<T>> {

    public void put(T[] path) {
        LinkedList<T> list = new LinkedList<>();
        for (T key : path) {
            list.add(key);
        }
        return put(list);
    }

    public void put(LinkedList<T> path) {
        if (path.isEmpty()) {
            return;
        }
        T key = path.removeFirst();
        TreeMap<T> val = get(key);
        if (val == null) {
            val = new TreeMap<>();
            put(key, val);
        }
        val.put(path);
    }

}

Es kann verwendet werden, um einen Baum von Dingen vom Typ "T" (generisch) zu speichern, unterstützt jedoch (noch) nicht das Speichern zusätzlicher Daten in seinen Knoten. Wenn Sie eine Datei wie diese haben:

root, child 1
root, child 1, child 1a
root, child 1, child 1b
root, child 2
root, child 3, child 3a

Dann können Sie daraus einen Baum machen, indem Sie Folgendes ausführen:

TreeMap<String> root = new TreeMap<>();
Scanner scanner = new Scanner(new File("input.txt"));
while (scanner.hasNextLine()) {
  root.put(scanner.nextLine().split(", "));
}

Und du wirst einen schönen Baum bekommen. Es sollte einfach sein, sich an Ihre Bedürfnisse anzupassen.

mevdschee
quelle
2

Sie können die in Apache JMeter enthaltene HashTree- Klasse verwenden, die Teil des Jakarta-Projekts ist.

Die HashTree-Klasse ist im Paket org.apache.jorphan.collections enthalten. Obwohl dieses Paket nicht außerhalb des JMeter-Projekts veröffentlicht wurde, können Sie es einfach herunterladen:

1) Laden Sie die JMeter-Quellen herunter .

2) Erstellen Sie ein neues Paket.

3) Kopieren Sie darauf / src / jorphan / org / apache / jorphan / collection /. Alle Dateien außer Data.java

4) Kopieren Sie auch /src/jorphan/org/apache/jorphan/util/JOrphanUtils.java

5) HashTree ist einsatzbereit.

David
quelle
2

In Java gibt es keine spezifische Datenstruktur, die Ihren Anforderungen entspricht. Ihre Anforderungen sind sehr spezifisch und dafür müssen Sie Ihre eigene Datenstruktur entwerfen. Wenn Sie sich Ihre Anforderungen ansehen, kann jeder sagen, dass Sie eine Art Baum mit einer bestimmten Funktionalität benötigen. Sie können Ihre Datenstruktur folgendermaßen gestalten:

  1. Die Struktur des Knotens des Baums entspricht dem Inhalt des Knotens und der Liste der untergeordneten Elemente wie folgt: class Node {String value; Kinder auflisten;}
  2. Sie müssen die untergeordneten Elemente einer bestimmten Zeichenfolge abrufen, damit Sie zwei Methoden verwenden können. 1: Node searchNode (String str) gibt den Knoten zurück, der denselben Wert wie die angegebene Eingabe hat (verwenden Sie BFS für die Suche). 2: List getChildren (String) str): Diese Methode ruft intern den searchNode auf, um den Knoten mit derselben Zeichenfolge abzurufen. Anschließend wird die Liste aller Zeichenfolgenwerte von untergeordneten Elementen erstellt und zurückgegeben.
  3. Sie müssen auch eine Zeichenfolge in den Baum einfügen. Sie müssen eine Methode schreiben, z. B. void insert (String parent, String value): Dadurch wird erneut der Knoten durchsucht, dessen Wert gleich parent ist. Anschließend können Sie einen Knoten mit einem bestimmten Wert erstellen und der Liste der untergeordneten Elemente zum gefundenen übergeordneten Knoten hinzufügen .

Ich würde vorschlagen, dass Sie die Struktur des Knotens in einer Klasse wie Class Node {String value; Listen Sie untergeordnete Elemente;} und alle anderen Methoden wie search, insert und getChildren in einer anderen NodeUtils-Klasse auf, damit Sie auch die Wurzel des Baums übergeben können, um eine Operation für einen bestimmten Baum auszuführen, z. B.: Class NodeUtils {public static Node search (Knotenwurzel, String-Wert) {// BFS ausführen und Node zurückgeben}

Aman Rastogi
quelle
2
    // TestTree.java
// A simple test to see how we can build a tree and populate it
//
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.tree.*;

public class TestTree extends JFrame {

  JTree tree;
  DefaultTreeModel treeModel;

  public TestTree( ) {
    super("Tree Test Example");
    setSize(400, 300);
    setDefaultCloseOperation(EXIT_ON_CLOSE);
  }

  public void init( ) {
    // Build up a bunch of TreeNodes. We use DefaultMutableTreeNode because the
    // DefaultTreeModel can use it to build a complete tree.
    DefaultMutableTreeNode root = new DefaultMutableTreeNode("Root");
    DefaultMutableTreeNode subroot = new DefaultMutableTreeNode("SubRoot");
    DefaultMutableTreeNode leaf1 = new DefaultMutableTreeNode("Leaf 1");
    DefaultMutableTreeNode leaf2 = new DefaultMutableTreeNode("Leaf 2");

    // Build our tree model starting at the root node, and then make a JTree out
    // of it.
    treeModel = new DefaultTreeModel(root);
    tree = new JTree(treeModel);

    // Build the tree up from the nodes we created.
    treeModel.insertNodeInto(subroot, root, 0);
    // Or, more succinctly:
    subroot.add(leaf1);
    root.add(leaf2);

    // Display it.
    getContentPane( ).add(tree, BorderLayout.CENTER);
  }

  public static void main(String args[]) {
    TestTree tt = new TestTree( );
    tt.init( );
    tt.setVisible(true);
  }
}
Tony Narloch
quelle
3
Bitte geben Sie nicht nur Code aus - erklären Sie, was er tut und insbesondere, warum er sich unterscheidet (besser ist) als alle anderen Antworten.
Jan Doggen
2

Ich habe eine Baumbibliothek geschrieben, die gut mit Java8 funktioniert und keine anderen Abhängigkeiten aufweist. Es bietet auch eine lose Interpretation einiger Ideen aus der funktionalen Programmierung und ermöglicht das Zuordnen / Filtern / Beschneiden / Durchsuchen des gesamten Baums oder der Teilbäume.

https://github.com/RutledgePaulV/prune

Die Implementierung macht nichts Besonderes mit der Indizierung und ich bin nicht von der Rekursion abgewichen. Daher ist es möglich, dass sich die Leistung bei großen Bäumen verschlechtert und Sie den Stapel sprengen können. Aber wenn Sie nur einen einfachen Baum von kleiner bis mittlerer Tiefe benötigen, funktioniert er meiner Meinung nach gut genug. Es bietet eine vernünftige (wertebasierte) Definition von Gleichheit und eine toString-Implementierung, mit der Sie den Baum visualisieren können!

RutledgePaulV
quelle
1

Bitte überprüfen Sie den folgenden Code, in dem ich Tree-Datenstrukturen verwendet habe, ohne Collection-Klassen zu verwenden. Der Code kann Fehler / Verbesserungen aufweisen, aber bitte verwenden Sie diesen nur als Referenz

package com.datastructure.tree;

public class BinaryTreeWithoutRecursion <T> {

    private TreeNode<T> root;


    public BinaryTreeWithoutRecursion (){
        root = null;
    }


    public void insert(T data){
        root =insert(root, data);

    }

    public TreeNode<T>  insert(TreeNode<T> node, T data ){

        TreeNode<T> newNode = new TreeNode<>();
        newNode.data = data;
        newNode.right = newNode.left = null;

        if(node==null){
            node = newNode;
            return node;
        }
        Queue<TreeNode<T>> queue = new Queue<TreeNode<T>>();
        queue.enque(node);
        while(!queue.isEmpty()){

            TreeNode<T> temp= queue.deque();
            if(temp.left!=null){
                queue.enque(temp.left);
            }else
            {
                temp.left = newNode;

                queue =null;
                return node;
            }
            if(temp.right!=null){
                queue.enque(temp.right);
            }else
            {
                temp.right = newNode;
                queue =null;
                return node;
            }
        }
        queue=null;
        return node; 


    }

    public void inOrderPrint(TreeNode<T> root){
        if(root!=null){

            inOrderPrint(root.left);
            System.out.println(root.data);
            inOrderPrint(root.right);
        }

    }

    public void postOrderPrint(TreeNode<T> root){
        if(root!=null){

            postOrderPrint(root.left);

            postOrderPrint(root.right);
            System.out.println(root.data);
        }

    }

    public void preOrderPrint(){
        preOrderPrint(root);
    }


    public void inOrderPrint(){
        inOrderPrint(root);
    }

    public void postOrderPrint(){
        inOrderPrint(root);
    }


    public void preOrderPrint(TreeNode<T> root){
        if(root!=null){
            System.out.println(root.data);
            preOrderPrint(root.left);
            preOrderPrint(root.right);
        }

    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        BinaryTreeWithoutRecursion <Integer> ls=  new BinaryTreeWithoutRecursion <>();
        ls.insert(1);
        ls.insert(2);
        ls.insert(3);
        ls.insert(4);
        ls.insert(5);
        ls.insert(6);
        ls.insert(7);
        //ls.preOrderPrint();
        ls.inOrderPrint();
        //ls.postOrderPrint();

    }

}
Amit Mathur
quelle
2
" ohne Sammlungsklassen zu verwenden " Ah? Woher kommt also die Queue-Klasse? Und wie oben erwähnt, handelt es sich um einen Binärbaum, der bei der ersten Anforderung fehlschlägt (beliebig viele untergeordnete Knoten).
PhiLho
1

Sie können die TreeSet-Klasse in java.util verwenden. *. Es funktioniert wie ein binärer Suchbaum, ist also bereits sortiert. Die TreeSet-Klasse implementiert Iterable-, Collection- und Set-Schnittstellen. Sie können den Baum mit einem Iterator wie eine Menge durchlaufen.

TreeSet<String> treeSet = new TreeSet<String>();
Iterator<String> it  = treeSet.Iterator();
while(it.hasNext()){
...
}

Sie können Java Doc und einige andere überprüfen .

Oguz
quelle
-1

Benutzerdefiniertes Tree-Implementieren von Tree ohne Verwendung des Collection-Frameworks. Es enthält verschiedene grundlegende Operationen, die für die Tree-Implementierung erforderlich sind.

class Node {

    int data;
    Node left;
    Node right;

    public Node(int ddata, Node left, Node right) {
        this.data = ddata;
        this.left = null;
        this.right = null;      
    }

    public void displayNode(Node n) {
        System.out.print(n.data + " "); 
    }

}

class BinaryTree {

    Node root;

    public BinaryTree() {
        this.root = null;
    }

    public void insertLeft(int parent, int leftvalue ) {
        Node n = find(root, parent);
        Node leftchild = new Node(leftvalue, null, null);
        n.left = leftchild;
    }

    public void insertRight(int parent, int rightvalue) {
        Node n = find(root, parent);
        Node rightchild = new Node(rightvalue, null, null);
        n.right = rightchild;
    }

    public void insertRoot(int data) {
        root = new Node(data, null, null);
    }

    public Node getRoot() {
        return root;
    }

    public Node find(Node n, int key) {     
        Node result = null;

        if (n == null)
            return null;

        if (n.data == key)
            return n;

        if (n.left != null)
            result = find(n.left, key);

        if (result == null)
            result = find(n.right, key);

        return result;
    } 

    public int getheight(Node root){
        if (root == null)
            return 0;

        return Math.max(getheight(root.left), getheight(root.right)) + 1; 
    }

    public void printTree(Node n) {     
        if (n == null)
            return;

        printTree(n.left);
        n.displayNode(n);
        printTree(n.right);             
    }

}
Shivam Verma
quelle
11
Das ist ein binärer Baum, der bei der ersten Anforderung des OP
fehlschlägt