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

}

这个呢?

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

在这里:

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

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

简单的例子:

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

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

没有必要创建保存值的节点对象，事实上，我认为这是大多数树实现中的主要设计缺陷和开销。如果查看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);
        }
    }
}

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