在这里:

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或任何其他对象。实现简单的树来满足您的需要是相当容易的。

您需要添加的只是用于添加、删除、遍历和构造函数的方法。节点是树的基本构建块。

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

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

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

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

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

与Gareth的答案相同，请检查DefaultMutableTreeNode。它不是一般的，但在其他方面似乎符合要求。即使它在javax中。swing包，它不依赖于任何AWT或swing类。事实上，源代码实际上有注释// ISSUE:这个类不依赖于AWT中的任何东西——移到java.util?

这个呢?

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

我写了一个处理通用树的小库。它比秋千轻多了。我也有一个专门的项目。

您可以使用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是一个带有字符串的树结构

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

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

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

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

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

还有另一种树结构:

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

首先应该定义什么是树(对于域)，最好先定义接口。并不是所有的树结构都是可修改的，能够添加和删除节点应该是一个可选的功能，所以我们为此做了一个额外的接口。

没有必要创建保存值的节点对象，事实上，我认为这是大多数树实现中的主要设计缺陷和开销。如果查看Swing, TreeModel没有节点类(只有DefaultTreeModel使用TreeNode)，因为实际上并不需要它们。

public interface Tree <N extends Serializable> extends Serializable {
    List<N> getRoots ();
    N getParent (N node);
    List<N> getChildren (N node);
}

可变树结构(允许添加和删除节点):

public interface MutableTree <N extends Serializable> extends Tree<N> {
    boolean add (N parent, N node);
    boolean remove (N node, boolean cascade);
}

有了这些接口，使用树的代码就不必太关心树是如何实现的。这允许您使用通用实现和专用实现，在专用实现中，通过将函数委托给另一个API来实现树。

例如:文件树结构

public class FileTree implements Tree<File> {

    @Override
    public List<File> getRoots() {
        return Arrays.stream(File.listRoots()).collect(Collectors.toList());
    }

    @Override
    public File getParent(File node) {
        return node.getParentFile();
    }

    @Override
    public List<File> getChildren(File node) {
        if (node.isDirectory()) {
            File[] children = node.listFiles();
            if (children != null) {
                return Arrays.stream(children).collect(Collectors.toList());
            }
        }
        return Collections.emptyList();
    }
}

示例:通用树结构(基于父/子关系):

public class MappedTreeStructure<N extends Serializable> implements MutableTree<N> {

    public static void main(String[] args) {

        MutableTree<String> tree = new MappedTreeStructure<>();
        tree.add("A", "B");
        tree.add("A", "C");
        tree.add("C", "D");
        tree.add("E", "A");
        System.out.println(tree);
    }

    private final Map<N, N> nodeParent = new HashMap<>();
    private final LinkedHashSet<N> nodeList = new LinkedHashSet<>();

    private void checkNotNull(N node, String parameterName) {
        if (node == null)
            throw new IllegalArgumentException(parameterName + " must not be null");
    }

    @Override
    public boolean add(N parent, N node) {
        checkNotNull(parent, "parent");
        checkNotNull(node, "node");

        // check for cycles
        N current = parent;
        do {
            if (node.equals(current)) {
                throw new IllegalArgumentException(" node must not be the same or an ancestor of the parent");
            }
        } while ((current = getParent(current)) != null);

        boolean added = nodeList.add(node);
        nodeList.add(parent);
        nodeParent.put(node, parent);
        return added;
    }

    @Override
    public boolean remove(N node, boolean cascade) {
        checkNotNull(node, "node");

        if (!nodeList.contains(node)) {
            return false;
        }
        if (cascade) {
            for (N child : getChildren(node)) {
                remove(child, true);
            }
        } else {
            for (N child : getChildren(node)) {
                nodeParent.remove(child);
            }
        }
        nodeList.remove(node);
        return true;
    }

    @Override
    public List<N> getRoots() {
        return getChildren(null);
    }

    @Override
    public N getParent(N node) {
        checkNotNull(node, "node");
        return nodeParent.get(node);
    }

    @Override
    public List<N> getChildren(N node) {
        List<N> children = new LinkedList<>();
        for (N n : nodeList) {
            N parent = nodeParent.get(n);
            if (node == null && parent == null) {
                children.add(n);
            } else if (node != null && parent != null && parent.equals(node)) {
                children.add(n);
            }
        }
        return children;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        dumpNodeStructure(builder, null, "- ");
        return builder.toString();
    }

    private void dumpNodeStructure(StringBuilder builder, N node, String prefix) {
        if (node != null) {
            builder.append(prefix);
            builder.append(node.toString());
            builder.append('\n');
            prefix = "  " + prefix;
        }
        for (N child : getChildren(node)) {
            dumpNodeStructure(builder, child, prefix);
        }
    }
}

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

    }

}

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.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;
    }
}

不使用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);             
    }

}

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

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

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

    // TestTree.java
// A simple test to see how we can build a tree and populate it
//
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.tree.*;

public class TestTree extends JFrame {

  JTree tree;
  DefaultTreeModel treeModel;

  public TestTree( ) {
    super("Tree Test Example");
    setSize(400, 300);
    setDefaultCloseOperation(EXIT_ON_CLOSE);
  }

  public void init( ) {
    // Build up a bunch of TreeNodes. We use DefaultMutableTreeNode because the
    // DefaultTreeModel can use it to build a complete tree.
    DefaultMutableTreeNode root = new DefaultMutableTreeNode("Root");
    DefaultMutableTreeNode subroot = new DefaultMutableTreeNode("SubRoot");
    DefaultMutableTreeNode leaf1 = new DefaultMutableTreeNode("Leaf 1");
    DefaultMutableTreeNode leaf2 = new DefaultMutableTreeNode("Leaf 2");

    // Build our tree model starting at the root node, and then make a JTree out
    // of it.
    treeModel = new DefaultTreeModel(root);
    tree = new JTree(treeModel);

    // Build the tree up from the nodes we created.
    treeModel.insertNodeInto(subroot, root, 0);
    // Or, more succinctly:
    subroot.add(leaf1);
    root.add(leaf2);

    // Display it.
    getContentPane( ).add(tree, BorderLayout.CENTER);
  }

  public static void main(String args[]) {
    TestTree tt = new TestTree( );
    tt.init( );
    tt.setVisible(true);
  }
}

public abstract class Node {
  List<Node> children;

  public List<Node> getChidren() {
    if (children == null) {
      children = new ArrayList<>();
    }
    return chidren;
  }
}

它非常简单，很容易使用。要使用它，请扩展它:

public class MenuItem extends Node {
  String label;
  String href;
  ...
}

我编写了一个树库，它可以很好地使用Java8，并且没有其他依赖项。它还提供了对函数式编程的一些思想的松散解释，并允许您映射/过滤/修剪/搜索整个树或子树。

https://github.com/RutledgePaulV/prune

这个实现在索引方面没有做任何特别的事情，而且我也没有偏离递归，所以使用大型树的性能可能会下降，可能会破坏堆栈。但如果你所需要的只是一个简单的小到中等深度的树，我认为它已经足够好了。它提供了一个健全的(基于值的)相等定义，它还有一个toString实现，可以让您可视化树!

您可以在java.util.*中使用TreeSet类。它像二叉搜索树一样工作，所以它已经排好序了。TreeSet类实现了Iterable、Collection和Set接口。您可以像使用set一样使用迭代器遍历树。

TreeSet<String> treeSet = new TreeSet<String>();
Iterator<String> it  = treeSet.Iterator();
while(it.hasNext()){
...
}

你可以检查，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
[]

我写了一个基于“HashMap”的小“TreeMap”类，它支持添加路径:

import java.util.HashMap;
import java.util.LinkedList;

public class TreeMap<T> extends LinkedHashMap<T, TreeMap<T>> {

    public void put(T[] path) {
        LinkedList<T> list = new LinkedList<>();
        for (T key : path) {
            list.add(key);
        }
        return put(list);
    }

    public void put(LinkedList<T> path) {
        if (path.isEmpty()) {
            return;
        }
        T key = path.removeFirst();
        TreeMap<T> val = get(key);
        if (val == null) {
            val = new TreeMap<>();
            put(key, val);
        }
        val.put(path);
    }

}

它可以用来存储一个“T”(泛型)类型的树，但(目前)不支持在节点中存储额外的数据。如果你有一个这样的文件:

root, child 1
root, child 1, child 1a
root, child 1, child 1b
root, child 2
root, child 3, child 3a

然后你可以通过执行:

TreeMap<String> root = new TreeMap<>();
Scanner scanner = new Scanner(new File("input.txt"));
while (scanner.hasNextLine()) {
  root.put(scanner.nextLine().split(", "));
}

你会得到一棵漂亮的树。它应该很容易适应你的需要。

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

简单的例子:

public class ArbrePlaner {

public static void main(String[] args) {
    ArbrePlaner ll = new ArbrePlaner();
    
    ll.add(1,"A");
    ll.add(2,"B");
    ll.add(1,"C");
    ll.add(3,"D");
    ll.add(1,"Z");
    
    for(int i = 0; i < ll.size; i++){
    //  System.out.println(ll.isIdExist(i));
        System.out.println("-----------------");
        System.out.println(ll.getIdAt(i)+" :");
        linkedList lst = ll.getListDataById(ll.getIdAt(i));
        for(int j = 0; j < lst.size; j++){
            System.out.println(lst.getElementAt(j));
        }
    }
    
    
    
    
}

private int size;
private Noeud root;

public Noeud add(long Id, Object data){
    if(isIdExist(Id)){
        Noeud nd = getNoeudId(Id);
        nd.add(data);
        return nd;
    }else{
        Noeud nd = new Noeud(Id, data, this.root);
        this.root = nd;
        this.size++;
        return nd;
    }
}
 
 public Object getDataById(long Id, int x){
        Noeud thisNode = this.root;
        while(thisNode!=null){
            if(thisNode.getId() == Id){
                return thisNode.getLl().getElementAt(x);
            }
            thisNode = thisNode.getNextNoeud();
        }
        return null;
    }
 
 public long getIdAt(int x){
        if(size >= x){
            Noeud nd = this.root;
            for(int i = 0; i<x; i++)try {nd = nd.getNextNoeud();} catch (Exception e) {return -1;}
            return nd.getId();
        }
            return -1;
    }
 
 public linkedList getListDataById(long Id){
        Noeud thisNode = this.root;
        while(thisNode!=null){
            if(thisNode.getId() == Id){
                return thisNode.getLl();
            }
            thisNode = thisNode.getNextNoeud();
        }
        return null;
    }
 
public boolean deleteById(long id){
    Noeud thisNode = this.root;
    Noeud prevNode = null;
    
    while(thisNode != null){
        if(thisNode.getId() == id){
            prevNode.setNextNoeud(thisNode.getNextNoeud());
            this.setSize(this.getSize()-1);
            return true;
        }
        prevNode = thisNode;
        thisNode = thisNode.getNextNoeud();
    }
    return false;
}

 public boolean isIdExist(long Id){
        Noeud thisNode = this.root;
        while(thisNode!=null){
            if(thisNode.getId()== Id){
                return true;
            }
            thisNode = thisNode.getNextNoeud();
        }
        return false;
    }

 public boolean isDataExist(long Id, Object data){
     if(isIdExist(Id)){
         Noeud thisNode = this.root;
            while(thisNode!=null){
                if(thisNode.getId() == Id){
                    linkedList ll = thisNode.getLl();
                    long x = ll.hashCode();
                    long y = data.hashCode();
                    if(x==y) return true;
                }
                thisNode = thisNode.getNextNoeud();
            }
     }
     return false;
 }
 
 public Noeud getNoeudId(long Id){
        Noeud thisNode = this.root;
        while(thisNode!=null){
            if(thisNode.getId() == Id){
                return thisNode;
            }
            thisNode = thisNode.getNextNoeud();
        }
        return null;
    }

public ArbrePlaner() {
    this.root = root;
}

public ArbrePlaner(Noeud root) {
    this.root = root;
}

public ArbrePlaner(int size, Noeud root) {
    this.size = size;
    this.root = root;
}

public int getSize() {
    return size;
}

public void setSize(int size) {
    this.size = size;
}

public Noeud getRoot() {
    return root;
}

public void setRoot(Noeud root) {
    this.root = root;
}

private class Noeud{
    private long id;
    private Noeud nextNoeud;
    private linkedList Ll;
    
    public void add(Object data){
        Ll.add(data);
    }
    
    public Noeud(long id, Object data ,Noeud nextNoeud){
        this.id = id;
        this.nextNoeud = nextNoeud;
        Ll = new linkedList();
        Ll.add(data);
    }
    
    public long getId() {
        return id;
    }
    
    public Noeud(Object data){
        Ll.add(data);
    }
            
    public void setId(long id) {
        this.id = id;
    }
    public Noeud getNextNoeud() {
        return nextNoeud;
    }
    public void setNextNoeud(Noeud nextNoeud) {
        this.nextNoeud = nextNoeud;
    }
    public linkedList getLl() {
        return Ll;
    }
    public void setLl(linkedList ll) {
        Ll = ll;
    }
}
}

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

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