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

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

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

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


当前回答

没有回答提到过度简化但有效的代码,所以下面是:

public class TreeNodeArray<T> {
    public T value;
    public final  java.util.List<TreeNodeArray<T>> kids =  new java.util.ArrayList<TreeNodeArray<T>>();
}

其他回答

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并返回节点}

由于问题要求可用的数据结构,树可以由列表或数组构造:

Object[] tree = new Object[2];
tree[0] = "Hello";
{
  Object[] subtree = new Object[2];
  subtree[0] = "Goodbye";
  subtree[1] = "";
  tree[1] = subtree;
}

Instanceof可用于确定元素是子树还是终端节点。

不使用Collection框架的Tree的自定义树实现。 它包含Tree实现所需的不同基本操作。

class Node {

    int data;
    Node left;
    Node right;

    public Node(int ddata, Node left, Node right) {
        this.data = ddata;
        this.left = null;
        this.right = null;      
    }

    public void displayNode(Node n) {
        System.out.print(n.data + " "); 
    }

}

class BinaryTree {

    Node root;

    public BinaryTree() {
        this.root = null;
    }

    public void insertLeft(int parent, int leftvalue ) {
        Node n = find(root, parent);
        Node leftchild = new Node(leftvalue, null, null);
        n.left = leftchild;
    }

    public void insertRight(int parent, int rightvalue) {
        Node n = find(root, parent);
        Node rightchild = new Node(rightvalue, null, null);
        n.right = rightchild;
    }

    public void insertRoot(int data) {
        root = new Node(data, null, null);
    }

    public Node getRoot() {
        return root;
    }

    public Node find(Node n, int key) {     
        Node result = null;

        if (n == null)
            return null;

        if (n.data == key)
            return n;

        if (n.left != null)
            result = find(n.left, key);

        if (result == null)
            result = find(n.right, key);

        return result;
    } 

    public int getheight(Node root){
        if (root == null)
            return 0;

        return Math.max(getheight(root.left), getheight(root.right)) + 1; 
    }

    public void printTree(Node n) {     
        if (n == null)
            return;

        printTree(n.left);
        n.displayNode(n);
        printTree(n.right);             
    }

}

JDK中实际上实现了一个非常好的树结构。

看看javax.swing。tree、TreeModel和TreeNode。它们被设计为与JTreePanel一起使用,但实际上,它们是一个非常好的树实现,没有什么可以阻止你使用它与swing接口。

注意,从Java 9开始,你可能不希望使用这些类,因为它们不会出现在“压缩配置文件”中。

我对所有这些方法都有意见。

我使用的是“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