在Java中是否有标准的Java库类来表示树?
具体来说,我需要表示以下内容:
任意节点上的子树可以有任意数量的子树 每个节点(根节点之后)及其子节点都有字符串值 我需要得到一个给定节点的所有子(某种类型的列表或字符串数组),它的字符串值(即。一个方法,将一个节点作为输入,并返回子节点的所有字符串值作为输出)
是否有任何可用的结构,或者我需要创建我自己的(如果是这样,实施建议将是伟大的)。
在Java中是否有标准的Java库类来表示树?
具体来说,我需要表示以下内容:
任意节点上的子树可以有任意数量的子树 每个节点(根节点之后)及其子节点都有字符串值 我需要得到一个给定节点的所有子(某种类型的列表或字符串数组),它的字符串值(即。一个方法,将一个节点作为输入,并返回子节点的所有字符串值作为输出)
是否有任何可用的结构,或者我需要创建我自己的(如果是这样,实施建议将是伟大的)。
当前回答
没有回答提到过度简化但有效的代码,所以下面是:
public class TreeNodeArray<T> {
public T value;
public final java.util.List<TreeNodeArray<T>> kids = new java.util.ArrayList<TreeNodeArray<T>>();
}
其他回答
我写了一个基于“HashMap”的小“TreeMap”类,它支持添加路径:
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);
}
}
它可以用来存储一个“T”(泛型)类型的树,但(目前)不支持在节点中存储额外的数据。如果你有一个这样的文件:
root, child 1
root, child 1, child 1a
root, child 1, child 1b
root, child 2
root, child 3, child 3a
然后你可以通过执行:
TreeMap<String> root = new TreeMap<>();
Scanner scanner = new Scanner(new File("input.txt"));
while (scanner.hasNextLine()) {
root.put(scanner.nextLine().split(", "));
}
你会得到一棵漂亮的树。它应该很容易适应你的需要。
我编写了一个树库,它可以很好地使用Java8,并且没有其他依赖项。它还提供了对函数式编程的一些思想的松散解释,并允许您映射/过滤/修剪/搜索整个树或子树。
https://github.com/RutledgePaulV/prune
这个实现在索引方面没有做任何特别的事情,而且我也没有偏离递归,所以使用大型树的性能可能会下降,可能会破坏堆栈。但如果你所需要的只是一个简单的小到中等深度的树,我认为它已经足够好了。它提供了一个健全的(基于值的)相等定义,它还有一个toString实现,可以让您可视化树!
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;
...
}
您可以在java.util.*中使用TreeSet类。它像二叉搜索树一样工作,所以它已经排好序了。TreeSet类实现了Iterable、Collection和Set接口。您可以像使用set一样使用迭代器遍历树。
TreeSet<String> treeSet = new TreeSet<String>();
Iterator<String> it = treeSet.Iterator();
while(it.hasNext()){
...
}
你可以检查,Java文档和其他的。
这个呢?
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
/**
* @author ycoppel@google.com (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;
}
}