是否有任何标准的 Java 库类来表示 Java 中的树?
具体来说,我需要表示以下内容:
任何节点的子树都可以有任意数量的孩子
每个节点(根节点之后)及其子节点都将具有字符串值
我需要获取给定节点的所有子节点(某种列表或字符串数组)及其字符串值(即一种将节点作为输入并将子节点的所有字符串值作为输出返回的方法)
是否有任何可用的结构,或者我需要创建自己的结构(如果有的话,实施建议会很棒)。
这里:
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
或任何其他对象的基本树结构。实现简单的树来做你需要的事情是相当容易的。
您需要添加的只是添加、删除、遍历和构造函数的方法。 Node
是 Tree
的基本构建块。
另一个树结构:
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
next()
之前调用 hasNext()
以获得有效结果。这不是 Iterator
规范的一部分。
实际上在 JDK 中实现了一个非常好的树结构。
查看 javax.swing.tree、TreeModel 和 TreeNode。它们被设计为与 JTreePanel
一起使用,但实际上它们是一个非常好的树实现,没有什么可以阻止您在没有 swing 接口的情况下使用它。
请注意,从 Java 9 开始,您可能不希望使用这些类,因为它们不会出现在 'Compact profiles' 中。
那这个呢?
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;
}
}
setAsParent
或 getHead
这样的方法是做什么的,此时我真的可以在树数据结构方面获得一些帮助。甚至文件的原始来源也没有评论。
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;
}
}
显然,您可以添加实用程序方法来添加/删除子项。
int size;
可以保留在 Tree 中,并且上面的一个必须编写类似 tree = tree.sortedAdd(data)
的东西来进行树操作。
您应该首先定义什么是树(对于域),最好先定义接口。并非所有的树结构都是可修改的,能够添加和删除节点应该是一个可选功能,因此我们为此制作了一个额外的接口。
没有必要创建保存值的节点对象,事实上,我认为这是大多数树实现中的主要设计缺陷和开销。如果您查看 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);
}
}
}
没有答案提到过度简化但有效的代码,所以这里是:
public class TreeNodeArray<T> {
public T value;
public final java.util.List<TreeNodeArray<T>> kids = new java.util.ArrayList<TreeNodeArray<T>>();
}
如果你正在做白板编码、面试,甚至只是打算使用一棵树,那么这些内容的冗长程度就有点多了。
应该进一步说,树不在其中的原因,例如 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;
}
或者,如果您想尝试一下:
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
[]
您可以将 Java 的任何 XML API 用作 Document 和 Node..因为 XML 是带有字符串的树结构
与 Gareth 的回答相同,请查看 DefaultMutableTreeNode。它不是通用的,但在其他方面似乎符合要求。即使它在 javax.swing 包中,它也不依赖于任何 AWT 或 Swing 类。其实源码里面居然有注释// ISSUE: this class depends on nothing in AWT -- move to java.util?
Java 中有一些树数据结构,例如 JDK Swing 中的 DefaultMutableTreeNode、Stanford 解析器包中的 Tree 和其他玩具代码。但是这些都不足以满足通用目的。
Java-tree 项目尝试在 Java 中提供另一种通用树数据结构。这个和其他的区别是
完全免费。你可以在任何地方使用它(除了你的作业:P)
小但足够一般。我将数据结构的所有内容放在一个类文件中,因此很容易复制/粘贴。
不仅仅是玩具。我知道有几十个 Java 树代码只能处理二叉树或有限的操作。这个 TreeNode 远不止这些。它提供了访问节点的不同方式,例如前序、后序、广度优先、叶子、到根的路径等。此外,为了充分性,还提供了迭代器。
将添加更多实用程序。我愿意添加更多的操作来使这个项目更加全面,特别是如果您通过 github 发送请求。
由于问题要求提供可用的数据结构,因此可以从列表或数组构造树:
Object[] tree = new Object[2];
tree[0] = "Hello";
{
Object[] subtree = new Object[2];
subtree[0] = "Goodbye";
subtree[1] = "";
tree[1] = subtree;
}
instanceof
可用于确定元素是子树还是终端节点。
Object
可以是叶对象(例如 String
)或分支(由数组表示)。它确实有效:该代码将编译,并创建一个 String
的小树。
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;
...
}
在过去,我只是为此使用了嵌套地图。这就是我今天使用的,它非常简单,但它符合我的需求。也许这会帮助另一个人。
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"));
}
}
我基于支持添加路径的“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(", "));
}
你会得到一棵漂亮的树。它应该很容易适应您的需求。
例如 :
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;
}
}
我编写了一个与 Java8 配合得很好并且没有其他依赖项的树形库。它还提供了对函数式编程的一些想法的松散解释,并允许您映射/过滤/修剪/搜索整个树或子树。
https://github.com/RutledgePaulV/prune
该实现对索引没有做任何特别的事情,我也没有偏离递归,所以大树的性能可能会降低,你可能会破坏堆栈。但是,如果您只需要一棵小到中等深度的简单树,我认为它就足够了。它提供了一个健全的(基于值的)相等定义,它还有一个 toString 实现,可以让您可视化树!
您可以使用 Apache JMeter 中包含的 HashTree 类,它是 Jakarta 项目的一部分。
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 中没有适合您要求的特定数据结构。您的要求非常具体,为此您需要设计自己的数据结构。查看您的要求,任何人都可以说您需要某种具有某些特定功能的 n 叉树。您可以通过以下方式设计数据结构:
树节点的结构类似于节点中的内容和子列表,例如:class Node { String value; List children;} 您需要检索给定字符串的子节点,因此您可以有 2 种方法 1:节点 searchNode(String str),将返回与给定输入具有相同值的节点(使用 BFS 进行搜索) 2: List getChildren(String str):该方法将在内部调用 searchNode 以获取具有相同字符串的节点,然后它将创建子节点的所有字符串值的列表并返回。您还需要在树中插入一个字符串。您将不得不编写一种方法,例如 void insert(String parent, String value):这将再次搜索值等于父节点的节点,然后您可以创建一个具有给定值的节点并将其添加到找到的父节点的子节点列表中.
我建议,你把节点的结构写在一个类中,比如 Class Node { String value; List children;} 和所有其他方法,如在另一个 NodeUtils 类中的搜索、插入和 getChildren,以便您还可以传递树的根以对特定树执行操作,例如: class NodeUtils{ public static Node search(Node root, String value) {// 执行 BFS 并返回 Node}
// 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);
}
}
请检查以下代码,其中我使用了 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();
}
}
import java.util.Collection;
import java.util.LinkedList;
import java.util.function.BiConsumer;
import java.util.function.Function;
/**
* @author changjin wei(魏昌进)
* @since 2021/7/15
*/
public class TreeUtils {
private TreeUtils() {
}
/**
* @param collection this is a collection of elements
* @param getId this is a getId Function
* @param getParentId this is a getParentId Function
* @param setNode this is a setNode BiConsumer
* @param <E> the type of elements in this collection
* @param <R> the type of the result of the function
*
* @return Collection
*/
public static <E, R> Collection<E> tree(Collection<E> collection, Function<E, R> getId, Function<E, R> getParentId, BiConsumer<E, Collection<E>> setNode) {
Collection<E> root = new LinkedList<>();
for (E node : collection) {
R parentId = getParentId.apply(node);
R id = getId.apply(node);
Collection<E> elements = new LinkedList<>();
boolean isParent = true;
for (E element : collection) {
if (id.equals(getParentId.apply(element))) {
elements.add(element);
}
if (isParent && getId.apply(element).equals(parentId)) {
isParent = false;
}
}
if (isParent) {
root.add(node);
}
setNode.accept(node, elements);
}
return root;
}
}
简单的例子:
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;
}
}
}
我对所有这些方法都有一个真正的问题。
我正在使用“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.tree;
import java.util.*;
import java.util.stream.Collectors;
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;
}
}
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, List<N>> tree() {
SortedMap<Long, List<N>> tree = new TreeMap<>();
tree(0L, tree, getRoots());
return tree;
}
protected void tree(Long i, SortedMap<Long, List<N>> tree, List<Node<N>> roots) {
for (Node<N> node : roots) {
List<N> tmp = tree.getOrDefault(i, new LinkedList<>());
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, List<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
不使用 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);
}
}
不定期副业成功案例分享
Tree
类不是必需的,因为每个Node
本身都可以被视为一棵树。