Java树数据结构？

Question

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

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

• 任何节点上的树都可以有任意数量的子节点
• 每个节点(在根之后)只是一个String(其子节点也是字符串)
• 给定一个表示给定节点的输入字符串,我需要能够获得所有子节点(某种列表或字符串数​​组)

是否有可用的结构或我是否需要创建自己的结构(如果是这样的实现建议会很好).

Answer 1

这里:

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.

Answer 2

另一种树形结构:

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

Answer 3

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

看看javax.swing.tree,TreeModel和TreeNode.它们被设计为与JTreePanel它们一起使用,但它们实际上是一个非常好的树实现,并且没有什么能阻止你在摆动界面中使用它.

请注意,从Java 9开始,您可能希望不使用这些类,因为它们不会出现在"压缩配置文件"中.

Answer 4

那这个呢？

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

Answer 5

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

Answer 6

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

显然,您可以添加实用程序方法来添加/删除子项.

Answer 7

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

没有必要创建保存值的节点对象,事实上我认为这是大多数树实现中的主要设计缺陷和开销.如果你看一下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);
        }
    }
}

Answer 8

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

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

Answer 9

您可以使用Java的任何XML API作为Document和Node..as XML是带有字符串的树结构

Answer 10

与Gareth的答案一样,查看DefaultMutableTreeNode.它不是通用的,但在其他方面似乎符合要求.即使它在javax.swing包中,它也不依赖于任何AWT或Swing类.实际上,源代码实际上有评论// ISSUE: this class depends on nothing in AWT -- move to java.util?

Answer 11

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

Java树项目试图在Java中提供另一种通用树数据结构.这与其他人的区别在于

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

Answer 12

如果您正在进行白板编码,采访,甚至只是计划使用树,那么这些问题的详细程度就会有所不同.

还应当说,树是不是在那里等,比方说,一个原因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
[]

Answer 13

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

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

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

Answer 14

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