首页 文章

Java树数据结构? [关闭]

提问于
浏览
436

是否有一个良好的可用(标准Java)数据结构来表示Java中的树?

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

  • 任何节点上的树都可以有任意数量的子节点

  • 每个节点(在根之后)只是一个字符串(其子节点也是字符串)

  • 我需要能够在给定表示给定节点的输入字符串的情况下获取所有子节点(某种列表或字符串数组)

是否有可用的结构或我是否需要创建自己的结构(如果是这样的实现建议会很好) .

24 回答

  • 4

    wrote一个处理通用树的小库 . 它比摇摆的东西轻得多 . 我也有一个maven project .

  • 6

    这里:

    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 或任何其他对象的基本树结构 . 实现简单的树来完成你需要的工作是相当容易的 .

    您需要添加的是添加,删除,遍历和构造函数的方法 . NodeTree 的基本构建块 .

  • 4

    我编写了一个与Java8很好地兼容的树库,它没有其他依赖项 . 它还提供了对函数式编程的一些想法的宽松解释,并允许您映射/过滤/修剪/搜索整个树或子树 .

    https://github.com/RutledgePaulV/prune

    实现对索引没有做任何特殊处理,并且我没有偏离递归,因此对于大型树,性能可能会降低并且您可能会破坏堆栈 . 但是,如果您只需要一个中小深度的直接树,我认为它的效果非常好 . 它提供了一个理智的(基于值)的相等定义,它还有一个toString实现,可以让你可视化树!

  • 1

    Java中没有适合您要求的特定数据结构 . 您的要求非常具体,因此您需要设计自己的数据结构 . 根据您的要求,任何人都可以说您需要某种具有某些特定功能的n-ary树 . 您可以通过以下方式设计数据结构:

    • 树的节点结构就像节点中的内容和子节点列表一样:class Node {String value;列出孩子;}

    • 您需要检索给定字符串的子项,因此您可以有2个方法1:节点searchNode(String str),将返回与给定输入具有相同值的节点(使用BFS进行搜索)2:List getChildren( String str):此方法将在内部调用searchNode以获取具有相同字符串的节点,然后它将创建子节点的所有字符串值的列表并返回 .

    • 您还需要在树中插入一个字符串 . 您将不得不编写一个方法,如void insert(String parent,String value):这将再次搜索具有等于parent的值的节点,然后您可以创建具有给定值的节点并将子节点添加到找到的父节点 .

    我建议,你在一个类中编写节点的结构,如Class Node {String value;在另一个NodeUtils类中列出children;}以及search,insert和getChildren等所有其他方法,这样您也可以传递树的根以对特定树执行操作,如:class NodeUtils {public static Node search(Node root,String value) {//执行BFS并返回Node}

  • 102

    我写了一个基于“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(", "));
    }
    

    你会得到一棵漂亮的树 . 应该很容易适应您的需求 .

  • 2

    您可以使用作为Jakarta Project一部分的Apache JMeter中包含的HashTree类 .

    HashTree类包含在org.apache.jorphan.collections包中 . 虽然此软件包未在JMeter项目之外发布,但您可以轻松获取:

    1)下载JMeter sources .

    2)创建一个新包 .

    3)复制它/ src / jorphan / org / apache / jorphan / collections / . 除Data.java之外的所有文件

    4)复制/src/jorphan/org/apache/jorphan/util/JOrphanUtils.java

    5)HashTree已准备好使用 .

  • 1

    您可以在java.util . *中使用TreeSet类 . 它像二进制搜索树一样工作,所以它已经排序了 . TreeSet类实现Iterable,Collection和Set接口 . 您可以使用迭代器遍历树,就像集合一样 .

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

    你可以查看Java Doc和一些other .

  • 1

    您可以使用Java的任何XML API作为Document和Node..as XML是带有字符串的树结构

  • 6

    您应该首先定义树是什么(对于域),最好通过首先定义 interface 来完成 . 并非所有树结构都是可修改的,能够添加和删除节点应该是一个可选功能,因此我们为此创建了一个额外的接口 .

    There's no need to create node objects which hold the values ,实际上我认为这是大多数树实现中的主要设计缺陷和开销 . 如果你看看Swing, TreeModel 没有节点类(只有 DefaultTreeModel 使用 TreeNode ),因为它们是不是真的需要 .

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

    给定这些接口,使用树的代码不必太在意树的实现方式 . 这允许您使用通用实现以及专用实现,您可以通过将函数委托给另一个API来实现树 .
    Example: File tree structure.

    public class MappedTreeStructure<N extends Serializable> implements MutableTree<N> {
    
        public static void main(String[] args) {
    
            MutableTree<String> tree = new MappedTreeStructure<String>();
            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<N, N>();
        private final LinkedHashSet<N> nodeList = new LinkedHashSet<N>();
    
        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<N>();
            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);
            }
        }
    }
    
  • 5

    那这个呢?

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

    另一种树形结构:

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

    BONUS
    查看完全成熟的树:

    • 迭代器

    • 搜索

    • Java / C#

    https://github.com/gt4dev/yet-another-tree-structure

  • 1

    请检查以下代码,我使用了Tree数据结构,而不使用Collection类 . 代码可能有错误/改进但请使用它仅供参考

    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();
    
        }
    
    }
    
  • 94

    在过去,我刚刚使用了嵌套 Map . 这就是我今天使用的,它很简单,但它符合我的需要 . 也许这会有助于另一个人 .

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

    Tree的自定义树实现,不使用Collection框架 . 它包含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);             
        }
    
    }
    
  • 1
    // 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);
      }
    }
    
  • 9

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

    看看javax.swing.treeTreeModelTreeNode . 它们被设计为与 JTreePanel 一起使用,但它们实际上是一个非常好的树实现,并且没有什么能阻止你在摆动界面中使用它 .

    请注意,从Java 9开始,您可能不希望使用这些类,因为它们不会出现在'Compact profiles'中 .

  • 9

    Java中有一些树数据结构,例如JDK Swing中的DefaultMutableTreeNode,Stanford解析器包中的Tree以及其他玩具代码 . 但这些都不足以满足一般目的 .

    Java-tree项目尝试在Java中提供另一个通用树数据结构 . 这和其他人的区别是

    • 完全免费 . 你可以在任何地方使用它(除了你的作业:P)

    • 虽小但很通用 . 我将数据结构的所有内容都放在一个类文件中,因此复制/粘贴很容易 .

    • 不仅仅是玩具 . 我知道几十个只能处理二叉树或有限操作的Java树代码 . 这个TreeNode远不止于此 . 它提供了访问节点的不同方式,例如预订,后序,广度,叶子,根路径等 . 此外,还提供了迭代器以满足要求 .

    • 将添加更多工具 . 我愿意添加更多操作来使这个项目更加全面,特别是如果你通过github发送请求 .

  • 40

    没有回答提到过度简化但工作的代码,所以这里是:

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

    例如 :

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

    显然,您可以添加实用程序方法来添加/删除子项 .

  • 12

    如果您正在进行白板编码,采访,甚至只是计划使用树,那么这些问题的详细程度就会有所不同 .

    应该进一步说,树不在那里的原因,例如, Pair (可以说是相同的),是因为你应该使用它将数据封装在类中, and 最简单的实现看起来像:

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

    或者如果你想要一个特里:

    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
    []
    
  • 1
    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;
      ...
    }
    
  • 272

    与Gareth的回答一样,请查看DefaultMutableTreeNode . 它在javax.swing包中是's not generic, but otherwise seems to fit the bill. Even though it',它不依赖于任何AWT或Swing类 . 实际上,源代码实际上有评论 // ISSUE: this class depends on nothing in AWT -- move to java.util?

  • 2

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

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

    instanceof 可用于确定元素是子树还是终端节点 .

相关问题