Javaツリーのデータ構造ですか?



11 Answers

さらに別のツリー構造:

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

Question

Javaでツリーを表現するのに利用できる(標準Java)データ構造がありますか?

具体的には、私は次のことを表す必要があります:

  • 任意のノードのツリーは任意の数の子を持つことができます
  • 各ノード(ルートの後ろ)はちょうどストリング(その子もストリングです)です。
  • 与えられたノードを表す入力文字列を与えられたすべての子(ある種のリストまたは文字列の配列)を得ることができる必要があります

これに対して利用可能な構造があるか、独自のものを作成する必要がありますか(実装上の提案があれば)。




Collectionフレームワークを使用しない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);             
}
}



これはどうですか?

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



Garethの答えと同じ行に沿って、 DefaultMutableTreeNodeチェックしてDefaultMutableTreeNode 。 それは一般的ではありませんが、そうでなければ法案に適合しているようです。 javax.swingパッケージに含まれていても、AWTクラスやSwingクラスに依存しません。 実際には、ソースコードには実際にコメントがあります// ISSUE: this class depends on nothing in AWT -- move to java.util?




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



パスの追加をサポートする「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(", "));
}

そしてあなたは素敵な木を手に入れます。 あなたのニーズに適応するのは簡単なはずです。




私は、Java8でうまくやっているツリーライブラリを書いています。他の依存関係はありません。 また、関数型プログラミングからいくつかのアイデアを緩やかに解釈し、ツリーまたはサブツリー全体をマップ/フィルタ/プルーン/検索することもできます。

https://github.com/RutledgePaulV/prune

実装はインデックス作成で特別なことはしませんし、再帰から離れずに済むので、大きなツリーのパフォーマンスが低下し、スタックを壊す可能性があります。 しかし、必要なのは深さの小さいものから順調なものであれば十分です。 それは、平等性の正当な(値に基づいた)定義を提供し、ツリーの可視化を可能にするtoString実装も備えています!




Jakartaプロジェクトの一部であるApache JMeterに含まれるHashTreeクラスを使用できます。

HashTreeクラスは、org.apache.jorphan.collectionsパッケージに含まれています。 このパッケージはJMeterプロジェクトの外部にはリリースされていませんが、簡単に入手できます:

1) JMeterソースをダウンロードします

2)新しいパッケージを作成します。

3)/ src / jorphan / org / apache / jorphan / collections /にコピーします。 Data.javaを除くすべてのファイル

4)/src/jorphan/org/apache/jorphan/util/JOrphanUtils.javaもコピーします。

5)HashTreeはすぐに使用できます。




ホワイトボードのコーディング、インタビュー、または単にツリーの使用を計画している場合でも、これらの冗長さはほんの少しです。

さらに、ツリーが存在しない理由( 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
[]



答えは単純化されていても動作しているコードなので、ここではそれはありません:

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



これまで、私はこれまでネストされたマップを使っていました。 これは私が今日使っているものですが、それはとてもシンプルですが、私のニーズに合っています。 多分、これは別のものを助けるでしょう。

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



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

明らかに、子供を追加/削除するユーティリティメソッドを追加することができます。




Related