Hoe implementeer je een boomdatastructuur in Java?

Is er een standaard Java-bibliotheekklasse om een ​​boomstructuur in Java weer te geven?

In het bijzonder moet ik het volgende vertegenwoordigen:

• De substructuur op elk knooppunt kan een willekeurig aantal kinderen hebben
• Elk knooppunt (na de root) en de onderliggende items hebben een tekenreekswaarde
• Ik moet alle kinderen (een soort lijst of array van tekenreeksen) van een bepaald knooppunt en zijn tekenreekswaarde krijgen (dwz een methode die een knooppunt als invoer neemt en alle tekenreekswaarden van het onderliggende knooppunt retourneert als uitvoer)

Is hier een beschikbare structuur voor of moet ik er zelf een maken (als dat zo is, zouden implementatiesuggesties geweldig zijn).

Antwoord 1, autoriteit 100%

Hier:

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

Dat is een basisboomstructuur die kan worden gebruikt voor Stringof elk ander object. Het is vrij eenvoudig om eenvoudige bomen te implementeren om te doen wat je nodig hebt.

Het enige dat u hoeft toe te voegen zijn methoden voor toevoegen aan, verwijderen uit, doorkruisen en constructors. De Nodeis de basisbouwsteen van de Tree.

Antwoord 2, autoriteit 41%

Nog een andere boomstructuur:

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

Voorbeeldgebruik:

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
Zie volwaardige boom met:

• iterator
• zoeken
• Java/C#

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

Antwoord 3, autoriteit 31%

Er is eigenlijk een behoorlijk goede boomstructuur geïmplementeerd in de JDK.

Bekijk javax. swing.tree, TreeModel, en TreeNode. Ze zijn ontworpen om te worden gebruikt met het JTreePanel, maar ze zijn in feite een behoorlijk goede boomimplementatie en er is niets dat je ervan weerhoudt om het te gebruiken zonder een swing-interface.

Merk op dat je vanaf Java 9 deze klassen misschien niet meer wilt gebruiken, omdat ze niet aanwezig zullen zijn in de ‘Compacte profielen’.

Antwoord 4, autoriteit 15%

Hoe zit het hiermee?

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

Antwoord 5, autoriteit 8%

Ik schreefeen kleine bibliotheek die generieke bomen verwerkt. Het is veel lichter dan de schommel spullen. Ik heb ook een maven-project ervoor.

Antwoord 6, autoriteit 7%

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

Natuurlijk kunt u hulpprogramma’s toevoegen om kinderen toe te voegen/te verwijderen.

Antwoord 7, autoriteit 6%

Je moet beginnen met het definiëren van wat een boom is (voor het domein), dit kun je het beste doen door eerst de interfacete definiëren. Niet alle boomstructuren zijn aanpasbaar, het kunnen toevoegenen verwijderenknooppunten zou een optionele functie moeten zijn, dus daar maken we een extra interface voor.

Het is niet nodig om knooppuntobjecten te maken die de waarden bevatten, in feite zie ik dit als een grote ontwerpfout en overhead in de meeste boomimplementaties. Als je naar Swing kijkt, is het TreeModelvrij van node-klassen (alleen DefaultTreeModelmaakt gebruik van TreeNode), omdat ze niet echt nodig zijn.

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

Veranderlijke boomstructuur (maakt het mogelijk om knooppunten toe te voegen en te verwijderen):

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

Gezien deze interfaces hoeft code die gebruikmaakt van bomen niet veel te schelen hoe de boom wordt geïmplementeerd. Hierdoor kunt u zowel generiekeals gespecialiseerdeimplementaties gebruiken, waarbij u de boomstructuur realiseert door functies te delegeren aan een andere API.

Voorbeeld: bestandsboomstructuur

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

Voorbeeld: algemene boomstructuur(gebaseerd op bovenliggende/onderliggende relaties):

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

Antwoord 8, autoriteit 4%

Geen antwoord vermeldt een te vereenvoudigde maar werkende code, dus hier is het:

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

Antwoord 9, autoriteit 3%

Je kunt elke XML API van Java gebruiken als Document en Node..as XML is een boomstructuur met Strings

Antwoord 10, autoriteit 3%

Als je whiteboard-codering doet, een interview houdt of zelfs maar van plan bent een boomstructuur te gebruiken, is de breedsprakigheid hiervan allemaal een beetje veel.

Verder moet gezegd worden dat de reden dat een boom daar niet in staat, zoals bijvoorbeeld een Pair(waarover hetzelfde zou kunnen worden gezegd), is omdat je je gegevens zou moeten inkapselen in de class gebruikt, ende eenvoudigste implementatie ziet er als volgt uit:

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

Dat is het eigenlijk voor een boom met een willekeurige breedte.

Als u een binaire boomstructuur wilde, is deze vaak gemakkelijker te gebruiken met benoemde velden:

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

Of als je het een keer wilt proberen:

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

Nu heb je gezegd dat je wilt

om alle kinderen (een soort lijst of array van Strings) een invoerstring te kunnen geven die een bepaald knooppunt vertegenwoordigt

Dat klinkt als je huiswerk.
Maar aangezien ik er redelijk zeker van ben dat er nu een deadline is verstreken

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

Hierdoor krijg je gebruik als:

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

Antwoord 11, autoriteit 2%

In dezelfde lijn als het antwoord van Gareth, bekijk DefaultMutableTreeNode. Het is niet generiek, maar verder lijkt het te passen. Ook al zit het in het javax.swing-pakket, het is niet afhankelijk van AWT- of Swing-klassen. In feite heeft de broncode de opmerking // ISSUE: this class depends on nothing in AWT -- move to java.util?

Antwoord 12, autoriteit 2%

Er zijn een aantal boomgegevensstructuren in Java, zoals DefaultMutableTreeNode in JDK Swing, Tree in Stanford-parserpakket en andere speelgoedcodes. Maar geen van deze is voldoende maar klein genoeg voor algemene doeleinden.

Java-treeproject probeert een andere algemene boomgegevensstructuur in Java te bieden. Het verschil tussen dit en anderen is

• Volledig gratis. Je kunt het overal gebruiken (behalve in je huiswerk :P)
• Klein maar algemeen genoeg. Ik heb alles van de gegevensstructuur in één klassenbestand geplaatst, zodat het gemakkelijk te kopiëren/plakken zou zijn.
• Niet alleen speelgoed. Ik ken tientallen Java-boomcodes die alleen binaire bomen of beperkte bewerkingen aankunnen. Deze TreeNode is veel meer dan dat. Het biedt verschillende manieren om knooppunten te bezoeken, zoals preorder, postorder, breedte eerst, bladeren, pad naar root, enz. Bovendien zijn er ook iterators voorzien voor de toereikendheid.
• Er zullen meer hulpprogramma’s worden toegevoegd. Ik ben bereid meer bewerkingen toe te voegen om dit project uitgebreid te maken, vooral als je een verzoek stuurt via github.

Antwoord 13, autoriteit 2%

Omdat de vraag om een ​​beschikbare datastructuur vraagt, kan een boom worden opgebouwd uit lijsten of arrays:

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

instanceofkan worden gebruikt om te bepalen of een element een substructuur of een terminalknooppunt is.

Antwoord 14, autoriteit 2%

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

Zo eenvoudig als het wordt en zeer gebruiksvriendelijk. Om het te gebruiken, verleng het:

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

Antwoord 15

Bijvoorbeeld:

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

Antwoord 16

In het verleden heb ik hiervoor zojuist een geneste kaart gebruikt. Dit is wat ik vandaag gebruik, het is heel eenvoudig, maar het past bij mijn behoeften. Misschien helpt dit een ander.

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

Antwoord 17

Ik heb een kleine “TreeMap”-klasse geschreven op basis van “HashMap” die het toevoegen van paden ondersteunt:

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

Het kan worden gebruikt om een ​​Tree of things van het type “T” (generiek) op te slaan, maar biedt (nog) geen ondersteuning voor het opslaan van extra data in zijn nodes. Als je een bestand als dit hebt:

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

Vervolgens kun je er een boom van maken door het volgende uit te voeren:

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

En je krijgt een mooie boom. Het moet gemakkelijk aan uw behoeften kunnen worden aangepast.

Antwoord 18

Je kunt de klasse HashTreegebruiken opgenomen in Apache JMeter dat deel uitmaakt van het Jakarta Project.

HashTree-klasse is opgenomen in het pakket org.apache.jorphan.collections. Hoewel dit pakket niet buiten het JMeter-project wordt vrijgegeven, kunt u het gemakkelijk verkrijgen:

1) Download de JMeter-bronnen.

2) Maak een nieuw pakket.

3) Kopieer ernaar /src/jorphan/org/apache/jorphan/collections/ . Alle bestanden behalve Data.java

4) Kopieer ook /src/jorphan/org/apache/jorphan/util/JOrphanUtils.java

5) HashTree is klaar voor gebruik.

Antwoord 19

Er is geen specifieke datastructuur in Java die aan uw eisen voldoet. Uw eisen zijn vrij specifiek en daarvoor moet u uw eigen datastructuur ontwerpen. Als je naar je vereisten kijkt, kan iedereen zeggen dat je een soort n-ary tree nodig hebt met een specifieke functionaliteit. U kunt uw gegevensstructuur op de volgende manier ontwerpen:

1. Structuur van het knooppunt van de boom zou zijn als inhoud in het knooppunt en de lijst met kinderen zoals:
   klasse Knooppunt { Stringwaarde; Lijst kinderen;}
2. Je moet de onderliggende items van een gegeven string ophalen, dus je kunt 2 methoden hebben 1: Node searchNode(String str), retourneert de node die dezelfde waarde heeft als de gegeven invoer (gebruik BFS voor zoeken) 2: Lijst getChildren(String str): deze methode roept intern de searchNode aan om het knooppunt met dezelfde string te krijgen en maakt vervolgens de lijst met alle stringwaarden van kinderen en retourneert.
3. Je moet ook een string in de boomstructuur invoegen. Je zult één methode moeten schrijven, zeg void insert (String parent, String value): dit zal opnieuw het knooppunt zoeken met een waarde die gelijk is aan ouder en dan kun je een knooppunt maken met een bepaalde waarde en toevoegen aan de lijst met kinderen van de gevonden ouder .

Ik zou willen voorstellen dat je de structuur van het knooppunt in één klasse schrijft, zoals Class Node { String value; Lijst kinderen;} en alle andere methoden zoals zoeken, invoegen en getChildren in een andere NodeUtils-klasse, zodat u ook de wortel van de boom kunt doorgeven om een ​​bewerking uit te voeren op een specifieke boom, zoals:
class NodeUtils{ public static Node search (Node root, String value){// voer BFS uit en retourneer Node}

Antwoord 20

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

Antwoord 21

Ik heb een boombibliotheek geschreven die goed samenspeelt met Java8 en die geen andere afhankelijkheden heeft. Het biedt ook een losse interpretatie van enkele ideeën uit functioneel programmeren en laat je de hele boom of subbomen in kaart brengen/filteren/snoeien/doorzoeken.

https://github.com/RutledgePaulV/prune

De implementatie doet niets speciaals met indexeren en ik ben niet afgedwaald van recursie, dus het is mogelijk dat met grote bomen de prestaties achteruitgaan en je de stapel zou kunnen opblazen. Maar als alles wat je nodig hebt een eenvoudige boom is van kleine tot matige diepte, denk ik dat het goed genoeg werkt. Het biedt een gezonde (op waarde gebaseerde) definitie van gelijkheid en het heeft ook een toString-implementatie waarmee je de boom kunt visualiseren!

Antwoord 22

Controleer de onderstaande code, waar ik Tree-gegevensstructuren heb gebruikt, zonder Collection-klassen te gebruiken. De code kan bugs/verbeteringen bevatten, maar gebruik deze alleen ter referentie

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

Antwoord 23

U kunt de TreeSet-klasse gebruiken in java.util.*. Het werkt als een binaire zoekboom, dus het is al gesorteerd. De klasse TreeSet implementeert de interfaces Iterable, Collection en Set. Je kunt als een set door de boom gaan met iterator.

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

Je kunt Java Docen enkele andere.

Antwoord 24

Aangepaste Tree-implementatie van Tree zonder het Collection-framework te gebruiken.
Het bevat verschillende fundamentele bewerkingen die nodig zijn in Tree-implementatie.

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