在Java中是否有标准的Java库类来表示树?
具体来说,我需要表示以下内容:
任意节点上的子树可以有任意数量的子树 每个节点(根节点之后)及其子节点都有字符串值 我需要得到一个给定节点的所有子(某种类型的列表或字符串数组),它的字符串值(即。一个方法,将一个节点作为输入,并返回子节点的所有字符串值作为输出)
是否有任何可用的结构,或者我需要创建我自己的(如果是这样,实施建议将是伟大的)。
在Java中是否有标准的Java库类来表示树?
具体来说,我需要表示以下内容:
任意节点上的子树可以有任意数量的子树 每个节点(根节点之后)及其子节点都有字符串值 我需要得到一个给定节点的所有子(某种类型的列表或字符串数组),它的字符串值(即。一个方法,将一个节点作为输入,并返回子节点的所有字符串值作为输出)
是否有任何可用的结构,或者我需要创建我自己的(如果是这样,实施建议将是伟大的)。
当前回答
如果您正在编写白板代码、进行面试,或者只是计划使用树,那么这些内容就有点冗长了。
应该进一步说,树不像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 {
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;
}
}
显然,您可以添加实用工具方法来添加/删除子元素。
JDK中实际上实现了一个非常好的树结构。
看看javax.swing。tree、TreeModel和TreeNode。它们被设计为与JTreePanel一起使用,但实际上,它们是一个非常好的树实现,没有什么可以阻止你使用它与swing接口。
注意,从Java 9开始,你可能不希望使用这些类,因为它们不会出现在“压缩配置文件”中。
如果您正在编写白板代码、进行面试,或者只是计划使用树,那么这些内容就有点冗长了。
应该进一步说,树不像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
[]
您可以使用Apache JMeter中包含的HashTree类,它是Jakarta项目的一部分。
HashTree类包含在包org.apache.jorphan.collections中。虽然这个包没有在JMeter项目之外发布,但你可以很容易地获得它:
1)下载JMeter源代码。
2)创建一个新包。
3)复制到/src/jorphan/org/apache/jorphan/collections/。除了Data.java之外的所有文件
4)复制/src/jorphan/ org/apache/jorphan/uti/jorphanutils .java
5) HashTree可以使用了。
我编写了一个树库,它可以很好地使用Java8,并且没有其他依赖项。它还提供了对函数式编程的一些思想的松散解释,并允许您映射/过滤/修剪/搜索整个树或子树。
https://github.com/RutledgePaulV/prune
这个实现在索引方面没有做任何特别的事情,而且我也没有偏离递归,所以使用大型树的性能可能会下降,可能会破坏堆栈。但如果你所需要的只是一个简单的小到中等深度的树,我认为它已经足够好了。它提供了一个健全的(基于值的)相等定义,它还有一个toString实现,可以让您可视化树!