在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
[]
其他回答
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并返回节点}
你可以使用Java的任何XML API作为文档和节点..因为XML是一个带有字符串的树结构
这个呢?
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.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;
}
}
在过去,我只是为此使用了一个嵌套映射。这是我今天用的,它很简单,但它符合我的需要。也许这能帮到另一个人。
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"));
}
}