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;
}
}
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);
}
}
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 ...
}
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);
}
}
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()));
}
}
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;
}
24 回答
我wrote一个处理通用树的小库 . 它比摇摆的东西轻得多 . 我也有一个maven project .
这里:
这是一个可用于
String
或任何其他对象的基本树结构 . 实现简单的树来完成你需要的工作是相当容易的 .您需要添加的是添加,删除,遍历和构造函数的方法 .
Node
是Tree
的基本构建块 .我编写了一个与Java8很好地兼容的树库,它没有其他依赖项 . 它还提供了对函数式编程的一些想法的宽松解释,并允许您映射/过滤/修剪/搜索整个树或子树 .
https://github.com/RutledgePaulV/prune
实现对索引没有做任何特殊处理,并且我没有偏离递归,因此对于大型树,性能可能会降低并且您可能会破坏堆栈 . 但是,如果您只需要一个中小深度的直接树,我认为它的效果非常好 . 它提供了一个理智的(基于值)的相等定义,它还有一个toString实现,可以让你可视化树!
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}
我写了一个基于“HashMap”的小“TreeMap”类,它支持添加路径:
它可用于存储“T”类型的事物树(通用),但不支持(还)支持在其节点中存储额外数据 . 如果您有这样的文件:
然后你可以通过执行以下命令使它成为树:
你会得到一棵漂亮的树 . 应该很容易适应您的需求 .
您可以使用作为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已准备好使用 .
您可以在java.util . *中使用TreeSet类 . 它像二进制搜索树一样工作,所以它已经排序了 . TreeSet类实现Iterable,Collection和Set接口 . 您可以使用迭代器遍历树,就像集合一样 .
你可以查看Java Doc和一些other .
您可以使用Java的任何XML API作为Document和Node..as XML是带有字符串的树结构
您应该首先定义树是什么(对于域),最好通过首先定义 interface 来完成 . 并非所有树结构都是可修改的,能够添加和删除节点应该是一个可选功能,因此我们为此创建了一个额外的接口 .
There's no need to create node objects which hold the values ,实际上我认为这是大多数树实现中的主要设计缺陷和开销 . 如果你看看Swing,
TreeModel
没有节点类(只有DefaultTreeModel
使用TreeNode
),因为它们是不是真的需要 .给定这些接口,使用树的代码不必太在意树的实现方式 . 这允许您使用通用实现以及专用实现,您可以通过将函数委托给另一个API来实现树 .
Example: File tree structure.
那这个呢?
另一种树形结构:
样品用法:
BONUS
查看完全成熟的树:
迭代器
搜索
Java / C#
https://github.com/gt4dev/yet-another-tree-structure
请检查以下代码,我使用了Tree数据结构,而不使用Collection类 . 代码可能有错误/改进但请使用它仅供参考
在过去,我刚刚使用了嵌套 Map . 这就是我今天使用的,它很简单,但它符合我的需要 . 也许这会有助于另一个人 .
Tree的自定义树实现,不使用Collection框架 . 它包含Tree实现中所需的不同基本操作 .
实际上在JDK中实现了一个非常好的树结构 .
看看javax.swing.tree,TreeModel和TreeNode . 它们被设计为与
JTreePanel
一起使用,但它们实际上是一个非常好的树实现,并且没有什么能阻止你在摆动界面中使用它 .请注意,从Java 9开始,您可能不希望使用这些类,因为它们不会出现在'Compact profiles'中 .
Java中有一些树数据结构,例如JDK Swing中的DefaultMutableTreeNode,Stanford解析器包中的Tree以及其他玩具代码 . 但这些都不足以满足一般目的 .
Java-tree项目尝试在Java中提供另一个通用树数据结构 . 这和其他人的区别是
完全免费 . 你可以在任何地方使用它(除了你的作业:P)
虽小但很通用 . 我将数据结构的所有内容都放在一个类文件中,因此复制/粘贴很容易 .
不仅仅是玩具 . 我知道几十个只能处理二叉树或有限操作的Java树代码 . 这个TreeNode远不止于此 . 它提供了访问节点的不同方式,例如预订,后序,广度,叶子,根路径等 . 此外,还提供了迭代器以满足要求 .
将添加更多工具 . 我愿意添加更多操作来使这个项目更加全面,特别是如果你通过github发送请求 .
没有回答提到过度简化但工作的代码,所以这里是:
例如 :
显然,您可以添加实用程序方法来添加/删除子项 .
如果您正在进行白板编码,采访,甚至只是计划使用树,那么这些问题的详细程度就会有所不同 .
应该进一步说,树不在那里的原因,例如,
Pair
(可以说是相同的),是因为你应该使用它将数据封装在类中, and 最简单的实现看起来像:对于任意宽度的树来说,这确实是它 .
如果你想要一个二叉树,它通常更容易用于命名字段:
或者如果你想要一个特里:
现在你说你想要
这听起来像是你的功课 .
但是,因为我有理由相信任何截止日期已经过去了......
这可以让你使用:
尽可能简单易用 . 要使用它,请扩展它:
与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?
由于该问题要求可用的数据结构,因此可以从列表或数组构造树:
instanceof
可用于确定元素是子树还是终端节点 .