在Java中是否有标准的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;
}
}
其他回答
这个呢?
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;
}
}
Java中没有适合您需求的特定数据结构。您的需求非常具体，因此需要设计自己的数据结构。看看你的需求，任何人都可以说你需要某种具有特定功能的n元树。你可以通过以下方式设计你的数据结构:
Structure of the node of the tree would be like content in the node and list of children like: class Node { String value; List children;} You need to retrieve the children of a given string, so you can have 2 methods 1: Node searchNode(String str), will return the node that has the same value as given input (use BFS for searching) 2: List getChildren(String str): this method will internally call the searchNode to get the node having same string and then it will create the list of all string values of children and return. You will also be required to insert a string in tree. You will have to write one method say void insert(String parent, String value): this will again search the node having value equal to parent and then you can create a Node with given value and add to the list of children to the found parent.
我建议，你写一个类的节点结构类节点{字符串值;在另一个NodeUtils类中列出children;}和所有其他方法，如search, insert和getChildren，这样你也可以传递树的根来对特定的树执行操作，例如: 类NodeUtils{公共静态节点搜索(节点根，字符串值){//执行BFS并返回节点}
在过去，我只是为此使用了一个嵌套映射。这是我今天用的，它很简单，但它符合我的需要。也许这能帮到另一个人。
import com.fasterxml.jackson.annotation.JsonValue;
import com.fasterxml.jackson.databind.ObjectMapper;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
/**
* Created by kic on 16.07.15.
*/
public class NestedMap<K, V> {
private final Map root = new HashMap<>();
public NestedMap<K, V> put(K key) {
Object nested = root.get(key);
if (nested == null || !(nested instanceof NestedMap)) root.put(key, nested = new NestedMap<>());
return (NestedMap<K, V>) nested;
}
public Map.Entry<K,V > put(K key, V value) {
root.put(key, value);
return (Map.Entry<K, V>) root.entrySet().stream().filter(e -> ((Map.Entry) e).getKey().equals(key)).findFirst().get();
}
public NestedMap<K, V> get(K key) {
return (NestedMap<K, V>) root.get(key);
}
public V getValue(K key) {
return (V) root.get(key);
}
@JsonValue
public Map getRoot() {
return root;
}
public static void main(String[] args) throws Exception {
NestedMap<String, Integer> test = new NestedMap<>();
test.put("a").put("b").put("c", 12);
Map.Entry<String, Integer> foo = test.put("a").put("b").put("d", 12);
test.put("b", 14);
ObjectMapper mapper = new ObjectMapper();
System.out.println(mapper.writeValueAsString(test));
foo.setValue(99);
System.out.println(mapper.writeValueAsString(test));
System.out.println(test.get("a").get("b").getValue("d"));
}
}
我写了一个基于“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(", "));
}
你会得到一棵漂亮的树。它应该很容易适应你的需要。
简单的例子:
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;
}
}
}
推荐文章
- 在流中使用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
