¿Cómo implementar una estructura de datos de árbol en Java? [cerrado]

496

¿Hay alguna clase de biblioteca Java estándar para representar un árbol en Java?

Específicamente necesito representar lo siguiente:

  • El subárbol en cualquier nodo puede tener un número arbitrario de hijos
  • Cada nodo (después de la raíz) y sus hijos tendrán un valor de cadena
  • Necesito obtener todos los elementos secundarios (algún tipo de lista o conjunto de cadenas) de un nodo dado y su valor de cadena (es decir, un método que tomará un nodo como entrada y devolverá todos los valores de cadena del nodo secundario como salida)

¿Hay alguna estructura disponible para esto o necesito crear la mía propia (si es así, las sugerencias de implementación serían geniales)?

ikl
fuente
3
Si está utilizando Java 8, y le gustaría atravesar sus nodos con flujos, filtros, etc. entonces es posible que desee echar un vistazo a Durian github.com/diffplug/durian
Ned Twigg
1
Puede utilizar esta API: sourceforge.net/p/treeds4j
Mohamed Ennahdi El Idrissi

Respuestas:

306

Aquí:

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

Esa es una estructura de árbol básica que se puede usar para Stringcualquier otro objeto. Es bastante fácil implementar árboles simples para hacer lo que necesita.

Todo lo que necesita agregar son métodos para agregar, eliminar, atravesar y constructores. El Nodees el bloque de construcción básico de la Tree.

jjnguy
fuente
304
Estrictamente hablando, la Treeclase no es necesaria, porque cada una de ellas Nodepuede verse como un árbol.
Joachim Sauer
34
@Joa, me gusta tener una estructura para contener la raíz. Puede agregar métodos a la clase de árbol que tengan más sentido llamar a un árbol en lugar de a un solo nodo.
jjnguy
24
@Justin: por ejemplo? Esa es una pregunta honesta: no puedo pensar en un solo método que tenga sentido en todo el árbol que no tiene sentido en un subárbol.
Joachim Sauer
22
Estoy de acuerdo con @Joa en que la clase Tree no es necesaria. Prefiero dejar explícita la naturaleza recursiva de los árboles en el código al no agregar una clase de árbol separada y usar consistentemente la clase Node. En cambio, llamo a una variable 'árbol' o 'raíz' si es necesario aclarar que se trata del Nodo raíz de un árbol.
jvdbogae
89
@Joa Un yo de cuatro años está completamente de acuerdo contigo. Nix la clase del árbol.
jjnguy
122

Otra estructura de árbol más:

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 ...

}

Uso de la muestra:

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

BONIFICACIÓN
Ver árbol de pleno derecho con:

  • iterador
  • buscando
  • Java / C #

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

Grzegorz Dev
fuente
2
Acabo de encontrar su biblioteca extremadamente útil. Gracias. Pero me gustaría saber cómo implementar dinámicamente poblar la estructura de árbol en función de la relación de referencia entre padre e hijo. El ejemplo dado es que tengo un miembro1 patrocinador de otro miembro2, y miembro2 patrocinador del miembro 3 y así sucesivamente. Ya tengo la relación de registros de la tabla, pero no estoy seguro de poder rellenarlos en un árbol usando su biblioteca.
d4v1dv00
1
a partir del año 2016, el enlace no contiene archivos de origen o descargas
Sharon Ben Asher
2
En mi opinión, esta respuesta tres años después de la respuesta mejor calificada anterior, es la más limpia. Sin embargo, reemplazaría la LinkedList con una ArrayList para this.children.
HopeKing
1
Yo usaría un Set para los niños.
DPM
Podría estar equivocado, pero parece que con esta implementación, debe llamar hasNext()antes de cada llamada next()para obtener resultados válidos. Esto no es parte de la Iteratorespecificación.
Robert Lewis
97

En realidad, hay una estructura de árbol bastante buena implementada en el JDK.

Echa un vistazo a javax.swing.tree , TreeModel y TreeNode . Están diseñados para ser utilizados con el JTreePanelpero son, de hecho, una implementación de árbol bastante buena y no hay nada que lo detenga de usarlo sin una interfaz de swing.

Tenga en cuenta que a partir de Java 9 es posible que no desee utilizar estas clases, ya que no estarán presentes en los 'Perfiles compactos' .

Gareth Davis
fuente
55
Sí, los usé en el pasado, y harán todo lo que quieras de un árbol. El único inconveniente que se me ocurre es la longitud de los nombres de sus respectivas clases de implementación: DefaultTreeModel y DefaultMutableTreeNode. Detallado, pero no es que sea tan importante, supongo.
Ultimate Gobblement
44
Una buena manera de lidiar con eso es crear un par de métodos estáticos newModel () y newNode () y luego importarlos estáticamente.
Gareth Davis el
140
Evitaría usar bibliotecas Swing en funciones no relacionadas con Swing. Esta es una mala práctica de codificación . Nunca se sabe cómo Swing implementa sus árboles, cuáles son sus dependencias y cómo esto podría cambiar en el futuro. Swing no es una biblioteca de utilidades sino una biblioteca de IU.
jasop
44
Creo que la mala práctica de codificación es un poco dura.
Gareth Davis
51
javax.swing.tree.TreeModel es una interfaz pública (exactamente como java.util.List) y no tendrá cambios incompatibles. Una ventaja adicional es que puede depurar / visualizar fácilmente su árbol mientras se desarrolla.
lbalazscs
45

¿Qué hay de esto?

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
fuente
55
¿Cómo se implementaría DFS en un árbol creado con este objeto de clase?
leba-lev
3
¿Cómo se implementaría la eliminación de una hoja usando esta clase?
ghedas
2
¿Para qué se usaría el campo de cabecera?
Acour83
2
Hubiera sido genial si esta clase tuviera algo de documentación. No entiendo qué métodos les gusta setAsParento getHeadqué hacen y este es el momento en que realmente podría obtener ayuda sobre las estructuras de datos de árbol. Incluso la fuente original del documento no tiene comentarios.
disasterkid
23

Yo escribí una pequeña biblioteca que se encarga de árboles genéricos. Es mucho más ligero que el material de swing. También tengo un proyecto maven para ello.

Vivin Paliath
fuente
3
Lo estoy usando ahora, funciona de manera brillante. Tuve que cambiar la fuente significativamente para mis propias personalizaciones, pero fue un excelente punto de partida. Gracias 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;
    }
}

Obviamente, puede agregar métodos de utilidad para agregar / eliminar hijos.

PaulJWilliams
fuente
1
Esto sugiere que el padre de un árbol es un árbol. Creo que estabas intentando crear una clase de nodo de árbol.
Madhur Bhargava
16

Debe comenzar definiendo qué es un árbol (para el dominio), esto se hace mejor definiendo primero la interfaz . No todas las estructuras de árboles son modificables, poder agregar y eliminar nodos debería ser una característica opcional, por lo que creamos una interfaz adicional para eso.

No hay necesidad de crear objetos de nodo que contengan los valores , de hecho, veo esto como un gran defecto de diseño y sobrecarga en la mayoría de las implementaciones de árbol. Si observa Swing, TreeModelestá libre de clases de nodos (solo DefaultTreeModelusa TreeNode), ya que no son realmente necesarias.

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

Estructura de árbol mutable (permite agregar y eliminar nodos):

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

Dadas estas interfaces, el código que usa árboles no tiene que preocuparse mucho por cómo se implementa el árbol. Esto le permite utilizar implementaciones genéricas , así como también especializadas , en las que se da cuenta del árbol delegando funciones a otra API.

Ejemplo: estructura de árbol de archivos

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

Ejemplo: estructura de árbol genérica (basada en relaciones padre / hijo):

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
fuente
1
Me enfrento a un problema cuando sigo esta estructura cuando hago tree.add ("A", "B"); tree.add ("A", "C"); tree.add ("C", "D"); tree.add ("E", "A"); E es padre de A ¿Cómo hacemos para hacer esto?
saNiks
1
Hola saNicks, hubo un error en el código anterior que causó que no se agregara la última relación. Ahora está arreglado, y también agregué verificaciones no nulas y (más importante): verificaciones cíclicas que evitan violar la estructura de árbol (agregar un código o uno de sus antepasados ​​como un niño a sí mismo). ¡Gracias por la pista!
Peter Walser
1
Solucioné el error si alguien está buscando una solución para ese error, lo que debe hacer es ver si el método add devuelve falso y si es falso solo cree un nuevo LinkedHashSet <N> temporal y clone la lista de nodos del árbol en él, entonces puede borrar el árbol, agregue el nodo padre que no se agregó en el paso anterior y luego agregue Todos los tempNode nuevamente al árbol padre ... ¡Gracias por la estructura!
saNiks
2
Simplemente elimine esos modificadores públicos inútiles de sus interfaces.
Hamedz
1
¿Cómo puedo generar una matriz json de esto?
Pawan Pandey
12

Ninguna respuesta menciona un código demasiado simplificado pero que funciona, así que aquí está:

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

Puede usar cualquier API XML de Java como documento y nodo ... ya que XML es una estructura de árbol con cadenas

Raja Nagendra Kumar
fuente
55
excelente idea, podríamos usar en memoria un esquema XML usando dom4j + jaxen xpath para buscar nodos.
Ben Rhouma Zied
8

Si está haciendo una codificación de pizarra, una entrevista o incluso planea usar un árbol, la verbosidad de estos es un poco demasiado.

Además, debe decirse que la razón por la que un árbol no está allí, como, digamos, un Pair(sobre el cual podría decirse lo mismo), es porque debe encapsular sus datos en la clase usándolo, y la implementación más simple se ve así:

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

Eso es todo para un árbol de ancho arbitrario.

Si quería un árbol binario, a menudo es más fácil de usar con campos con nombre:

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

O si querías un trie:

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

Ahora dijiste que quieres

para poder obtener todos los elementos secundarios (algún tipo de lista o conjunto de cadenas) dada una cadena de entrada que representa un nodo dado

Eso suena como tu tarea.
Pero como estoy razonablemente seguro de que ha pasado cualquier fecha límite ...

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

Esto te hace usar como:

$ 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
fuente
7

En la misma línea que la respuesta de Gareth, consulte DefaultMutableTreeNode . No es genérico, pero por lo demás parece encajar. Aunque está en el paquete javax.swing, no depende de ninguna clase de AWT o Swing. De hecho, el código fuente tiene el comentario// ISSUE: this class depends on nothing in AWT -- move to java.util?

marca
fuente
Lol, ¿cómo te encontraste con esta clase?
Pacerier
7

Hay un par de estructuras de datos de árbol en Java, como DefaultMutableTreeNode en JDK Swing, Tree en el paquete del analizador Stanford y otros códigos de juguetes. Pero ninguno de estos es suficiente pero lo suficientemente pequeño para fines generales.

El proyecto de árbol de Java intenta proporcionar otra estructura de datos de árbol de propósito general en Java. La diferencia entre este y otros son

  • Totalmente libre. Puedes usarlo en cualquier lugar (excepto en tu tarea: P)
  • Pequeño pero lo suficientemente general. Puse toda la estructura de datos en un archivo de clase, por lo que sería fácil copiar / pegar.
  • No solo un juguete. Soy consciente de docenas de códigos de árbol Java que solo pueden manejar árboles binarios u operaciones limitadas. Este TreeNode es mucho más que eso. Proporciona diferentes formas de visitar nodos, como preordenar, postorder, amplitud, hojas, ruta a la raíz, etc. Además, también se proporcionan iteradores para la suficiencia.
  • Se agregarán más utilidades. Estoy dispuesto a agregar más operaciones para hacer que este proyecto sea integral, especialmente si envía una solicitud a través de github.
Yifan Peng
fuente
5

Como la pregunta solicita una estructura de datos disponible, se puede construir un árbol a partir de listas o matrices:

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

instanceof se puede usar para determinar si un elemento es un subárbol o un nodo terminal.

Olathe
fuente
2
Bastante feo. Y no funciona, si sus objetos de datos pueden ser matrices, respectivamente listas.
user686249
1
Estoy de acuerdo en que es feo. Los Objects serían los objetos hoja (por ejemplo, Strings) o ramas (representados por matrices). Y funciona: ese código se compilará y creará un pequeño árbol de Strings.
Olathe
5
public abstract class Node {
  List<Node> children;

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

Tan simple como se pone y muy fácil de usar. Para usarlo, extiéndelo:

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

Por ejemplo :

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;
    }
}
ENE
fuente
3

En el pasado, acabo de usar un mapa anidado para esto. Esto es lo que uso hoy, es muy simple pero se ajusta a mis necesidades. Quizás esto ayude a otro.

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
fuente
3

Escribí una pequeña clase "TreeMap" basada en "HashMap" que admite agregar rutas:

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

}

Se puede usar para almacenar un árbol de cosas del tipo "T" (genérico), pero (todavía) no admite el almacenamiento de datos adicionales en sus nodos. Si tiene un archivo como este:

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

Luego puedes convertirlo en un árbol ejecutando:

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

Y obtendrás un bonito árbol. Debería ser fácil adaptarse a sus necesidades.

mevdschee
fuente
2

Puedes usar el HashTree clase incluida en Apache JMeter que es parte del Proyecto Jakarta.

La clase HashTree se incluye en el paquete org.apache.jorphan.collections. Aunque este paquete no se publica fuera del proyecto JMeter, puede obtenerlo fácilmente:

1) Descargue las fuentes de JMeter .

2) Crear un nuevo paquete.

3) Copie en él / src / jorphan / org / apache / jorphan / collections /. Todos los archivos excepto Data.java

4) Copie también /src/jorphan/org/apache/jorphan/util/JOrphanUtils.java

5) HashTree está listo para usar.

David
fuente
2

No existe una estructura de datos específica en Java que se adapte a sus requisitos. Sus requisitos son bastante específicos y para eso necesita diseñar su propia estructura de datos. Mirando sus requisitos, cualquiera puede decir que necesita algún tipo de árbol n-ary con alguna funcionalidad específica. Puede diseñar su estructura de datos de la siguiente manera:

  1. La estructura del nodo del árbol sería como contenido en el nodo y una lista de elementos secundarios como: class Node {String value; Lista de niños;}
  2. Debe recuperar los elementos secundarios de una cadena dada, por lo que puede tener 2 métodos 1: Node searchNode (String str), devolverá el nodo que tiene el mismo valor que la entrada dada (use BFS para buscar) 2: List getChildren (String str): este método llamará internamente al searchNode para que el nodo tenga la misma cadena y luego creará la lista de todos los valores de cadena de los elementos secundarios y regresará.
  3. También se le pedirá que inserte una cadena en el árbol. Tendrá que escribir un método, digamos void insert (String parent, String value): esto buscará nuevamente el nodo que tenga un valor igual a parent y luego puede crear un Nodo con el valor dado y agregarlo a la lista de hijos al padre encontrado .

Sugeriría que escriba la estructura del nodo en una clase como Class Node {String value; Enumere children;} y todos los demás métodos como search, insert y getChildren en otra clase NodeUtils para que también pueda pasar la raíz del árbol para realizar operaciones en un árbol específico como: class NodeUtils {búsqueda de nodo público estático (raíz de nodo, valor de cadena) {// realiza BFS y devuelve el nodo}

aman rastogi
fuente
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
fuente
3
Por favor, no solo descargue el código, explique lo que hace, y especialmente por qué difiere (es mejor) que todas las otras respuestas.
Jan Doggen
2

Escribí una biblioteca de árbol que juega muy bien con Java8 y que no tiene otras dependencias. También proporciona una interpretación flexible de algunas ideas de la programación funcional y le permite mapear / filtrar / podar / buscar en todo el árbol o subárboles.

https://github.com/RutledgePaulV/prune

La implementación no hace nada especial con la indexación y no me alejé de la recursión, por lo que es posible que con árboles grandes el rendimiento se degrade y pueda volar la pila. Pero si todo lo que necesita es un árbol sencillo de profundidad pequeña a moderada, creo que funciona lo suficientemente bien. ¡Proporciona una definición sensata (basada en el valor) de igualdad y también tiene una implementación toString que le permite visualizar el árbol!

RutledgePaulV
fuente
1

Verifique el código a continuación, donde he usado estructuras de datos de árbol, sin usar clases de colección. El código puede tener errores / mejoras, pero use esto solo como referencia

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
fuente
2
" sin usar clases de colección " Ah? Entonces, ¿de dónde viene la clase Queue? Y como se dijo anteriormente, es un árbol binario, que falla al primer requisito (cualquier número de nodos hijos).
PhiLho
1

Puede usar la clase TreeSet en java.util. *. Funciona como un árbol de búsqueda binario, por lo que ya está ordenado. La clase TreeSet implementa las interfaces Iterable, Collection y Set. Puede atravesar el árbol con un iterador como un conjunto.

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

Puedes consultar, Java Doc y algunos otros .

Oguz
fuente
-1

Implementación personalizada de Tree sin utilizar el marco de la Colección. Contiene diferentes operaciones fundamentales necesarias en la implementación de Tree.

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
fuente
11
Es un árbol binario, falla en el primer requisito del OP ...
PhiLho