Como implementar uma estrutura de dados em árvore em Java? [fechadas]

496

Existe alguma classe de biblioteca Java padrão para representar uma árvore em Java?

Especificamente, preciso representar o seguinte:

  • A subárvore em qualquer nó pode ter um número arbitrário de filhos
  • Cada nó (após a raiz) e seus filhos terão valor de sequência
  • Eu preciso obter todos os filhos (algum tipo de lista ou matriz de Strings) de um determinado nó e seu valor de string (ou seja, um método que terá um nó como entrada e retornará todos os valores de string do nó filho como saída)

Existe alguma estrutura disponível para isso ou preciso criar minha própria (se houver, sugestões de implementação seriam ótimas).

ikl
fonte
3
Se você estiver usando o Java 8, e gostaria de atravessar seus nós com fluxos, filtros, etc; então você pode querer dar uma olhada em Durian github.com/diffplug/durian
Ned Twigg
1
Você pode usar este API: sourceforge.net/p/treeds4j
Mohamed Ennahdi El Idrissi

Respostas:

306

Aqui:

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

Essa é uma estrutura de árvore básica que pode ser usada para Stringou qualquer outro objeto. É bastante fácil implementar árvores simples para fazer o que você precisa.

Tudo que você precisa adicionar são métodos para adicionar, remover, atravessar e construtores. O Nodeé o bloco de construção básico do Tree.

jjnguy
fonte
304
A rigor, a Treeclasse não é necessária, porque cada uma Nodepode ser vista como uma árvore.
Joachim Sauer
34
@Joa, eu gosto de ter uma estrutura para conter a raiz. Você pode adicionar métodos à classe de árvore que fazem mais sentido chamar uma árvore em vez de um único nó.
jjnguy
24
@ Justin: por exemplo? Essa é uma pergunta honesta: não consigo pensar em um único método que faça sentido em toda a árvore que não faça sentido em uma subárvore.
Joachim Sauer
22
Concordo com @Joa que a classe Tree não é necessária. Prefiro deixar explícita a natureza recursiva das árvores no código, não adicionando uma classe Tree separada e usando consistentemente a classe Node. Em vez disso, nomeio uma variável 'árvore' ou 'raiz' se precisar ficar claro que você está lidando com o nó raiz de uma árvore.
jvdbogae
89
@Joa Um eu de quatro anos de idade concorda completamente com você. Nix a classe de árvore.
Jjnguy
122

Ainda outra estrutura de árvore:

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 da amostra:

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

BÔNUS
Veja a árvore de pleno direito com:

  • iterador
  • procurando
  • Java / C #

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

Grzegorz Dev
fonte
2
Achei sua biblioteca extremamente útil. Obrigado. Mas eu gostaria de saber como implementar o preenchimento dinâmico da estrutura em árvore com base no relacionamento de referência entre pai e filho. Exemplo dado é que eu tenho um membro1 patrocinador outro membro2 e membro2 patrocinador membro 3 e assim por diante. Já tenho o relacionamento de registros de tabela, mas não tenho certeza se posso preenchê-los em uma árvore usando sua biblioteca.
precisa saber é o seguinte
1
a partir de 2016, o link não contém arquivos de origem ou downloads
Sharon Ben Asher
2
Na minha opinião, essa resposta três anos após a resposta classificada acima, é a mais limpa. No entanto, eu substituiria o LinkedList por um ArrayList para this.children.
HopeKing
1
Eu usaria um conjunto para as crianças.
DPM
Eu posso estar errado, mas parece que, com esta implementação, você deve ligar hasNext()antes de cada chamada next()para obter resultados válidos. Isso não faz parte da Iteratorespecificação.
Robert Lewis
97

Na verdade, existe uma estrutura de árvore muito boa implementada no JDK.

Dê uma olhada em javax.swing.tree , TreeModel e TreeNode . Eles foram projetados para serem usados ​​com o JTreePanelmas são, de fato, uma implementação de árvore muito boa e não há nada que o impeça de usá-lo sem uma interface swing.

Observe que no Java 9 você pode não usar essas classes, pois elas não estarão presentes nos 'Perfis compactos' .

Gareth Davis
fonte
5
Sim, eu os usei no passado, e eles farão tudo o que você quiser de uma árvore. A única desvantagem em que consigo pensar é o tamanho dos nomes de suas respectivas classes de implementação: DefaultTreeModel e DefaultMutableTreeNode. Verbose, mas não que seja tão importante assim, eu acho.
final Gobblement
4
Uma boa maneira de lidar com isso é criar alguns métodos estáticos newModel () e newNode () e importá-los estáticos.
Gareth Davis
140
Eu evitaria o uso de bibliotecas Swing em funções não relacionadas a Swing. Essa é uma prática ruim de codificação . Você nunca sabe como o Swing implementa suas árvores, quais são suas dependências e como isso pode mudar no futuro. Swing não é uma biblioteca de utilitários, mas uma biblioteca de interface do usuário.
jasop
44
Eu acho que a prática ruim de codificação é um pouco dura.
26512 Gareth Davis
51
javax.swing.tree.TreeModel é uma interface pública (exatamente como java.util.List) e não terá alterações incompatíveis. Uma vantagem adicional é que você pode facilmente depurar / visualizar sua árvore durante o desenvolvimento.
precisa saber é o seguinte
45

Que tal isso?

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
fonte
5
Como o DFS seria implementado em uma árvore criada usando esse objeto de classe?
Leba-lev
3
Como a remoção de uma folha seria implementada usando essa classe?
ghedas
2
Para que o campo principal seria usado?
precisa
2
Seria ótimo se essa classe tivesse alguma documentação. Eu não entendo exatamente como os métodos gostam setAsParentou getHeadfazem, e é nesse momento que eu realmente posso obter ajuda nas estruturas de dados da árvore. Até a fonte original do documento não possui comentários.
Disasterkid
23

Eu escrevi uma pequena biblioteca que lida com árvores genéricas. É muito mais leve que o material do balanço. Eu também tenho um projeto para mim .

Vivin Paliath
fonte
3
Estou usando agora, funciona de forma brilhante. Tive que mudar a fonte significativamente para minhas próprias personalizações, mas foi um ótimo ponto de partida. Graças à 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, você pode adicionar métodos utilitários para adicionar / remover filhos.

PaulJWilliams
fonte
1
Isso sugere que o pai de uma árvore é uma árvore. Acredito que você estava tentando criar uma classe Nó da Árvore.
Madhur Bhargava
16

Você deve começar definindo o que é uma árvore (para o domínio); isso é melhor feito definindo a interface primeiro. Nem todas as estruturas de árvores são modificáveis, sendo possível adicionar e remover nós deve ser um recurso opcional, por isso criamos uma interface extra para isso.

Não há necessidade de criar objetos de nó que contenham os valores ; na verdade, eu vejo isso como uma grande falha de design e sobrecarga na maioria das implementações em árvore. Se você olhar para o Swing, ele TreeModelestá livre de classes de nós (somente DefaultTreeModelé utilizado TreeNode), pois elas não são realmente necessárias.

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

Estrutura em árvore mutável (permite adicionar e remover nós):

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

Dadas essas interfaces, o código que usa árvores não precisa se preocupar muito com a maneira como a árvore é implementada. Isso permite usar implementações genéricas e especializadas , nas quais você realiza a árvore delegando funções a outra API.

Exemplo: estrutura da árvore de arquivos

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

Exemplo: estrutura em árvore genérica (com base nas relações pai / filho):

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
fonte
1
Estou enfrentando um problema quando sigo essa estrutura ao executar tree.add ("A", "B"); tree.add ("A", "C"); tree.add ("C", "D"); tree.add ("E", "A"); E é pai de A Como vamos fazer isso?
saNiks
1
Olá saNicks, houve um erro no código acima que fazia com que a última relação não fosse adicionada. Está consertado agora e também adicionei verificações não nulas e (mais importante): verificações cíclicas que evitam violar a estrutura da árvore (adicionando um código ou um de seus ancestrais como filho a si mesmo). Obrigado pela dica!
27416 Peter Walser
1
Eu consertei o bug se alguém está procurando uma correção para esse bug, o que você precisa fazer é ver se o método add retorna false e se for false, basta criar uma temp new LinkedHashSet <N> e clonar o nodelist da árvore nele, para que você possa limpar Na árvore, adicione o nó pai que não foi adicionado na etapa anterior e adicione todos os tempNode de volta à árvore pai ... Obrigado pela estrutura!
SaNiks
2
Apenas remova esses modificadores públicos inúteis de suas interfaces.
Hamedz 29/07
1
como posso gerar uma matriz JSON fora deste
Pawan Pandey
12

Nenhuma resposta menciona código simplificado, mas funcionando demais, então aqui está:

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

Você pode usar qualquer API XML de Java como documento e nó .. como XML é uma estrutura de árvore com Strings

Raja Nagendra Kumar
fonte
5
excelente idéia, poderíamos usar no esquema XML de memória usando dom4j + jaxen xpath para pesquisar nós.
Ben Rhouma Zied
8

Se você estiver fazendo codificação do quadro branco, uma entrevista ou apenas planejando usar uma árvore, a verbosidade delas é um pouco demais.

Além disso, deve-se dizer que a razão pela qual uma árvore não está lá como, digamos, a Pair(sobre a qual o mesmo poderia ser dito), é porque você deve encapsular seus dados na classe que a usa, e a implementação mais simples se parece com:

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

É isso mesmo para uma árvore de largura arbitrária.

Se você queria uma árvore binária, geralmente é mais fácil usar com campos nomeados:

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

Ou se você quisesse um trie:

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

Agora você disse que quer

ser capaz de obter todos os filhos (algum tipo de lista ou matriz de Strings) com uma string de entrada que representa um determinado nó

Isso soa como sua lição de casa.
Mas desde que eu tenho certeza que qualquer prazo já passou ...

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

Isso faz você 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
fonte
7

Na mesma linha da resposta de Gareth, confira DefaultMutableTreeNode . Não é genérico, mas de outra forma parece se encaixar na conta. Mesmo que esteja no pacote javax.swing, não depende de nenhuma classe AWT ou Swing. De fato, o código fonte realmente tem o comentário// ISSUE: this class depends on nothing in AWT -- move to java.util?

Marca
fonte
Lol, como você se deparou com essa classe?
Pacerier 28/01
7

Existem algumas estruturas de dados de árvore em Java, como DefaultMutableTreeNode no JDK Swing, pacote de analisador de árvore no Stanford e outros códigos de brinquedo. Mas nenhum deles é suficiente, mas pequeno o suficiente para fins gerais.

O projeto da árvore Java tenta fornecer outra estrutura de dados em árvore de uso geral em Java. A diferença entre este e outros são

  • Totalmente grátis. Você pode usá-lo em qualquer lugar (exceto na lição de casa: P)
  • Pequeno, mas geral o suficiente. Coloquei tudo da estrutura de dados em um arquivo de classe, para que fosse fácil copiar / colar.
  • Não é apenas um brinquedo. Estou ciente de dezenas de códigos de árvore Java que podem lidar apenas com árvores binárias ou operações limitadas. Este TreeNode é muito mais que isso. Ele fornece maneiras diferentes de visitar nós, como pré-encomenda, pós-encomenda, largura de boca, folhas, caminho para a raiz, etc. Além disso, os iteradores também são fornecidos para a suficiência.
  • Mais utils serão adicionados. Estou disposto a adicionar mais operações para tornar este projeto abrangente, especialmente se você enviar uma solicitação através do github.
Yifan Peng
fonte
5

Como a pergunta solicita uma estrutura de dados disponível, uma árvore pode ser construída a partir de listas ou matrizes:

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

instanceof pode ser usado para determinar se um elemento é uma subárvore ou um nó terminal.

Olathe
fonte
2
Muito feio. E não funciona, se seus objetos de dados podem ser matrizes, respectivamente.
user686249
1
Eu concordo que é feio. Os Objects seriam os objetos de folha (por exemplo, Strings) ou ramos (representados por matrizes). E funciona: esse código será compilado e cria uma pequena árvore de Strings.
Olathe
5
public abstract class Node {
  List<Node> children;

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

Tão simples quanto possível e muito fácil de usar. Para usá-lo, estenda-o:

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

Por exemplo :

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

No passado, acabei de usar um mapa aninhado para isso. É isso que eu uso hoje, é muito simples, mas atende às minhas necessidades. Talvez isso ajude outro.

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

Eu escrevi uma pequena classe "TreeMap" baseada em "HashMap" que suporta a adição de caminhos:

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

}

Pode ser usado para armazenar uma Árvore de coisas do tipo "T" (genérico), mas ainda não suporta o armazenamento de dados extras em seus nós. Se você possui um arquivo como este:

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

Então você pode torná-lo uma árvore executando:

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

E você receberá uma bela árvore. Deve ser fácil se adaptar às suas necessidades.

mevdschee
fonte
2

Você pode usar a classe HashTree incluída no Apache JMeter que faz parte do Projeto Jakarta.

A classe HashTree está incluída no pacote org.apache.jorphan.collections. Embora este pacote não seja lançado fora do projeto JMeter, você pode obtê-lo facilmente:

1) Faça o download das fontes JMeter .

2) Crie um novo pacote.

3) Copie nele / src / jorphan / org / apache / jorphan / collections /. Todos os arquivos, exceto Data.java

4) Copie também /src/jorphan/org/apache/jorphan/util/JOrphanUtils.java

5) O HashTree está pronto para uso.

David
fonte
2

Não existe uma estrutura de dados específica em Java que atenda aos seus requisitos. Seus requisitos são bastante específicos e, para isso, é necessário projetar sua própria estrutura de dados. Analisando seus requisitos, qualquer pessoa pode dizer que você precisa de algum tipo de árvore n-ária com alguma funcionalidade específica. Você pode projetar sua estrutura de dados da seguinte maneira:

  1. A estrutura do nó da árvore seria como o conteúdo no nó e a lista de filhos como: class Node {String value; Listar filhos;}
  2. Você precisa recuperar os filhos de uma determinada string, para poder ter 2 métodos 1: Node searchNode (String str), retornará o nó que tem o mesmo valor que a entrada especificada (use o BFS para pesquisar) 2: List getChildren (String str): esse método chamará internamente o searchNode para obter o nó com a mesma string e, em seguida, criará a lista de todos os valores de string dos filhos e retornará.
  3. Você também precisará inserir uma string na árvore. Você precisará escrever um método, por exemplo, void insert (String pai, Valor da string): isso procurará novamente o nó com valor igual ao pai e, em seguida, você poderá criar um Nó com determinado valor e adicionar à lista de filhos do pai encontrado .

Eu sugeriria que você escrevesse a estrutura do nó em uma classe como Class Node {String value; Listar children;} e todos os outros métodos, como search, insert e getChildren em outra classe NodeUtils, para que você também possa passar a raiz da árvore para executar operações em uma árvore específica, como: class NodeUtils {public static Node search (Node root, String value) {// execute o BFS e retorne o nó}

aman rastogi
fonte
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
fonte
3
Por favor, não apenas despeje o código - explique o que ele faz, e especialmente por que ele difere (é melhor) do que todas as outras respostas.
Jan Doggen
2

Eu escrevi uma biblioteca em árvore que funciona bem com o Java8 e que não tem outras dependências. Ele também fornece uma interpretação livre de algumas idéias da programação funcional e permite mapear / filtrar / remover / pesquisar a árvore ou subárvores inteiras.

https://github.com/RutledgePaulV/prune

A implementação não faz nada de especial na indexação e eu não me afastei da recursão; portanto, é possível que, com árvores grandes, o desempenho diminua e você possa explodir a pilha. Mas se tudo o que você precisa é de uma árvore simples, de profundidade pequena a moderada, acho que funciona bem o suficiente. Ele fornece uma definição sadia (baseada em valor) de igualdade e também possui uma implementação toString que permite visualizar a árvore!

RutledgePaulV
fonte
1

Por favor, verifique o código abaixo, onde usei estruturas de dados em árvore, sem usar as classes Collection. O código pode ter bugs / aprimoramentos, mas use isso apenas para referência

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
fonte
2
" sem usar classes de coleção " Ah? Então, de onde vem a classe Queue? E, como dito acima, é uma árvore binária, com falha no primeiro requisito (qualquer número de nós filhos).
PhiLho
1

Você pode usar a classe TreeSet em java.util. *. Está funcionando como uma árvore de pesquisa binária, portanto já está classificada. A classe TreeSet implementa as interfaces Iterable, Collection e Set. Você pode percorrer a árvore com o iterador como um conjunto.

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

Você pode verificar, Java Doc e outros .

Oguz
fonte
-1

Implementar Árvore Personalizada da Árvore sem usar a estrutura Coleção. Ele contém diferentes operações fundamentais necessárias na implementação da Árvore.

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
fonte
11
Isso é uma árvore binária, ele falha na primeira exigência do OP ...
PhiLho