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

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

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.

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

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

A co z tym?

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

/**
  * @author ycoppel@google.com (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;
  }
}

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

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.

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

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

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

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

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?

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.

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.

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

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

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

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.

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.

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

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

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!

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

    }

}

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 .

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

}