如何在 Java 中实现树数据结构？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3522454/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to implement a tree data-structure in Java?
提问by ikl
Is there any standard Java library class to represent a tree in Java?
是否有任何标准的 Java 库类来表示 Java 中的树？
Specifically I need to represent the following:
具体来说，我需要代表以下内容：
- The sub-tree at any node can have an arbitrary number of children
- Each node (after the root) and it's children will have string value
- I need to get all the children (some sort of list or array of Strings) of a given node and it's string value(i.e. a method that will take a node as input and return all the string values of the children node as output)
- 任何节点的子树可以有任意数量的子节点
- 每个节点（在根之后）及其子节点将具有字符串值
- 我需要获取给定节点的所有子节点（某种列表或字符串数组）及其字符串值（即一种将节点作为输入并返回子节点的所有字符串值作为输出的方法）
Is there any available structure for this or do I need to create my own (if so implementation suggestions would be great).
是否有任何可用的结构，或者我是否需要创建自己的结构（如果有的话，实施建议会很棒）。
回答by jjnguy
Here:
这里：
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;
}
}
That is a basic tree structure that can be used for Stringor any other object. It is fairly easy to implement simple trees to do what you need.
这是一个基本的树结构，可用于String或任何其他对象。实现简单的树来做你需要的事情是相当容易的。
All you need to add are methods for add to, removing from, traversing, and constructors. The Nodeis the basic building block of the Tree.
您需要添加的只是用于添加、删除、遍历和构造函数的方法。该Node是对基本构建块Tree。
回答by Gareth Davis
There is actually a pretty good tree structure implemented in the JDK.
在JDK中实际上实现了一个非常好的树结构。
Have a look at javax.swing.tree, TreeModel, and TreeNode. They are designed to be used with the JTreePanelbut they are, in fact, a pretty good tree implementation and there is nothing stopping you from using it with out a swing interface.
查看javax.swing.tree、TreeModel和TreeNode。它们旨在与 一起使用，JTreePanel但实际上，它们是一个非常好的树实现，没有什么可以阻止您在没有 Swing 界面的情况下使用它。
Note that as of Java 9 you may wish not to use these classes as they will not be present in the 'Compact profiles'.
请注意，从 Java 9 开始，您可能不希望使用这些类，因为它们不会出现在“紧凑配置文件”中。
回答by PaulJWilliams
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;
}
}
Obviously you can add utility methods to add/remove children.
显然，您可以添加实用方法来添加/删除子项。
回答by Mark
Along the same lines as Gareth's answer, check out DefaultMutableTreeNode. It's not generic, but otherwise seems to fit the bill. Even though it's in the javax.swing package, it doesn't depend on any AWT or Swing classes. In fact, the source code actually has the comment // ISSUE: this class depends on nothing in AWT -- move to java.util?
与 Gareth 的回答相同，请查看DefaultMutableTreeNode。它不是通用的，但在其他方面似乎符合要求。即使它在 javax.swing 包中，它也不依赖于任何 AWT 或 Swing 类。其实源码里面居然有注释// ISSUE: this class depends on nothing in AWT -- move to java.util?
回答by MountainX
What about this?
那这个呢？
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;
}
}
回答by Vivin Paliath
I wrotea little library that handles generic trees. It's much more lightweight than the swing stuff. I also have a maven projectfor it.
回答by David
You can use the HashTreeclass included in Apache JMeter that is part of the Jakarta Project.
您可以使用Apache JMeter 中包含的HashTree类，它是 Jakarta 项目的一部分。
HashTree class is included in the package org.apache.jorphan.collections. Although this package is not released outside the JMeter project, you can get it easily:
HashTree 类包含在包 org.apache.jorphan.collections 中。虽然这个包没有在 JMeter 项目之外发布，但是你可以很容易地得到它：
1) Download the JMeter sources.
1) 下载JMeter 源代码。
2) Create a new package.
2) 创建一个新包。
3) Copy on it /src/jorphan/org/apache/jorphan/collections/ . All files except Data.java
3）复制它 /src/jorphan/org/apache/jorphan/collections/ 。除 Data.java 之外的所有文件
4) Copy also /src/jorphan/org/apache/jorphan/util/JOrphanUtils.java
4) 也复制 /src/jorphan/org/apache/jorphan/util/JOrphanUtils.java
5) HashTree is ready to use.
5) HashTree 可以使用了。
回答by Raja Nagendra Kumar
You can use any XML API of Java as Document and Node..as XML is a tree structure with Strings
您可以使用 Java 的任何 XML API 作为文档和节点..因为 XML 是带有字符串的树结构
回答by peenut
No answer mentions over-simplified but working code, so here it is:
没有答案提到过度简化但有效的代码，所以这里是：
public class TreeNodeArray<T> {
public T value;
public final java.util.List<TreeNodeArray<T>> kids = new java.util.ArrayList<TreeNodeArray<T>>();
}
回答by Olathe
Since the question asks for an available data structure, a tree can be constructed from lists or arrays:
由于问题要求提供可用的数据结构，因此可以从列表或数组构造树：
Object[] tree = new Object[2];
tree[0] = "Hello";
{
Object[] subtree = new Object[2];
subtree[0] = "Goodbye";
subtree[1] = "";
tree[1] = subtree;
}
instanceofcan be used to determine whether an element is a subtree or a terminal node.
instanceof可用于确定元素是子树还是终端节点。
