在Java中是否有标准的Java库类来表示树?

具体来说,我需要表示以下内容:

任意节点上的子树可以有任意数量的子树 每个节点(根节点之后)及其子节点都有字符串值 我需要得到一个给定节点的所有子(某种类型的列表或字符串数组),它的字符串值(即。一个方法,将一个节点作为输入,并返回子节点的所有字符串值作为输出)

是否有任何可用的结构,或者我需要创建我自己的(如果是这样,实施建议将是伟大的)。


当前回答

在过去,我只是为此使用了一个嵌套映射。这是我今天用的,它很简单,但它符合我的需要。也许这能帮到另一个人。

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"));
    }
}

其他回答

如果您正在编写白板代码、进行面试,或者只是计划使用树,那么这些内容就有点冗长了。

应该进一步说,树不像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
[]
public class Tree {
    private List<Tree> leaves = new LinkedList<Tree>();
    private Tree parent = null;
    private String data;

    public Tree(String data, Tree parent) {
        this.data = data;
        this.parent = parent;
    }
}

显然,您可以添加实用工具方法来添加/删除子元素。

您可以使用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可以使用了。

你可以使用Java的任何XML API作为文档和节点..因为XML是一个带有字符串的树结构

请检查下面的代码,其中我使用了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();

    }

}