Jak zaimplementować strukturę danych drzewa w Javie? [Zamknięte]

496

Czy jest jakaś standardowa klasa biblioteki Java do reprezentowania drzewa w Javie?

W szczególności muszę przedstawić następujące informacje:

  • Pod-drzewo w dowolnym węźle może mieć dowolną liczbę dzieci
  • Każdy węzeł (po katalogu głównym) i jego dzieci będą miały wartość ciągu
  • Muszę uzyskać wszystkie elementy potomne (jakąś listę lub tablicę ciągów) danego węzła i jego wartość ciągu (tj. Metodę, która pobierze węzeł jako dane wejściowe i zwróci wszystkie wartości ciągu węzła potomnego jako dane wyjściowe)

Czy istnieje jakaś dostępna struktura do tego, czy też muszę utworzyć własną (jeśli tak, sugestie dotyczące implementacji byłyby świetne).

ikl
źródło
3
Jeśli używasz Java 8 i chcesz przeglądać węzły za pomocą strumieni, filtrowania itp .; to możesz rzucić
Ned Twigg
1
Możesz użyć tego interfejsu API: sourceforge.net/p/treeds4j
Mohamed Ennahdi El Idrissi

Odpowiedzi:

306

Tutaj:

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

Jest to podstawowa struktura drzewa, której można użyć do Stringdowolnego innego obiektu. Łatwo jest wdrożyć proste drzewa, aby zrobić to, czego potrzebujesz.

Wszystko, co musisz dodać, to metody dodawania, usuwania, przechodzenia i konstruktorów. Jest Nodeto podstawowy element składowy Tree.

jjnguy
źródło
304
Ściśle mówiąc, Treeklasa nie jest konieczna, ponieważ każdy Nodemoże być postrzegany jako drzewo.
Joachim Sauer,
34
@Joa, lubię mieć strukturę zawierającą root. Do klasy drzewa można dodawać metody, które bardziej sensownie wywołują drzewo niż pojedynczy węzeł.
jjnguy,
24
@Justin: na przykład? To szczere pytanie: nie mogę wymyślić jednej metody, która miałaby sens na całym drzewie, która nie miałaby sensu na poddrzewie.
Joachim Sauer,
22
Zgadzam się z @Joa, że ​​klasa Tree nie jest konieczna. Wolę pozostawić rekurencyjną naturę drzew jawną w kodzie, nie dodając osobnej klasy Tree i konsekwentnie używając klasy Node. Zamiast tego nazywam zmienną „drzewem” lub „korzeniem”, jeśli musi być jasne, że masz do czynienia z węzłem głównym drzewa.
jvdbogae
89
@Joa Czteroletni ja całkowicie się z tobą zgadzam. Nix klasy drzewa.
jjnguy
122

Jeszcze inna struktura drzewa:

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

}

Przykładowe użycie:

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
Zobacz pełne drzewo z:

  • iterator
  • badawczy
  • Java / C #

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

Grzegorz Dev
źródło
2
Właśnie znalazłem twoją bibliotekę niezwykle przydatną. Dziękuję Ci. Chciałbym jednak wiedzieć, jak zaimplementować dynamicznie zapełnianie struktury drzewa na podstawie relacji referencyjnej między rodzicem a dzieckiem. Podany przykład to, że mam jednego członka 1, sponsora, innego członka 2, i członka 2, członka sponsora 3 i tak dalej. Mam już relację między rekordami tabeli, ale po prostu nie jestem pewien, czy mogę umieścić je w drzewie za pomocą biblioteki.
d4v1dv00
1
od 2016 r. link nie zawiera plików źródłowych ani plików do pobrania
Sharon Ben Asher
2
Moim zdaniem ta odpowiedź trzy lata po wyżej ocenianej odpowiedzi jest bardziej przejrzysta. Jednak zastąpiłbym LinkedList ArrayList dla this.children.
HopeKing,
1
Chciałbym użyć zestawu dla dzieci.
DPM,
Mogę się mylić, ale wydaje się, że dzięki tej implementacji musisz zadzwonić hasNext()przed każdym wywołaniem, next()aby uzyskać prawidłowe wyniki. To nie jest część Iteratorspecyfikacji.
Robert Lewis,
97

W JDK zaimplementowano całkiem dobrą strukturę drzewa.

Spójrz na javax.swing.tree , TreeModel i TreeNode . Zostały zaprojektowane do użytku zJTreePanel ale w rzeczywistości są całkiem dobrą implementacją drzewa i nic nie stoi na przeszkodzie, aby używać go bez interfejsu swing.

Zwróć uwagę, że od wersji Java 9 możesz nie chcieć korzystać z tych klas, ponieważ nie będą one obecne w „Kompaktowych profilach” .

Gareth Davis
źródło
5
Tak, korzystałem z nich w przeszłości, a oni zrobią wszystko, co chcesz z drzewa. Jedynym minusem, jaki mogę wymyślić, jest długość nazw odpowiednich klas implementujących: DefaultTreeModel i DefaultMutableTreeNode. Pełne, ale nie tak ważne, jak sądzę.
Ultimate Gobblement,
4
Dobrym sposobem na poradzenie sobie z tym jest utworzenie kilku metod statycznych newModel () i newNode (), a następnie ich importowanie statyczne.
Gareth Davis
140
Unikałbym używania bibliotek Swing do funkcji niezwiązanych z Swing. To zła praktyka kodowania . Nigdy nie wiadomo, jak Swing wdraża swoje drzewa, jakie są ich zależności i jak może się to zmienić w przyszłości. Swing nie jest biblioteką narzędziową, ale biblioteką interfejsu użytkownika.
jasop
44
Myślę, że zła praktyka kodowania jest trochę trudna.
Gareth Davis
51
javax.swing.tree.TreeModel to interfejs publiczny (dokładnie taki jak java.util.List) i nie będzie zawierał niezgodnych zmian. Dodatkową zaletą jest to, że możesz łatwo debugować / wizualizować swoje drzewo podczas programowania.
lbalazscs
45

A co z tym?

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
źródło
5
Jak DFS zostałby zaimplementowany w drzewie utworzonym przy użyciu tego obiektu klasy?
leba-lev
3
W jaki sposób usunięcie liścia byłoby zaimplementowane przy użyciu tej klasy?
ghedas
2
Do czego służy pole przednie?
Acour83
2
Byłoby wspaniale, gdyby ta klasa miała jakąś dokumentację. Nie bardzo rozumiem, co podobne metody setAsParentlub getHeadzrobić i jest to czas, kiedy naprawdę można uzyskać pomoc na temat struktur danych drzewo. Nawet oryginalne źródło dokumentu nie ma komentarzy.
disasterkid
23

Ja napisałem małą bibliotekę, która obsługuje rodzajowe drzewa. Jest znacznie lżejszy niż huśtawka. Mam też do tego projekt maven .

Vivin Paliath
źródło
3
Używam go teraz, działa doskonale. Musiałem znacznie zmienić źródło dla moich własnych dostosowań, ale był to świetny punkt wyjścia. Dzięki 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;
    }
}

Oczywiście możesz dodać metody narzędzi do dodawania / usuwania dzieci.

PaulJWilliams
źródło
1
Sugeruje to, że rodzicem drzewa jest drzewo. Myślę, że próbujesz stworzyć klasę Tree Node.
Madhur Bhargava
16

Powinieneś zacząć od zdefiniowania, czym jest drzewo (dla domeny), najlepiej to zrobić , najpierw definiując interfejs . Nie wszystkie struktury drzew można modyfikować, ponieważ można je dodawać i usuwać węzłów powinna być funkcją opcjonalną, dlatego tworzymy dodatkowy interfejs do tego.

Nie ma potrzeby tworzenia obiektów węzłów, które przechowują wartości , w rzeczywistości postrzegam to jako poważną wadę projektową i koszty ogólne w większości implementacji drzew. Jeśli spojrzysz na Swinga, TreeModeljest on wolny od klas węzłów ( DefaultTreeModelwykorzystuje tylko TreeNode), ponieważ nie są one tak naprawdę potrzebne.

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

Zmienna struktura drzewa (pozwala dodawać i usuwać węzły):

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

Biorąc pod uwagę te interfejsy, kod wykorzystujący drzewa nie musi zbytnio dbać o sposób implementacji drzewa. Pozwala to na korzystanie zarówno z implementacji ogólnych, jak i specjalistycznych , w których drzewo jest realizowane przez delegowanie funkcji do innego interfejsu API.

Przykład: struktura drzewa plików

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

Przykład: ogólna struktura drzewa (oparta na relacjach rodzic / dziecko):

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
źródło
1
Mam do czynienia z problemem, gdy podążam za tą strukturą, gdy robię tree.add („A”, „B”); tree.add („A”, „C”); tree.add („C”, „D”); tree.add („E”, „A”); E jest rodzicem A Jak to zrobić?
saNiks
1
Cześć saNicks, w powyższym kodzie był błąd, który spowodował, że ostatnia relacja nie została dodana. Zostało to teraz naprawione, a także dodałem kontrole niepuste i (co ważniejsze): kontrole cykliczne, które zapobiegają naruszeniu struktury drzewa (dodawanie kodu lub jednego z jego przodków jako dziecka do siebie). Dzięki za podpowiedź!
Peter Walser
1
Naprawiłem błąd, jeśli ktoś szuka poprawki dla tego błędu, co musisz zrobić, to zobaczyć, czy metoda add zwraca false, a jeśli jest fałszywa, po prostu utwórz tymczasowo nowy LinkedHashSet <N> i sklonuj do niego listę węzłów drzewa, a następnie możesz wyczyścić drzewo, dodaj węzeł nadrzędny, który nie został dodany w poprzednim kroku, a następnie dodaj wszystkie tempNode z powrotem do drzewa nadrzędnego ... Dzięki za strukturę!
saNiks 30.04.16
2
Po prostu usuń te bezużyteczne publiczne modyfikatory z interfejsów.
Hamedz
1
jak mogę wygenerować z tego tablicę json
Pawan Pandey
12

W żadnej odpowiedzi nie wspomniano o zbyt uproszczonym, ale działającym kodzie, więc oto:

public class TreeNodeArray<T> {
    public T value;
    public final  java.util.List<TreeNodeArray<T>> kids =  new java.util.ArrayList<TreeNodeArray<T>>();
}
peenut
źródło
10

Możesz używać dowolnego interfejsu API języka Java w języku Java jako Dokumentu i Węzła. XML jest strukturą drzewa z ciągami

Raja Nagendra Kumar
źródło
5
doskonały pomysł, możemy użyć schematu XML pamięci przy użyciu dom4j + jaxen xpath do wyszukiwania węzłów.
Ben Rhouma Zied
8

Jeśli wykonujesz kodowanie tablicy, wywiad, a nawet po prostu planujesz użyć drzewa, wszystko to jest trochę gadatliwe.

Należy ponadto powiedzieć, że powodem, dla którego nie ma tam drzewa, na przykład Pair(o którym można powiedzieć to samo), jest to, że powinieneś hermetyzować swoje dane w klasie, używając go, a najprostsza implementacja wygląda następująco:

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

To naprawdę tyle w przypadku drzewa o dowolnej szerokości.

Jeśli chcesz drzewa binarnego, często łatwiej jest używać nazwanych pól:

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

Lub jeśli chcesz spróbować:

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

Teraz powiedziałeś, że chcesz

aby uzyskać wszystkie elementy potomne (jakąś listę lub tablicę ciągów) na podstawie ciągu wejściowego reprezentującego dany węzeł

To brzmi jak twoja praca domowa.
Ale ponieważ jestem dość pewien, że minął termin…

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

Dzięki temu możesz używać:

$ 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
źródło
7

Wzdłuż tych samych wierszy, co odpowiedź Garetha, sprawdź DefaultMutableTreeNode . To nie jest ogólne, ale poza tym wydaje się pasować do rachunku. Mimo że znajduje się w pakiecie javax.swing, nie zależy od żadnych klas AWT ani Swing. W rzeczywistości kod źródłowy ma komentarz// ISSUE: this class depends on nothing in AWT -- move to java.util?

znak
źródło
Lol, jak trafiłeś na tę klasę?
Pacerier
7

W Javie istnieje kilka struktur danych drzewa, takich jak DefaultMutableTreeNode w JDK Swing, pakiet parsera Tree w Stanford i inne kody zabawek. Ale żaden z nich nie jest wystarczający, ale wystarczająco mały do ​​ogólnego zastosowania.

Projekt drzewa Java próbuje dostarczyć inną strukturę danych drzewa ogólnego przeznaczenia w Javie. Różnica między tym a innymi jest

  • Totalnie wolny. Możesz go używać w dowolnym miejscu (poza pracą domową: P)
  • Mały, ale dość ogólny. Umieściłem całą strukturę danych w jednym pliku klasy, więc łatwo byłoby skopiować / wkleić.
  • Nie tylko zabawki. Znam dziesiątki kodów drzew Java, które mogą obsługiwać tylko drzewa binarne lub ograniczone operacje. Ten TreeNode to znacznie więcej. Zapewnia różne sposoby odwiedzania węzłów, takie jak zamówienie przedpremierowe, postorder, pierwsze sprawdzenie, liście, ścieżka do rootowania itp. Ponadto dla zapewnienia wystarczającej liczby iteratorów.
  • Dodano więcej narzędzi. Jestem gotów dodać więcej operacji, aby uczynić ten projekt kompleksowym, szczególnie jeśli wyślesz zapytanie za pośrednictwem github.
Yifan Peng
źródło
5

Ponieważ pytanie dotyczy dostępnej struktury danych, drzewo można zbudować z list lub tablic:

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

instanceof można użyć do ustalenia, czy element jest poddrzewem, czy węzłem końcowym.

Olathe
źródło
2
Dość brzydka. I nie działa, jeśli obiektami danych mogą być tablice lub listy.
user686249
1
Zgadzam się, że to brzydkie. ObjectA to być zarówno przedmioty liści (na przykład, StringS) lub oddziałów (reprezentowanych przez macierze). I to działa: ten kod się skompiluje i utworzy małe drzewo Strings.
Olathe
5
public abstract class Node {
  List<Node> children;

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

Tak prosty, jak to tylko możliwe i bardzo łatwy w użyciu. Aby go użyć, rozszerz go:

public class MenuItem extends Node {
  String label;
  String href;
  ...
}
bretter
źródło
3

Na przykład :

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
źródło
3

W przeszłości użyłem do tego zagnieżdżonej mapy. Tego właśnie używam, jest to bardzo proste, ale pasuje do moich potrzeb. Może to pomoże kolejnemu.

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"));
    }
}
WWI
źródło
3

Napisałem małą klasę „TreeMap” opartą na „HashMap”, która obsługuje dodawanie ścieżek:

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

}

Można go użyć do przechowywania Drzewa rzeczy typu „T” (ogólne), ale nie obsługuje (jeszcze) przechowywania dodatkowych danych w jego węzłach. Jeśli masz taki plik:

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

Następnie możesz zrobić z niego drzewo, wykonując:

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

I dostaniesz ładne drzewo. Powinno być łatwo dostosować się do twoich potrzeb.

mevdschee
źródło
2

Możesz użyć klasy HashTree zawartej w Apache JMeter, który jest częścią projektu Jakarta.

Klasa HashTree znajduje się w pakiecie org.apache.jorphan.collections. Chociaż ten pakiet nie został wydany poza projektem JMeter, możesz go łatwo uzyskać:

1) Pobierz źródła JMeter .

2) Utwórz nowy pakiet.

3) Skopiuj na niego / src / jorphan / org / apache / jorphan / collections /. Wszystkie pliki oprócz Data.java

4) Skopiuj również /src/jorphan/org/apache/jorphan/util/JOrphanUtils.java

5) HashTree jest gotowy do użycia.

David
źródło
2

W Javie nie ma określonej struktury danych, która odpowiada Twoim wymaganiom. Twoje wymagania są dość specyficzne i do tego musisz zaprojektować własną strukturę danych. Patrząc na twoje wymagania, każdy może powiedzieć, że potrzebujesz jakiegoś drzewa n-ary z pewną specyficzną funkcjonalnością. Możesz zaprojektować strukturę danych w następujący sposób:

  1. Struktura węzła drzewa byłaby podobna do zawartości w węźle i listy dzieci takich jak: class Node {Wartość ciągu; Lista dzieci;}
  2. Musisz pobrać elementy potomne danego ciągu, abyś mógł mieć 2 metody 1: Węzeł searchNode (String str), zwróci węzeł, który ma taką samą wartość jak podane dane wejściowe (użyj BFS do wyszukiwania) 2: List getChildren (String str): ta metoda wywoła wewnętrznie searchNode, aby uzyskać węzeł mający ten sam ciąg znaków, a następnie utworzy listę wszystkich wartości ciągu dzieci i zwróci.
  3. Będziesz także musiał wstawić ciąg do drzewa. Będziesz musiał napisać jedną metodę: void insert (String parent, String value): to ponownie przeszuka węzeł o wartości równej rodzicowi, a następnie możesz utworzyć Węzeł o podanej wartości i dodać do listy dzieci znalezionego rodzica .

Sugerowałbym, abyś napisał strukturę węzła w jednej klasie, np. Class Node {Wartość ciągu; Lista potomków;} i wszystkie inne metody, takie jak search, insert i getChildren w innej klasie NodeUtils, dzięki czemu można również przekazać katalog główny drzewa, aby wykonać operację na określonym drzewie, na przykład: class NodeUtils {publiczne statyczne wyszukiwanie węzłów (węzeł główny, wartość ciągu) {// wykonaj BFS i zwróć węzeł}

aman rastogi
źródło
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
źródło
3
Proszę nie tylko zrzucać kod - wyjaśnić, co robi, a zwłaszcza dlaczego różni się (jest lepszy) niż wszystkie inne odpowiedzi.
Jan Doggen,
2

Napisałem bibliotekę drzewa, która ładnie gra z Javą 8 i która nie ma innych zależności. Zapewnia również luźną interpretację niektórych pomysłów z programowania funkcjonalnego i pozwala mapować / filtrować / przycinać / przeszukiwać całe drzewo lub poddrzewa.

https://github.com/RutledgePaulV/prune

Implementacja nie robi nic specjalnego z indeksowaniem i nie oddaliłam się od rekurencji, więc możliwe jest, że przy dużych drzewach wydajność spadnie i możesz zdmuchnąć stos. Ale jeśli wszystko, czego potrzebujesz, to proste drzewo o małej do umiarkowanej głębokości, myślę, że działa wystarczająco dobrze. Zapewnia rozsądną (opartą na wartościach) definicję równości, a także implementację toString, która umożliwia wizualizację drzewa!

RutledgePaulV
źródło
1

Sprawdź poniższy kod, w którym użyłem struktur danych drzewa, bez używania klas Collection. Kod może zawierać błędy / ulepszenia, ale użyj go tylko w celach informacyjnych

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
źródło
2
bez użycia klas kolekcji ” Ah? Skąd więc bierze się klasa Queue? I jak wspomniano powyżej, jest to drzewo binarne, które nie spełnia pierwszego wymagania (dowolna liczba węzłów potomnych).
PhiLho,
1

Możesz użyć klasy TreeSet w java.util. *. Działa jak drzewo wyszukiwania binarnego, więc jest już posortowane. Klasa TreeSet implementuje interfejsy Iterable, Collection i Set. Możesz przechodzić przez drzewo z iteratorem jak zestaw.

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

Możesz sprawdzić, Java Doc i kilka innych .

Oguz
źródło
-1

Niestandardowe drzewo implementacji Tree bez korzystania z frameworku Collection. Zawiera różne podstawowe operacje potrzebne do implementacji drzewa.

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
źródło
11
To drzewo binarne, zawodzi przy pierwszym wymaganiu OP ...
PhiLho