Java树的数据结构?

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

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

  • 任何节点上的树可以有任意数量的子节点
  • 每个节点(在根之后)只是一个string(其子节点也是string)
  • 我需要能够得到所有的孩子(某种列表或string数​​组)给定一个inputstring表示给定的节点

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

这里:

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的基本构build块。

又一个树形结构:

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

奖金
看到完全成熟的树:

  • 迭代器
  • search
  • 的Java / C#

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

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

看看javax.swing.tree , TreeModel和TreeNode 。 它们被devise成与JTreePanel一起使用,但实际上它们是一个非常好的树实现,没有任何东西阻止你使用它,而不是使用swing接口。

请注意,从Java 9开始,您可能不希望使用这些类,因为它们不会出现在“紧凑configuration文件”中 。

那这个呢? (顺便说一句,不pipe我好像尝试了什么,我都不能粘贴网站代码格式化程序会正确处理的代码,对不起。

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

我写了一个处理通用树的小型库。 它比摇摆的东西轻得多。 我也有一个maven项目 。

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

显然你可以添加实用的方法来添加/删除子项。

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

没有必要创build包含这些值的节点对象 ,事实上,我认为这是大多数树实现中的主要devise缺陷和开销。 如果你看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); } 

鉴于这些接口,使用树的代码不必太在意树的实现方式。 这允许您使用generics实现以及专用实现,通过将函数委托给另一个API来实现树。
示例:文件树结构。

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

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

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

和Gareth的答案一样,检查DefaultMutableTreeNode 。 这不是通用的,但似乎符合法案。 即使它在javax.swing包中,也不依赖于任何AWT或Swing类。 实际上,源代码实际上有注释// ISSUE: this class depends on nothing in AWT -- move to java.util?

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

Java中有一些树型数据结构,如JDK Swing中的DefaultMutableTreeNode,Stanfordparsing器包中的Tree以及其他玩具代码。 但是这些都不足以满足一般目的。

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

  • 完全免费。 你可以在任何地方使用(除了作业:P)
  • 小但一般不够。 我将数据结构的所有内容放在一个类文件中,因此复制/粘贴会很容易。
  • 不只是一个玩具。 我知道许多只能处理二叉树或有限操作的Java树代码。 这个TreeNode远不止于此。 它提供了不同的访问节点的方式,比如前序,后序,广度,叶子,根path等。此外,还提供了迭代器以满足要求。
  • 更多的utils将被添加。 我愿意添加更多的操作来使这个项目全面,特别是如果你通过github发送请求。

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

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

instanceof可以用来确定一个元素是一个子树还是一个terminal节点。

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

如果你正在做白板编码,面试,甚至只是计划使用树,这些冗长的一点点。

应该进一步说,一个树不在那里的原因就像一个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; } 

现在你说你想要

为了能够得到所有的孩子(某种列表或string数​​组)给定一个inputstring表示给定的节点

这听起来像你的功课。
但是因为我相当确定任何截止date已经过去了…

 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 [] 

例如 :

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

树的自定义Tree实现,而不使用Collection框架。 它包含了树实现中所需的不同基本操作。

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

您可以使用雅加达项目中包含的Apache JMeter中的HashTree类。

HashTree类包含在org.apache.jorphan.collections包中。 虽然这个包不是在JMeter项目之外发布的,但是你可以很容易地获得它:

1)下载JMeter源代码 。

2)创build一个新的包。

3)拷贝它/ src / jorphan / org / apache / jorphan / collections /。 除Data.java外的所有文件

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

5)HashTree已经可以使用了。

请检查下面的代码,我已经使用了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(); } } 

Java中没有适合您需求的特定数据结构。 您的要求是非常具体的,因此您需要devise自己的数据结构。 看着你的需求,任何人都可以说你需要某种具有一些特定function的n-ary树。 您可以按照以下方式devise您的数据结构:

  1. 树节点的结构就像节点和孩子列表中的内容一样:class Node {String value; 列出孩子;}
  2. 你需要检索给定string的子元素,所以你可以有2个方法1:Node searchNode(String str),将返回与给定input相同值的节点(使用BFS进行search)2:List getChildren(String str):这个方法将在内部调用searchNode来获取具有相同string的节点,然后它将创build所有子string值列表并返回。
  3. 您还将被要求在树中插入一个string。 你将不得不写一个方法说空插入(string父,string值):这将再次search的价值等于父母的节点,然后你可以创build一个具有给定值的节点,并添加到孩子列表find父。

我build议,你写一个类的节点结构像类节点{string值; 列表中的孩子;}和所有其他方法,如search,插入和getChildren在另一个NodeUtils类,以便您还可以传递树的根在特定的树上执行操作,如:class NodeUtils {public static Node search(Node root,String value) {//执行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); } } 

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

https://github.com/RutledgePaulV/prune

这个实现并没有对索引做任何特殊的处理,而且我也没有偏离recursion,所以有可能大树性能会下降,你可能会把堆栈炸掉。 但是,如果你所需要的只是一个中等深度的简单树,我认为它工作得很好。 它提供了一个理智的(基于价值的)平等的定义,它也有一个toString的实现,让你可视化的树!

您可以使用java.util。*中的TreeSet类。 它像Binarysearch树一样工作,所以它已经被sorting。 TreeSet类实现Iterable,Collection和Set接口。 你可以像迭代一样遍历遍历树。

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

你可以检查, Java Doc和其他一些。