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

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

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

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


当前回答

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

其他回答

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

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

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

还有另一种树结构:

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();

    }

}