在Java中是否有标准的Java库类来表示树?
具体来说，我需要表示以下内容:
任意节点上的子树可以有任意数量的子树 每个节点(根节点之后)及其子节点都有字符串值 我需要得到一个给定节点的所有子(某种类型的列表或字符串数组)，它的字符串值(即。一个方法，将一个节点作为输入，并返回子节点的所有字符串值作为输出)
是否有任何可用的结构，或者我需要创建我自己的(如果是这样，实施建议将是伟大的)。
当前回答
import java.util.Collection;
import java.util.LinkedList;
import java.util.function.BiConsumer;
import java.util.function.Function;
/**
* @author changjin wei(魏昌进)
* @since 2021/7/15
*/
public class TreeUtils {
private TreeUtils() {
}
/**
* @param collection this is a collection of elements
* @param getId this is a getId Function
* @param getParentId this is a getParentId Function
* @param setNode this is a setNode BiConsumer
* @param <E> the type of elements in this collection
* @param <R> the type of the result of the function
*
* @return Collection
*/
public static <E, R> Collection<E> tree(Collection<E> collection, Function<E, R> getId, Function<E, R> getParentId, BiConsumer<E, Collection<E>> setNode) {
Collection<E> root = new LinkedList<>();
for (E node : collection) {
R parentId = getParentId.apply(node);
R id = getId.apply(node);
Collection<E> elements = new LinkedList<>();
boolean isParent = true;
for (E element : collection) {
if (id.equals(getParentId.apply(element))) {
elements.add(element);
}
if (isParent && getId.apply(element).equals(parentId)) {
isParent = false;
}
}
if (isParent) {
root.add(node);
}
setNode.accept(node, elements);
}
return root;
}
}
其他回答
与Gareth的答案相同，请检查DefaultMutableTreeNode。它不是一般的，但在其他方面似乎符合要求。即使它在javax中。swing包，它不依赖于任何AWT或swing类。事实上，源代码实际上有注释// ISSUE:这个类不依赖于AWT中的任何东西——移到java.util?
在这里:
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或任何其他对象。实现简单的树来满足您的需要是相当容易的。
您需要添加的只是用于添加、删除、遍历和构造函数的方法。节点是树的基本构建块。
在过去，我只是为此使用了一个嵌套映射。这是我今天用的，它很简单，但它符合我的需要。也许这能帮到另一个人。
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"));
}
}
import java.util.Collection;
import java.util.LinkedList;
import java.util.function.BiConsumer;
import java.util.function.Function;
/**
* @author changjin wei(魏昌进)
* @since 2021/7/15
*/
public class TreeUtils {
private TreeUtils() {
}
/**
* @param collection this is a collection of elements
* @param getId this is a getId Function
* @param getParentId this is a getParentId Function
* @param setNode this is a setNode BiConsumer
* @param <E> the type of elements in this collection
* @param <R> the type of the result of the function
*
* @return Collection
*/
public static <E, R> Collection<E> tree(Collection<E> collection, Function<E, R> getId, Function<E, R> getParentId, BiConsumer<E, Collection<E>> setNode) {
Collection<E> root = new LinkedList<>();
for (E node : collection) {
R parentId = getParentId.apply(node);
R id = getId.apply(node);
Collection<E> elements = new LinkedList<>();
boolean isParent = true;
for (E element : collection) {
if (id.equals(getParentId.apply(element))) {
elements.add(element);
}
if (isParent && getId.apply(element).equals(parentId)) {
isParent = false;
}
}
if (isParent) {
root.add(node);
}
setNode.accept(node, elements);
}
return root;
}
}
我对所有这些方法都有意见。
我使用的是“MappedTreeStructure”实现。这个实现很好地重新组织了树，并且不包含节点的“副本”。
但是没有提供分级方法。
看看那些有问题的输出!
MutableTree<String> tree = new MappedTreeStructure<>();
tree.add("0", "1");
tree.add("0", "2");
tree.add("0", "3");
tree.add("0", "4");
tree.add("0", "5");
tree.add("2", "3");
tree.add("2", "5");
tree.add("1", "2");
tree.add("1", "3");
tree.add("1", "5");
System.out.println(
tree.toString()
);
哪个输出:(错误)
- 0
- 1
- 2
- 3
- 5
- 4
还有这个:(正确)
tree = new MappedTreeStructure<>();
tree.add("0", "1");
tree.add("0", "2");
tree.add("0", "3");
tree.add("0", "4");
tree.add("0", "5");
tree.add("1", "2");
tree.add("1", "3");
tree.add("1", "5");
tree.add("2", "3");
tree.add("2", "5");
System.out.println(
tree.toString()
);
正确的输出:
- 0
- 1
- 2
- 3
- 5
- 4
如此!我创建了另一个实现来欣赏。请给一些建议和反馈!
package util;
import java.util.HashMap;
import java.util.Map;
public class Node<N extends Comparable<N>> {
public final Map<N, Node<N>> parents = new HashMap<>();
public final N value;
public final Map<N, Node<N>> children = new HashMap<>();
public Node(N value) {
this.value = value;
}
}
package util;
import java.util.*;
import java.util.stream.Collectors;
public class HierarchyTree<N extends Comparable<N>> {
protected final Map<N, Node<N>> nodeList = new HashMap<>();
public static <T extends Comparable<T>> Node<T> state(Map<T, Node<T>> nodeList, T node) {
Node<T> tmp = nodeList.getOrDefault(node, new Node<>(node));
nodeList.putIfAbsent(node, tmp);
return tmp;
}
public static <T extends Comparable<T>> Node<T> state(Map<T, Node<T>> nodeList, Node<T> node) {
Node<T> tmp = nodeList.getOrDefault(node.value, node);
nodeList.putIfAbsent(node.value, tmp);
return tmp;
}
public Node<N> state(N child) {
return state(nodeList, child);
}
public Node<N> stateChild(N parent, N child) {
Node<N> pai = state(parent);
Node<N> filho = state(child);
state(pai.children, filho);
state(filho.parents, pai);
return filho;
}
public List<Node<N>> addChildren(List<N> children) {
List<Node<N>> retorno = new LinkedList<>();
for (N child : children) {
retorno.add(state(child));
}
return retorno;
}
public List<Node<N>> addChildren(N parent, List<N> children) {
List<Node<N>> retorno = new LinkedList<>();
for (N child : children) {
retorno.add(stateChild(parent, child));
}
return retorno;
}
public List<Node<N>> addChildren(N parent, N... children) {
return addChildren(parent, Arrays.asList(children));
}
public List<Node<N>> getRoots() {
return nodeList.values().stream().filter(value -> value.parents.size() == 0).collect(Collectors.toList());
}
@Override
public String toString() {
return deepPrint("- ");
}
public String deepPrint(String prefix) {
StringBuilder builder = new StringBuilder();
deepPrint(builder, prefix, "", getRoots());
return builder.toString();
}
protected void deepPrint(StringBuilder builder, String prefix, String sep, List<Node<N>> node) {
for (Node<N> item : node) {
builder.append(sep).append(item.value).append("\n");
deepPrint(builder, prefix, sep + prefix, new ArrayList<>(item.children.values()));
}
}
public SortedMap<Long, Set<N>> tree() {
SortedMap<Long, Set<N>> tree = new TreeMap<>();
tree(0L, tree, getRoots());
return tree;
}
protected void tree(Long i, SortedMap<Long, Set<N>> tree, List<Node<N>> roots) {
for (Node<N> node : roots) {
Set<N> tmp = tree.getOrDefault(i, new HashSet<>());
tree.putIfAbsent(i, tmp);
tmp.add(node.value);
tree(i + 1L, tree, new ArrayList<>(node.children.values()));
}
}
public void prune() {
Set<N> nodes = new HashSet<>();
SortedMap<Long, Set<N>> tree = tree();
List<Long> treeInverse = tree.keySet().stream().sorted(Comparator.reverseOrder()).collect(Collectors.toList());
for (Long treeItem : treeInverse) {
for (N n : tree.get(treeItem)) {
Map<N, Node<N>> children = nodeList.get(n).children;
for (N node : nodes) {
children.remove(node);
}
nodes.addAll(children.keySet());
}
}
}
public static void main(String[] args) {
HierarchyTree<Integer> tree = new HierarchyTree<>();
tree.addChildren(Arrays.asList(1, 2, 3, 4, 5));
tree.addChildren(1, Arrays.asList(2, 3, 5));
tree.addChildren(2, Arrays.asList(3, 5));
tree.prune();
System.out.println(tree);
tree = new HierarchyTree<>();
tree.addChildren(Arrays.asList(1, 2, 3, 4, 5));
tree.addChildren(2, Arrays.asList(3, 5));
tree.addChildren(1, Arrays.asList(2, 3, 5));
tree.prune();
System.out.println(tree);
}
}
输出总是正确的:
1
- 2
- - 3
- - 5
4
1
- 2
- - 3
- - 5
4
推荐文章
- 如何在java中格式化持续时间?(如格式H:MM:SS)
- urlencoder .encode(字符串)已弃用，我应该使用什么代替?
- javax.transaction.Transactional vs . org.springframework.transaction.annotation.Transactional
- Java 8接口方法中不允许“同步”的原因是什么?
- 如何找到Java堆大小和内存使用(Linux)?
- set()是如何实现的?
- 使用Enum实现单例(Java)
- RabbitMQ与通道和连接之间的关系
- buildSessionFactory()配置方法在Hibernate中已弃用?
- Spring MVC -如何获得所有的请求参数在一个地图在Spring控制器?
- 如何在Java中按两个字段排序?
- 文件之间的差异。路径中的分隔符和斜杠
- 在方法参数中使用NotNull注释
- Spring MVC中处理可选参数的@RequestParam
- Tomcat:如何查找正在运行的Tomcat版本?
