还有另一种树结构:

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

在这里:

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中有一些树数据结构，比如JDK Swing中的DefaultMutableTreeNode, Stanford解析器包中的tree，以及其他一些玩具代码。但这些都不够，也不够小，不能用于一般用途。

Java tree项目试图在Java中提供另一种通用的树数据结构。这个和其他的区别是

Totally free. You can use it anywhere (except in your homework :P) Small but general enough. I put everything of the data structure in one class file, so it would be easy to copy/paste. Not just a toys. I am aware of dozens of Java tree codes that can only handle binary trees or limited operations. This TreeNode is much more than that. It provides different ways of visiting nodes, such as preorder, postorder, breadthfirst, leaves, path to root, etc. Moreover, iterators are provided too for the sufficiency. More utils will be added. I am willing to add more operations to make this project comprehensive, especially if you send a request through github.

import java.util.Collection;
import java.util.LinkedList;
import java.util.function.BiConsumer;
import java.util.function.Function;

/**
 * @author changjin wei(魏昌进)
 * @since 2021/7/15
 */
public class TreeUtils {

    private TreeUtils() {
    }

    /**
     * @param collection this is a collection of elements
     * @param getId this is a getId Function
     * @param getParentId this is a getParentId Function
     * @param setNode this is a setNode BiConsumer
     * @param <E> the type of elements in this collection
     * @param <R> the type of the result of the function
     *
     * @return Collection
     */
    public static <E, R> Collection<E> tree(Collection<E> collection, Function<E, R> getId, Function<E, R> getParentId, BiConsumer<E, Collection<E>> setNode) {
        Collection<E> root = new LinkedList<>();
        for (E node : collection) {
            R parentId = getParentId.apply(node);
            R id = getId.apply(node);
            Collection<E> elements = new LinkedList<>();
            boolean isParent = true;
            for (E element : collection) {
                if (id.equals(getParentId.apply(element))) {
                    elements.add(element);
                }
                if (isParent && getId.apply(element).equals(parentId)) {
                    isParent = false;
                }
            }
            if (isParent) {
                root.add(node);
            }
            setNode.accept(node, elements);
        }
        return root;
    }
}

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

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

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