在Java中是否有标准的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
[]

其他回答

与Gareth的答案相同,请检查DefaultMutableTreeNode。它不是一般的,但在其他方面似乎符合要求。即使它在javax中。swing包,它不依赖于任何AWT或swing类。事实上,源代码实际上有注释// ISSUE:这个类不依赖于AWT中的任何东西——移到java.util?

还有另一种树结构:

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

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

Structure of the node of the tree would be like content in the node and list of children like: class Node { String value; List children;} You need to retrieve the children of a given string, so you can have 2 methods 1: Node searchNode(String str), will return the node that has the same value as given input (use BFS for searching) 2: List getChildren(String str): this method will internally call the searchNode to get the node having same string and then it will create the list of all string values of children and return. You will also be required to insert a string in tree. You will have to write one method say void insert(String parent, String value): this will again search the node having value equal to parent and then you can create a Node with given value and add to the list of children to the found parent.

我建议,你写一个类的节点结构类节点{字符串值;在另一个NodeUtils类中列出children;}和所有其他方法,如search, insert和getChildren,这样你也可以传递树的根来对特定的树执行操作,例如: 类NodeUtils{公共静态节点搜索(节点根,字符串值){//执行BFS并返回节点}

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

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

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

你可以检查,Java文档和其他的。