在Java中是否有标准的Java库类来表示树?
具体来说，我需要表示以下内容:
任意节点上的子树可以有任意数量的子树 每个节点(根节点之后)及其子节点都有字符串值 我需要得到一个给定节点的所有子(某种类型的列表或字符串数组)，它的字符串值(即。一个方法，将一个节点作为输入，并返回子节点的所有字符串值作为输出)
是否有任何可用的结构，或者我需要创建我自己的(如果是这样，实施建议将是伟大的)。
当前回答
请检查下面的代码，其中我使用了Tree数据结构，没有使用Collection类。代码可能有bug /改进，但请使用这只是作为参考
package com.datastructure.tree;
public class BinaryTreeWithoutRecursion <T> {
private TreeNode<T> root;
public BinaryTreeWithoutRecursion (){
root = null;
}
public void insert(T data){
root =insert(root, data);
}
public TreeNode<T> insert(TreeNode<T> node, T data ){
TreeNode<T> newNode = new TreeNode<>();
newNode.data = data;
newNode.right = newNode.left = null;
if(node==null){
node = newNode;
return node;
}
Queue<TreeNode<T>> queue = new Queue<TreeNode<T>>();
queue.enque(node);
while(!queue.isEmpty()){
TreeNode<T> temp= queue.deque();
if(temp.left!=null){
queue.enque(temp.left);
}else
{
temp.left = newNode;
queue =null;
return node;
}
if(temp.right!=null){
queue.enque(temp.right);
}else
{
temp.right = newNode;
queue =null;
return node;
}
}
queue=null;
return node;
}
public void inOrderPrint(TreeNode<T> root){
if(root!=null){
inOrderPrint(root.left);
System.out.println(root.data);
inOrderPrint(root.right);
}
}
public void postOrderPrint(TreeNode<T> root){
if(root!=null){
postOrderPrint(root.left);
postOrderPrint(root.right);
System.out.println(root.data);
}
}
public void preOrderPrint(){
preOrderPrint(root);
}
public void inOrderPrint(){
inOrderPrint(root);
}
public void postOrderPrint(){
inOrderPrint(root);
}
public void preOrderPrint(TreeNode<T> root){
if(root!=null){
System.out.println(root.data);
preOrderPrint(root.left);
preOrderPrint(root.right);
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
BinaryTreeWithoutRecursion <Integer> ls= new BinaryTreeWithoutRecursion <>();
ls.insert(1);
ls.insert(2);
ls.insert(3);
ls.insert(4);
ls.insert(5);
ls.insert(6);
ls.insert(7);
//ls.preOrderPrint();
ls.inOrderPrint();
//ls.postOrderPrint();
}
}
其他回答
我写了一个处理通用树的小库。它比秋千轻多了。我也有一个专门的项目。
首先应该定义什么是树(对于域)，最好先定义接口。并不是所有的树结构都是可修改的，能够添加和删除节点应该是一个可选的功能，所以我们为此做了一个额外的接口。
没有必要创建保存值的节点对象，事实上，我认为这是大多数树实现中的主要设计缺陷和开销。如果查看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);
}
}
}
我写了一个基于“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(", "));
}
你会得到一棵漂亮的树。它应该很容易适应你的需要。
您可以使用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可以使用了。
例如:
import java.util.ArrayList;
import java.util.List;
/**
*
* @author X2
*
* @param <T>
*/
public class HisTree<T>
{
private Node<T> root;
public HisTree(T rootData)
{
root = new Node<T>();
root.setData(rootData);
root.setChildren(new ArrayList<Node<T>>());
}
}
class Node<T>
{
private T data;
private Node<T> parent;
private List<Node<T>> children;
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public Node<T> getParent() {
return parent;
}
public void setParent(Node<T> parent) {
this.parent = parent;
}
public List<Node<T>> getChildren() {
return children;
}
public void setChildren(List<Node<T>> children) {
this.children = children;
}
}
推荐文章
- 在流中使用Java 8 foreach循环移动到下一项
- 访问限制:'Application'类型不是API(必需库rt.jar的限制)
- 用Java计算两个日期之间的天数
- 如何配置slf4j-simple
- 在Jar文件中运行类
- 带参数的可运行?
- 我如何得到一个字符串的前n个字符而不检查大小或出界?
- 我可以在Java中设置enum起始值吗?
- Java中的回调函数
- c#和Java中的泛型有什么不同?和模板在c++ ?
- 在Java中，流相对于循环的优势是什么?
- Jersey在未找到InjectionManagerFactory时停止工作
- 在Java流是peek真的只是调试?
- Recyclerview不调用onCreateViewHolder
- 将JSON字符串转换为HashMap
