如何在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的基本构建块。

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

看看javax.swing.tree， TreeModel和TreeNode。它们被设计为与JTreePanel一起使用，但实际上，它们是一个非常好的树实现，没有什么可以阻止你在没有swing接口的情况下使用它。

注意，从Java 9开始，你可能不希望使用这些类，因为它们不会出现在“紧凑的配置文件”中。

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

显然，您可以添加实用工具方法来添加/删除子元素。

和加雷斯的答案一样，看看DefaultMutableTreeNode。它不是一般的，但在其他方面似乎符合要求。即使它在javax中。swing包，它不依赖于任何AWT或swing类。事实上，源代码实际上有注释// ISSUE: this class depends on nothing in AWT -- move to java.util?

这个呢?

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项目。

您可以使用Apache JMeter中包含的HashTree类，它是Jakarta项目的一部分。

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

1)下载JMeter来源。

2)创建一个新包。

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

4)复制/src/jorphan/ org/apache/jorphan/uti/jorphanutils .java

5) HashTree可以使用了。

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

没有回答提到过度简化但有效的代码，所以下面是:

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

由于问题要求可用的数据结构，树可以由列表或数组构造:

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

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

还有另一种树结构:

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来实现树

例如:# EYZ0

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


}


}

Java中有一些树数据结构，比如JDK Swing中的DefaultMutableTreeNode, Stanford解析器包中的tree，以及其他一些玩具代码。但这些都不够，也不够小，不能用于一般用途。

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

• 完全免费的。你可以在任何地方使用它(除了你的家庭作业:P)
• 虽小，但足够普遍。我把所有的数据结构都放在一个类文件中，这样就很容易复制/粘贴。
• 不仅仅是玩具。我知道有许多Java树代码只能处理二叉树或有限的操作。这个TreeNode远远不止于此。它提供了不同的访问节点的方式，如预订，postorder, broadthfirst，叶子，路径到根等。此外，还为充分性提供了迭代器。
• 更多的utils将被添加。我愿意增加更多的操作，使这个项目全面，特别是如果你通过github发送请求。

例如:

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

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


}

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

1. 树节点的结构将类似于节点和子列表中的内容，如: 类节点{字符串值;李列表孩子;}< / >
2. 你需要检索给定字符串的子字符串，所以你可以有2个方法1:Node searchNode(string str)，将返回与给定输入具有相同值的节点(使用BFS进行搜索)2:List getChildren(string str):这个方法将在内部调用searchNode来获得具有相同字符串的节点，然后它将创建所有子字符串值的列表并返回。
3. 您还需要在树中插入一个字符串。你必须写一个方法说void insert(String parent, String value):这将再次搜索值等于parent的节点，然后你可以创建一个给定值的node，并添加到找到的父节点的子节点列表中。

在过去，我只是为此使用了一个嵌套映射。这是我今天用的，它很简单，但它符合我的需要。也许这能帮到另一个人。

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

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

我编写了一个树库，它可以很好地使用Java8，并且没有其他依赖项。它还提供了对函数式编程的一些思想的松散解释，并允许您映射/过滤/修剪/搜索整个树或子树。

https://github.com/RutledgePaulV/prune

这个实现在索引方面没有做任何特别的事情，而且我也没有偏离递归，所以使用大型树的性能可能会下降，可能会破坏堆栈。但如果你所需要的只是一个简单的小到中等深度的树，我认为它已经足够好了。它提供了一个健全的(基于值的)相等定义，它还有一个toString实现，可以让您可视化树!

您可以在java.util.*中使用TreeSet类。它像二叉搜索树一样工作，所以它已经排好序了。TreeSet类实现了Iterable、Collection和Set接口。您可以像使用set一样使用迭代器遍历树。

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

你可以检查Java文档和一些其他。

如果您正在编写白板代码、进行面试，或者只是计划使用树，那么这些内容就有点冗长了。

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

现在你说你想要

给定一个表示给定节点的输入字符串，能够获得所有的子节点(某种类型的列表或字符串数组)

听起来像你的家庭作业 但是因为我很确定截止日期已经过去了

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

我写了一个基于“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.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;
}
}
}

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

我用的是“mapappedtreestructure”。实现。这个实现很好地重新组织了树，并且不包含节点“复制”。

但是没有提供分级方法。

看看那些有问题的输出!

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