Structure de données Java tree? [fermé]

Ici:

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

C'est une structure arborescente de base qui peut être utilisée pour String ou tout autre objet. Il est assez facile d'implémenter des arbres simples pour faire ce dont vous avez besoin.

Tout ce que vous devez ajouter sont des méthodes pour ajouter, supprimer, traverser et les constructeurs. Le Node est le bloc de construction de base du Tree.

Encore une autre structure arborescente:

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

}

Exemple d'utilisation:

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
Voir l'arbre à part entière avec:

• itérateur
• recherche
• Java/C #

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

Il y a en fait une assez bonne structure arborescente implémentée dans le JDK.

Jetez un oeil à javax.swing.arbre, Il s'agit d'un modèle d'arbre, et de TreeNode. Ils sont conçus pour être utilisés avec le JTreePanel mais ils sont, en fait, une assez bonne implémentation d'arbre et rien ne vous empêche de l'utiliser sans une interface swing.

Notez qu'à partir de Java 9, vous pouvez ne pas utiliser ces classes car elles ne seront pas présentes dans les 'Profils compacts'.

Qu'en est-il de cela?

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

I a écrit une petite bibliothèque qui gère les génériques des arbres. C'est beaucoup plus léger que le swing. J'ai aussi un projet maven pour elle.

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

Évidemment, vous pouvez ajouter des méthodes utilitaires pour ajouter/supprimer des enfants.

Vous devriez commencer par définir ce qu'est un arbre (pour le domaine), ceci est mieux fait en définissant d'abord l'interface . Toutes les structures d'arbres ne sont pas modifiables, être capable de ajouter et supprimer les nœuds devrait être une fonctionnalité facultative, nous faisons donc une interface supplémentaire pour cela.

Il n'est pas nécessaire de créer des objets node qui contiennent les valeurs, en fait, je vois cela comme un défaut de conception majeur et une surcharge dans la plupart des implémentations d'arborescence. Si vous regardez Swing, le TreeModel est libre de classes de nœuds (seulement DefaultTreeModel utilise TreeNode), car elles ne sont pas vraiment nécessaires.

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

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

Compte tenu de ces interfaces, le code qui utilise des arbres n'a pas à se soucier beaucoup de la façon dont l'arbre est implémenté. Cela vous permet d'utiliser implémentations génériquesainsi que spécialisées, où vous réalisez l'arborescence en déléguant des fonctions à une autre API.
Exemple: Arborescence de fichiers.

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

    public static void main(String[] args) {

        MutableTree<String> tree = new MappedTreeStructure<String>();
        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<N, N>();
    private final LinkedHashSet<N> nodeList = new LinkedHashSet<N>();

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

Vous pouvez utiliser n'importe quelle API XML de Java comme document et Node..as XML est une structure arborescente avec des chaînes

Aucune réponse ne mentionne un code trop simplifié mais fonctionnel, donc le voici:

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

Il existe quelques structures de données arborescentes en Java, telles que DefaultMutableTreeNode dans JDK Swing, Tree dans Stanford parser package et d'autres codes toy. Mais aucun d'entre eux n'est suffisant mais assez petit pour un usage général.

Le projet Java-tree tente de fournir une autre structure de données arborescente à usage général en Java. La différence entre ceci et d'autres sont

• Totalement gratuit. Vous pouvez l'utiliser n'importe où (sauf dans vos devoirs: P)
• Petit mais général assez. J'ai mis tout de la structure de données dans un fichier de classe, il serait donc facile de copier / coller.
• Pas seulement un jouet. Je connais des dizaines de codes d'arborescence Java qui ne peuvent gérer que des arbres binaires ou des opérations limitées. Ce TreeNode est beaucoup plus que cela. Il offre différentes façons de visiter les nœuds, comme précommande, postorder, breadthfirst, les feuilles, la racine, etc. De plus, des itérateurs sont également fournis pour la suffisance.
• D'autres utils seront ajoutés. Je suis prêt à ajouter plus d'opérations pour rendre ce projet complet, surtout si vous envoyez une demande via github.

Dans le même sens que la réponse de Gareth, consultez DefaultMutableTreeNode. Ce n'est pas générique, mais sinon semble correspondre à la facture. Même si c'est dans le javax.paquet swing, il ne dépend d'aucune classe AWT ou Swing. En fait, le code source a en fait le commentaire // ISSUE: this class depends on nothing in AWT -- move to java.util?

Si vous faites du codage sur tableau blanc, une interview ou même si vous envisagez simplement d'utiliser un arbre, la verbosité de tout cela est un peu beaucoup.

Il faut en outre dire que la raison pour laquelle un arbre n'est pas là comme, disons, un Pair (à propos duquel la même chose pourrait être dite), est parce que vous devriez encapsuler vos données dans la classe en l'utilisant, et {[10] } l'implémentation la plus simple ressemble à:

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

C'est vraiment ça pour un arbre de largeur arbitraire.

Si vous vouliez un binaire arbre il est souvent plus facile à utiliser avec les champs nommés:

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

Ou si vous vouliez un trie:

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

Maintenant, vous avez dit que vous voulez

Pour pouvoir obtenir tous les enfants (une sorte de liste ou de tableau de chaînes) étant donné une chaîne d'entrée représentant un nœud donné

Cela ressemble à vos devoirs.
Mais comme je suis raisonnablement sûr que toute date limite est maintenant passée {

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

Cela vous permet d'utiliser comme:

$ 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
[]

Puisque la question demande une structure de données disponible, un arbre peut être construit à partir de listes ou de tableaux:

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

instanceof peut être utilisé pour déterminer si un élément est un sous-arbre ou un nœud terminal.

public abstract class Node {
  List<Node> children;

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

Aussi simple que possible et très facile à utiliser. Pour l'utiliser, étendez-le:

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

Par exemple :

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

Vous pouvez utiliser la classe HashTree incluse dans Apache JMeter qui fait partie du projet Jakarta.

La classe HashTree est incluse dans l'organisation du paquet.Apache.jorphan.collection. Bien que ce paquet ne soit pas publié en dehors du projet JMeter, vous pouvez l'obtenir facilement:

1) Téléchargez les sources JMeter.

2) Créez un nouveau paquet.

3) Copie sur elle /src/jorphan/org/apache/jorphan/collections/ . Tous les fichiers à l'exception des Données.java

4) Copier aussi /src/jorphan/org/apache/jorphan/util/JOrphanUtils.java

5) HashTree est prêt à l'emploi.

Veuillez vérifier le code ci-dessous, où j'ai utilisé des structures de données arborescentes, sans utiliser de classes de collection. Le code peut avoir des bugs / améliorations mais veuillez l'utiliser juste pour référence

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

    }

}

Il n'y a pas de structure de données spécifique en Java qui convient à vos besoins. Vos exigences sont assez spécifiques et pour cela, vous devez concevoir votre propre structure de données. En regardant vos besoins, tout le monde peut dire que vous avez besoin d'une sorte d'arbre n-ary avec des fonctionnalités spécifiques. Vous pouvez concevoir votre structure de données de la manière suivante:

1. Structure du nœud de l'arbre est contenu dans le nœud et la liste des enfants comme: la classe Node { Chaîne de valeur; Liste enfants;}
2. Vous devez récupérer les enfants d'une chaîne donnée, vous pouvez donc avoir 2 méthodes 1: Node searchNode(String str), retournera le nœud qui a la même valeur que l'entrée donnée (utilisez BFS pour la recherche) 2: List getChildren(String str): cette méthode appellera en interne le searchNode pour obtenir le nœud ayant la même chaîne, puis elle créera la liste de toutes les valeurs de chaîne des enfants et retournera.
3. Vous devrez également insérer une chaîne dans l'arborescence. Vous devrez écrire une méthode dit void insert (String parent, String value): cela recherchera à nouveau le nœud ayant une valeur égale à parent, puis vous pourrez créer un nœud avec une valeur donnée et ajouter à la liste des enfants au parent trouvé.

Je suggère que vous écriviez la structure du nœud dans une classe comme Class Node { String value; List children;} et toutes les autres méthodes comme search, insert et getChildren dans une autre classe NodeUtils afin que vous puissiez également passer la racine de l'arbre pour effectuer une opération sur arbre spécifique comme: classe NodeUtils{ public static Nœud de recherche(Nœud racine, String valeur){// exécution de la BFS et retour Nœud}

Dans le passé, je viens d'utiliser une carte imbriquée pour cela. C'est ce que j'utilise aujourd'hui, c'est très simple, mais il correspond à mes besoins. Peut-être que cela aidera à un autre.

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

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

J'ai écrit une bibliothèque d'arbres qui joue bien avec Java8 et qui n'a pas d'autres dépendances. Il fournit également une interprétation lâche de certaines idées de la programmation fonctionnelle et vous permet de mapper/filtrer/élaguer/rechercher l'ensemble de l'arbre ou des sous-arbres.

Https://github.com/RutledgePaulV/prune

L'implémentation ne fait rien de spécial avec l'indexation et je ne me suis pas éloigné de la récursivité, il est donc possible qu'avec de grands arbres les performances se dégradent et que vous puissiez souffler pile. Mais si tout ce dont vous avez besoin est un arbre simple de petite à moyenne profondeur, je pense que cela fonctionne assez bien. Il fournit une définition saine (basée sur la valeur) de l'égalité et il a également une implémentation toString qui vous permet de visualiser l'arbre!

Vous pouvez utiliser la classe TreeSet en java.util.*. Il fonctionne comme un arbre de recherche binaire, il est donc déjà trié. La classe TreeSet implémente les interfaces Itérables, Collection et Set. Vous pouvez traverser l'arbre avec l'itérateur comme un ensemble.

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

, Vous pouvez vérifier, Java Doc et des autres .

J'ai écrit une petite classe "TreeMap" basée sur "HashMap" qui prend en charge l'ajout de chemins:

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

}

Il peut être utilisé pour stocker un arbre de choses de type "T" (générique), mais ne prend pas (encore) en charge le stockage de données supplémentaires dans ses nœuds. Si vous avez un fichier comme celui-ci:

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

Ensuite, vous pouvez en faire un arbre en exécutant:

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

Et vous obtiendrez un bel arbre. Il devrait être facile de s'adapter à vos besoins.

Implémentation d'Arborescence personnalisée de l'Arborescence sans utiliser le framework de collection. Il contient différentes opérations fondamentales nécessaires dans l'implémentation de l'arbre.

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

}