在Java中是否有标准的Java库类来表示树?
具体来说,我需要表示以下内容:
任意节点上的子树可以有任意数量的子树 每个节点(根节点之后)及其子节点都有字符串值 我需要得到一个给定节点的所有子(某种类型的列表或字符串数组),它的字符串值(即。一个方法,将一个节点作为输入,并返回子节点的所有字符串值作为输出)
是否有任何可用的结构,或者我需要创建我自己的(如果是这样,实施建议将是伟大的)。
在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;
}
}
其他回答
我编写了一个树库,它可以很好地使用Java8,并且没有其他依赖项。它还提供了对函数式编程的一些思想的松散解释,并允许您映射/过滤/修剪/搜索整个树或子树。
https://github.com/RutledgePaulV/prune
这个实现在索引方面没有做任何特别的事情,而且我也没有偏离递归,所以使用大型树的性能可能会下降,可能会破坏堆栈。但如果你所需要的只是一个简单的小到中等深度的树,我认为它已经足够好了。它提供了一个健全的(基于值的)相等定义,它还有一个toString实现,可以让您可视化树!
如果您正在编写白板代码、进行面试,或者只是计划使用树,那么这些内容就有点冗长了。
应该进一步说,树不像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;
}
现在你说你想要
给定一个表示给定节点的输入字符串,能够获得所有的子节点(某种类型的列表或字符串数组)
听起来像是你的家庭作业。 但既然我有理由相信任何最后期限都已经过去了……
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
[]
在这里:
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或任何其他对象。实现简单的树来满足您的需要是相当容易的。
您需要添加的只是用于添加、删除、遍历和构造函数的方法。节点是树的基本构建块。
由于问题要求可用的数据结构,树可以由列表或数组构造:
Object[] tree = new Object[2];
tree[0] = "Hello";
{
Object[] subtree = new Object[2];
subtree[0] = "Goodbye";
subtree[1] = "";
tree[1] = subtree;
}
Instanceof可用于确定元素是子树还是终端节点。
不使用Collection框架的Tree的自定义树实现。 它包含Tree实现所需的不同基本操作。
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);
}
}