在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();
}
}
其他回答
我对所有这些方法都有意见。
我使用的是“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
JDK中实际上实现了一个非常好的树结构。
看看javax.swing。tree、TreeModel和TreeNode。它们被设计为与JTreePanel一起使用，但实际上，它们是一个非常好的树实现，没有什么可以阻止你使用它与swing接口。
注意，从Java 9开始，你可能不希望使用这些类，因为它们不会出现在“压缩配置文件”中。
还有另一种树结构:
public class TreeNode<T> implements Iterable<TreeNode<T>> {
T data;
TreeNode<T> parent;
List<TreeNode<T>> children;
public TreeNode(T data) {
this.data = data;
this.children = new LinkedList<TreeNode<T>>();
}
public TreeNode<T> addChild(T child) {
TreeNode<T> childNode = new TreeNode<T>(child);
childNode.parent = this;
this.children.add(childNode);
return childNode;
}
// other features ...
}
示例用法:
TreeNode<String> root = new TreeNode<String>("root");
{
TreeNode<String> node0 = root.addChild("node0");
TreeNode<String> node1 = root.addChild("node1");
TreeNode<String> node2 = root.addChild("node2");
{
TreeNode<String> node20 = node2.addChild(null);
TreeNode<String> node21 = node2.addChild("node21");
{
TreeNode<String> node210 = node20.addChild("node210");
}
}
}
奖金 见羽翼丰满的树与:
迭代器 搜索 Java / c#
https://github.com/gt4dev/yet-another-tree-structure
与Gareth的答案相同，请检查DefaultMutableTreeNode。它不是一般的，但在其他方面似乎符合要求。即使它在javax中。swing包，它不依赖于任何AWT或swing类。事实上，源代码实际上有注释// ISSUE:这个类不依赖于AWT中的任何东西——移到java.util?
在这里:
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或任何其他对象。实现简单的树来满足您的需要是相当容易的。
您需要添加的只是用于添加、删除、遍历和构造函数的方法。节点是树的基本构建块。
推荐文章
- 在流中使用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
