在Java中是否有标准的Java库类来表示树?
具体来说,我需要表示以下内容:
任意节点上的子树可以有任意数量的子树 每个节点(根节点之后)及其子节点都有字符串值 我需要得到一个给定节点的所有子(某种类型的列表或字符串数组),它的字符串值(即。一个方法,将一个节点作为输入,并返回子节点的所有字符串值作为输出)
是否有任何可用的结构,或者我需要创建我自己的(如果是这样,实施建议将是伟大的)。
在Java中是否有标准的Java库类来表示树?
具体来说,我需要表示以下内容:
任意节点上的子树可以有任意数量的子树 每个节点(根节点之后)及其子节点都有字符串值 我需要得到一个给定节点的所有子(某种类型的列表或字符串数组),它的字符串值(即。一个方法,将一个节点作为输入,并返回子节点的所有字符串值作为输出)
是否有任何可用的结构,或者我需要创建我自己的(如果是这样,实施建议将是伟大的)。
当前回答
首先应该定义什么是树(对于域),最好先定义接口。并不是所有的树结构都是可修改的,能够添加和删除节点应该是一个可选的功能,所以我们为此做了一个额外的接口。
没有必要创建保存值的节点对象,事实上,我认为这是大多数树实现中的主要设计缺陷和开销。如果查看Swing, TreeModel没有节点类(只有DefaultTreeModel使用TreeNode),因为实际上并不需要它们。
public interface Tree <N extends Serializable> extends Serializable {
List<N> getRoots ();
N getParent (N node);
List<N> getChildren (N node);
}
可变树结构(允许添加和删除节点):
public interface MutableTree <N extends Serializable> extends Tree<N> {
boolean add (N parent, N node);
boolean remove (N node, boolean cascade);
}
有了这些接口,使用树的代码就不必太关心树是如何实现的。这允许您使用通用实现和专用实现,在专用实现中,通过将函数委托给另一个API来实现树。
例如:文件树结构
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();
}
}
示例:通用树结构(基于父/子关系):
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);
}
}
}
其他回答
我编写了一个树库,它可以很好地使用Java8,并且没有其他依赖项。它还提供了对函数式编程的一些思想的松散解释,并允许您映射/过滤/修剪/搜索整个树或子树。
https://github.com/RutledgePaulV/prune
这个实现在索引方面没有做任何特别的事情,而且我也没有偏离递归,所以使用大型树的性能可能会下降,可能会破坏堆栈。但如果你所需要的只是一个简单的小到中等深度的树,我认为它已经足够好了。它提供了一个健全的(基于值的)相等定义,它还有一个toString实现,可以让您可视化树!
没有回答提到过度简化但有效的代码,所以下面是:
public class TreeNodeArray<T> {
public T value;
public final java.util.List<TreeNodeArray<T>> kids = new java.util.ArrayList<TreeNodeArray<T>>();
}
与Gareth的答案相同,请检查DefaultMutableTreeNode。它不是一般的,但在其他方面似乎符合要求。即使它在javax中。swing包,它不依赖于任何AWT或swing类。事实上,源代码实际上有注释// ISSUE:这个类不依赖于AWT中的任何东西——移到java.util?
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;
}
}
显然,您可以添加实用工具方法来添加/删除子元素。
在过去,我只是为此使用了一个嵌套映射。这是我今天用的,它很简单,但它符合我的需要。也许这能帮到另一个人。
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"));
}
}