Java树的数据结构？

是否有一个好的可用（标准Java）数据结构来表示Java中的树？

具体来说，我需要表示以下内容：

• 任何节点上的树可以有任意数量的子节点
• 每个节点（在根之后）只是一个string（其子节点也是string）
• 我需要能够得到所有的孩子（某种列表或string数​​组）给定一个inputstring表示给定的节点

有没有可用的结构，或者我需要创build自己的（如果这样的实施build议将是伟大的）。

Answer 1

这里：

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

这是一个可以用于String或任何其他对象的基本树结构。 实现简单的树来完成你所需要的是相当容易的。

所有你需要添加的方法是添加，删除，遍历和构造函数。 Node是Tree的基本构build块。

Answer 2

又一个树形结构：

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

示例用法：

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

奖金
看到完全成熟的树：

• 迭代器
• search
• 的Java / C＃

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

Answer 3

实际上在JDK中实现了一个非常好的树结构。

看看javax.swing.tree ， TreeModel和TreeNode 。 它们被devise成与JTreePanel一起使用，但实际上它们是一个非常好的树实现，没有任何东西阻止你使用它，而不是使用swing接口。

请注意，从Java 9开始，您可能不希望使用这些类，因为它们不会出现在“紧凑configuration文件”中 。

Answer 4

那这个呢？ （顺便说一句，不pipe我好像尝试了什么，我都不能粘贴网站代码格式化程序会正确处理的代码，对不起。

 import java.util.ArrayList; import java.util.Collection; import java.util.HashMap; /** * @author [e-mail] (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; } } 

Answer 5

我写了一个处理通用树的小型库。 它比摇摆的东西轻得多。 我也有一个maven项目 。

Answer 6

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

显然你可以添加实用的方法来添加/删除子项。

Answer 7

您应该首先定义一个树（对于域），最好通过首先定义接口来完成。 并非所有的树结构都是可修改的，能够添加和删除节点应该是可选function，所以我们为此创build了一个额外的接口。

没有必要创build包含这些值的节点对象 ，事实上，我认为这是大多数树实现中的主要devise缺陷和开销。 如果你看Swing， TreeModel是没有节点类的（只有DefaultTreeModel使用TreeNode ），因为它们并不是真的需要。

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

鉴于这些接口，使用树的代码不必太在意树的实现方式。 这允许您使用generics实现以及专用实现，通过将函数委托给另一个API来实现树。
示例：文件树结构。

 public class MappedTreeStructure<N extends Serializable> implements MutableTree<N> { public static void main(String[] args) { MutableTree<String> tree = new MappedTreeStructure<String>(); tree.add("A", "B"); tree.add("A", "C"); tree.add("C", "D"); tree.add("E", "A"); System.out.println(tree); } private final Map<N, N> nodeParent = new HashMap<N, N>(); private final LinkedHashSet<N> nodeList = new LinkedHashSet<N>(); private void checkNotNull(N node, String parameterName) { if (node == null) throw new IllegalArgumentException(parameterName + " must not be null"); } @Override public boolean add(N parent, N node) { checkNotNull(parent, "parent"); checkNotNull(node, "node"); // check for cycles N current = parent; do { if (node.equals(current)) { throw new IllegalArgumentException(" node must not be the same or an ancestor of the parent"); } } while ((current = getParent(current)) != null); boolean added = nodeList.add(node); nodeList.add(parent); nodeParent.put(node, parent); return added; } @Override public boolean remove(N node, boolean cascade) { checkNotNull(node, "node"); if (!nodeList.contains(node)) { return false; } if (cascade) { for (N child : getChildren(node)) { remove(child, true); } } else { for (N child : getChildren(node)) { nodeParent.remove(child); } } nodeList.remove(node); return true; } @Override public List<N> getRoots() { return getChildren(null); } @Override public N getParent(N node) { checkNotNull(node, "node"); return nodeParent.get(node); } @Override public List<N> getChildren(N node) { List<N> children = new LinkedList<N>(); for (N n : nodeList) { N parent = nodeParent.get(n); if (node == null && parent == null) { children.add(n); } else if (node != null && parent != null && parent.equals(node)) { children.add(n); } } return children; } @Override public String toString() { StringBuilder builder = new StringBuilder(); dumpNodeStructure(builder, null, "- "); return builder.toString(); } private void dumpNodeStructure(StringBuilder builder, N node, String prefix) { if (node != null) { builder.append(prefix); builder.append(node.toString()); builder.append('\n'); prefix = " " + prefix; } for (N child : getChildren(node)) { dumpNodeStructure(builder, child, prefix); } } } 

Answer 8

没有回答提到过简化，但工作代码，所以这里是：

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

Answer 9

和Gareth的答案一样，检查DefaultMutableTreeNode 。 这不是通用的，但似乎符合法案。 即使它在javax.swing包中，也不依赖于任何AWT或Swing类。 实际上，源代码实际上有注释// ISSUE: this class depends on nothing in AWT -- move to java.util?

Answer 10

您可以使用Java的任何XML API作为文档和节点..因为XML是一个带有string的树结构

Answer 11

Java中有一些树型数据结构，如JDK Swing中的DefaultMutableTreeNode，Stanfordparsing器包中的Tree以及其他玩具代码。 但是这些都不足以满足一般目的。

Java-tree项目试图在Java中提供另一个通用树数据结构。 这和其他人的区别是

• 完全免费。 你可以在任何地方使用（除了作业：P）
• 小但一般不够。 我将数据结构的所有内容放在一个类文件中，因此复制/粘贴会很容易。
• 不只是一个玩具。 我知道许多只能处理二叉树或有限操作的Java树代码。 这个TreeNode远不止于此。 它提供了不同的访问节点的方式，比如前序，后序，广度，叶子，根path等。此外，还提供了迭代器以满足要求。
• 更多的utils将被添加。 我愿意添加更多的操作来使这个项目全面，特别是如果你通过github发送请求。

Answer 12

由于该问题要求提供可用的数据结构，因此可以从列表或数组构build树：

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

instanceof可以用来确定一个元素是一个子树还是一个terminal节点。

Answer 13

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

非常简单，使用起来非常简单。 要使用它，扩展它：

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

Answer 14

如果你正在做白板编码，面试，甚至只是计划使用树，这些冗长的一点点。

应该进一步说，一个树不在那里的原因就像一个Pair （关于它可以这么说），是因为你应该用你的数据封装你的类，最简单的实现看起来像：

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

这是一个任意宽度的树。

如果你想要一个二叉树，使用命名字段通常更容易：

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

或者如果你想要一个trie：

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

现在你说你想要

为了能够得到所有的孩子（某种列表或string数​​组）给定一个inputstring表示给定的节点

这听起来像你的功课。
但是因为我相当确定任何截止date已经过去了…

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

这让你使用像：

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

Answer 15

例如 ：

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

Answer 16

树的自定义Tree实现，而不使用Collection框架。 它包含了树实现中所需的不同基本操作。

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

Answer 17

您可以使用雅加达项目中包含的Apache JMeter中的HashTree类。

HashTree类包含在org.apache.jorphan.collections包中。 虽然这个包不是在JMeter项目之外发布的，但是你可以很容易地获得它：

1）下载JMeter源代码 。

2）创build一个新的包。

3）拷贝它/ src / jorphan / org / apache / jorphan / collections /。 除Data.java外的所有文件

4）也复制/src/jorphan/org/apache/jorphan/util/JOrphanUtils.java

5）HashTree已经可以使用了。

Answer 18

请检查下面的代码，我已经使用了Tree数据结构，而不使用Collection类。 代码可能有错误/改进，但请使用此仅供参考

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

Answer 19

Java中没有适合您需求的特定数据结构。 您的要求是非常具体的，因此您需要devise自己的数据结构。 看着你的需求，任何人都可以说你需要某种具有一些特定function的n-ary树。 您可以按照以下方式devise您的数据结构：

1. 树节点的结构就像节点和孩子列表中的内容一样：class Node {String value; 列出孩子;}
2. 你需要检索给定string的子元素，所以你可以有2个方法1：Node searchNode（String str），将返回与给定input相同值的节点（使用BFS进行search）2：List getChildren（String str）：这个方法将在内部调用searchNode来获取具有相同string的节点，然后它将创build所有子string值列表并返回。
3. 您还将被要求在树中插入一个string。 你将不得不写一个方法说空插入（string父，string值）：这将再次search的价值等于父母的节点，然后你可以创build一个具有给定值的节点，并添加到孩子列表find父。

我build议，你写一个类的节点结构像类节点{string值; 列表中的孩子;}和所有其他方法，如search，插入和getChildren在另一个NodeUtils类，以便您还可以传递树的根在特定的树上执行操作，如：class NodeUtils {public static Node search（Node root，String value） {//执行BFS并返回节点}

Answer 20

在过去，我刚刚使用了一个嵌套的地图。 这是我今天使用的，它非常简单，但它适合我的需求。 也许这会帮助另一个。

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

Answer 21

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

Answer 22

我写了一个与Java8很好地玩的树库，没有其他的依赖。 它还提供了对函数式编程的一些想法的宽松解释，并允许您映射/过滤/修剪/search整个树或子树。

https://github.com/RutledgePaulV/prune

这个实现并没有对索引做任何特殊的处理，而且我也没有偏离recursion，所以有可能大树性能会下降，你可能会把堆栈炸掉。 但是，如果你所需要的只是一个中等深度的简单树，我认为它工作得很好。 它提供了一个理智的（基于价值的）平等的定义，它也有一个toString的实现，让你可视化的树！

Answer 23

您可以使用java.util。*中的TreeSet类。 它像Binarysearch树一样工作，所以它已经被sorting。 TreeSet类实现Iterable，Collection和Set接口。 你可以像迭代一样遍历遍历树。

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

你可以检查， Java Doc和其他一些。