在Java中是否有标准的Java库类来表示树?
具体来说，我需要表示以下内容:
任意节点上的子树可以有任意数量的子树 每个节点(根节点之后)及其子节点都有字符串值 我需要得到一个给定节点的所有子(某种类型的列表或字符串数组)，它的字符串值(即。一个方法，将一个节点作为输入，并返回子节点的所有字符串值作为输出)
是否有任何可用的结构，或者我需要创建我自己的(如果是这样，实施建议将是伟大的)。
当前回答
与Gareth的答案相同，请检查DefaultMutableTreeNode。它不是一般的，但在其他方面似乎符合要求。即使它在javax中。swing包，它不依赖于任何AWT或swing类。事实上，源代码实际上有注释// ISSUE:这个类不依赖于AWT中的任何东西——移到java.util?
其他回答
例如:
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;
}
}
简单的例子:
public class ArbrePlaner {
public static void main(String[] args) {
ArbrePlaner ll = new ArbrePlaner();
ll.add(1,"A");
ll.add(2,"B");
ll.add(1,"C");
ll.add(3,"D");
ll.add(1,"Z");
for(int i = 0; i < ll.size; i++){
// System.out.println(ll.isIdExist(i));
System.out.println("-----------------");
System.out.println(ll.getIdAt(i)+" :");
linkedList lst = ll.getListDataById(ll.getIdAt(i));
for(int j = 0; j < lst.size; j++){
System.out.println(lst.getElementAt(j));
}
}
}
private int size;
private Noeud root;
public Noeud add(long Id, Object data){
if(isIdExist(Id)){
Noeud nd = getNoeudId(Id);
nd.add(data);
return nd;
}else{
Noeud nd = new Noeud(Id, data, this.root);
this.root = nd;
this.size++;
return nd;
}
}
public Object getDataById(long Id, int x){
Noeud thisNode = this.root;
while(thisNode!=null){
if(thisNode.getId() == Id){
return thisNode.getLl().getElementAt(x);
}
thisNode = thisNode.getNextNoeud();
}
return null;
}
public long getIdAt(int x){
if(size >= x){
Noeud nd = this.root;
for(int i = 0; i<x; i++)try {nd = nd.getNextNoeud();} catch (Exception e) {return -1;}
return nd.getId();
}
return -1;
}
public linkedList getListDataById(long Id){
Noeud thisNode = this.root;
while(thisNode!=null){
if(thisNode.getId() == Id){
return thisNode.getLl();
}
thisNode = thisNode.getNextNoeud();
}
return null;
}
public boolean deleteById(long id){
Noeud thisNode = this.root;
Noeud prevNode = null;
while(thisNode != null){
if(thisNode.getId() == id){
prevNode.setNextNoeud(thisNode.getNextNoeud());
this.setSize(this.getSize()-1);
return true;
}
prevNode = thisNode;
thisNode = thisNode.getNextNoeud();
}
return false;
}
public boolean isIdExist(long Id){
Noeud thisNode = this.root;
while(thisNode!=null){
if(thisNode.getId()== Id){
return true;
}
thisNode = thisNode.getNextNoeud();
}
return false;
}
public boolean isDataExist(long Id, Object data){
if(isIdExist(Id)){
Noeud thisNode = this.root;
while(thisNode!=null){
if(thisNode.getId() == Id){
linkedList ll = thisNode.getLl();
long x = ll.hashCode();
long y = data.hashCode();
if(x==y) return true;
}
thisNode = thisNode.getNextNoeud();
}
}
return false;
}
public Noeud getNoeudId(long Id){
Noeud thisNode = this.root;
while(thisNode!=null){
if(thisNode.getId() == Id){
return thisNode;
}
thisNode = thisNode.getNextNoeud();
}
return null;
}
public ArbrePlaner() {
this.root = root;
}
public ArbrePlaner(Noeud root) {
this.root = root;
}
public ArbrePlaner(int size, Noeud root) {
this.size = size;
this.root = root;
}
public int getSize() {
return size;
}
public void setSize(int size) {
this.size = size;
}
public Noeud getRoot() {
return root;
}
public void setRoot(Noeud root) {
this.root = root;
}
private class Noeud{
private long id;
private Noeud nextNoeud;
private linkedList Ll;
public void add(Object data){
Ll.add(data);
}
public Noeud(long id, Object data ,Noeud nextNoeud){
this.id = id;
this.nextNoeud = nextNoeud;
Ll = new linkedList();
Ll.add(data);
}
public long getId() {
return id;
}
public Noeud(Object data){
Ll.add(data);
}
public void setId(long id) {
this.id = id;
}
public Noeud getNextNoeud() {
return nextNoeud;
}
public void setNextNoeud(Noeud nextNoeud) {
this.nextNoeud = nextNoeud;
}
public linkedList getLl() {
return Ll;
}
public void setLl(linkedList ll) {
Ll = ll;
}
}
}
在这里:
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或任何其他对象。实现简单的树来满足您的需要是相当容易的。
您需要添加的只是用于添加、删除、遍历和构造函数的方法。节点是树的基本构建块。
我对所有这些方法都有意见。
我使用的是“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
首先应该定义什么是树(对于域)，最好先定义接口。并不是所有的树结构都是可修改的，能够添加和删除节点应该是一个可选的功能，所以我们为此做了一个额外的接口。
没有必要创建保存值的节点对象，事实上，我认为这是大多数树实现中的主要设计缺陷和开销。如果查看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);
}
}
}
推荐文章
- 在流中使用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
