Bagaimana cara mengimplementasikan struktur data pohon di Jawa? [Tutup]

Apakah ada kelas perpustakaan Java standar untuk mewakili pohon di Jawa?

Secara khusus saya perlu mewakili yang berikut:

• Sub-pohon di sembarang simpul dapat memiliki jumlah anak yang berubah-ubah
• Setiap node (setelah root) dan anak-anak itu akan memiliki nilai string
• Saya perlu mendapatkan semua anak-anak (semacam daftar atau array dari Strings) dari suatu simpul dan nilai string-nya (yaitu metode yang akan mengambil simpul sebagai input dan mengembalikan semua nilai string dari simpul anak-anak sebagai output)

Apakah ada struktur yang tersedia untuk ini atau apakah saya perlu membuat sendiri (jika demikian saran implementasi akan bagus).

Sini:

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

Itu adalah struktur pohon dasar yang dapat digunakan untuk Stringatau objek lain. Cukup mudah untuk menerapkan pohon sederhana untuk melakukan apa yang Anda butuhkan.

Yang perlu Anda tambahkan adalah metode untuk menambahkan, menghapus dari, melintasi, dan konstruktor. Ini Nodeadalah blok bangunan dasar Tree.

Namun struktur pohon lain:

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

}

Penggunaan sampel:

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

BONUS
Lihat pohon lengkap dengan:

• iterator
• mencari
• Java / C #

https://github.com/gt4dev/yet-another-tree-structure

Sebenarnya ada struktur pohon yang cukup bagus diimplementasikan di JDK.

Lihatlah javax.swing.tree , TreeModel , dan TreeNode . Mereka dirancang untuk digunakan dengan JTreePaneltetapi mereka, pada kenyataannya, implementasi pohon yang cukup bagus dan tidak ada yang menghentikan Anda dari menggunakannya tanpa antarmuka ayunan.

Perhatikan bahwa pada Java 9 Anda mungkin ingin tidak menggunakan kelas-kelas ini karena mereka tidak akan hadir di 'Profil ringkas' .

Bagaimana dengan ini?

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;

/**
  * @author [email protected] (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;
  }
}

Saya menulis perpustakaan kecil yang menangani pohon generik. Ini jauh lebih ringan dari pada ayunan. Saya juga punya proyek pakar untuk itu.

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

Jelas Anda dapat menambahkan metode utilitas untuk menambah / menghapus anak-anak.

Anda harus mulai dengan mendefinisikan pohon apa (untuk domain), ini paling baik dilakukan dengan mendefinisikan antarmuka terlebih dahulu. Tidak semua struktur pohon dapat dimodifikasi, dapat menambah dan menghapus node harus menjadi fitur opsional, jadi kami membuat antarmuka tambahan untuk itu.

Tidak perlu membuat objek node yang memegang nilai , pada kenyataannya saya melihat ini sebagai cacat desain utama dan overhead di sebagian besar implementasi pohon. Jika Anda melihat Swing, TreeModelbebas dari kelas simpul (hanya DefaultTreeModelmemanfaatkan TreeNode), karena mereka tidak benar-benar diperlukan.

public interface Tree <N extends Serializable> extends Serializable {
    List<N> getRoots ();
    N getParent (N node);
    List<N> getChildren (N node);
}

Struktur pohon yang dapat diubah (memungkinkan untuk menambah dan menghapus node):

public interface MutableTree <N extends Serializable> extends Tree<N> {
    boolean add (N parent, N node);
    boolean remove (N node, boolean cascade);
}

Dengan adanya antarmuka ini, kode yang menggunakan tree tidak harus terlalu peduli tentang bagaimana tree diimplementasikan. Ini memungkinkan Anda untuk menggunakan implementasi generik serta yang khusus , di mana Anda menyadari pohon dengan mendelegasikan fungsi ke API lain.

Contoh: struktur pohon file

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

Contoh: struktur pohon generik (berdasarkan hubungan orang tua / anak):

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

Tidak ada jawaban yang menyebutkan kode yang terlalu disederhanakan tetapi berfungsi, jadi ini dia:

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

Anda dapat menggunakan API XML apa pun dari Java sebagai Dokumen dan Node..sebagai XML adalah struktur pohon dengan Strings

Jika Anda melakukan pengkodean papan tulis, wawancara, atau bahkan hanya berencana untuk menggunakan pohon, verbositas semua ini sedikit banyak.

Lebih lanjut harus dikatakan bahwa alasan pohon tidak ada di sana seperti, katakanlah a Pair(tentang hal yang sama dapat dikatakan), adalah karena Anda harus merangkum data Anda di kelas menggunakannya, dan implementasi paling sederhana terlihat seperti:

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

Itu benar-benar untuk pohon lebar yang sewenang-wenang.

Jika Anda menginginkan pohon biner, seringkali lebih mudah digunakan dengan bidang bernama:

private class Node { // Using package visibility is an option
  String value;
  Node left;
  Node right;
}

Atau jika Anda menginginkan trie:

private class Node {
  String value;
  Map<char, Node> nodes;
}

Sekarang kamu bilang mau

untuk bisa mendapatkan semua anak (semacam daftar atau array dari Strings) diberi string input yang mewakili suatu node

Kedengarannya seperti pekerjaan rumah Anda.
Tapi karena saya cukup yakin tenggat waktu sekarang telah berlalu ...

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

Ini bisa Anda gunakan seperti:

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

Sepanjang baris yang sama dengan jawaban Gareth, periksa DefaultMutableTreeNode . Itu tidak generik, tetapi sebaliknya tampaknya sesuai dengan tagihan. Meskipun ada dalam paket javax.swing, itu tidak tergantung pada kelas AWT atau Swing. Sebenarnya, kode sumber sebenarnya memiliki komentar// ISSUE: this class depends on nothing in AWT -- move to java.util?

Ada beberapa struktur data pohon di Jawa, seperti DefaultMutableTreeNode di JDK Swing, paket parser Tree in Stanford, dan kode mainan lainnya. Tetapi tidak ada yang cukup namun cukup kecil untuk tujuan umum.

Proyek Java-tree mencoba untuk menyediakan struktur data pohon tujuan umum lainnya di Jawa. Perbedaan antara ini dan yang lainnya adalah

• Benar-benar gratis Anda dapat menggunakannya di mana saja (kecuali dalam pekerjaan rumah Anda: P)
• Kecil tapi cukup umum. Saya meletakkan semua struktur data dalam satu file kelas, jadi akan mudah untuk menyalin / menempel.
• Bukan hanya mainan. Saya mengetahui puluhan kode pohon Java yang hanya dapat menangani pohon biner atau operasi terbatas. TreeNode ini jauh lebih dari itu. Ini menyediakan berbagai cara mengunjungi node, seperti preorder, postorder, breadthfirst, leaves, path to root, dll. Selain itu, iterator juga disediakan untuk kecukupan.
• Utilitas lainnya akan ditambahkan. Saya bersedia menambahkan lebih banyak operasi untuk membuat proyek ini komprehensif, terutama jika Anda mengirim permintaan melalui github.

Karena pertanyaannya menanyakan struktur data yang tersedia, pohon dapat dibangun dari daftar atau array:

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

instanceof dapat digunakan untuk menentukan apakah suatu elemen subtree atau terminal node.

public abstract class Node {
  List<Node> children;

  public List<Node> getChidren() {
    if (children == null) {
      children = new ArrayList<>();
    }
    return chidren;
  }
}

Sesederhana dan sangat mudah digunakan. Untuk menggunakannya, perluas:

public class MenuItem extends Node {
  String label;
  String href;
  ...
}

Sebagai contoh :

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

Di masa lalu saya baru saja menggunakan peta bersarang untuk ini. Inilah yang saya gunakan hari ini, sangat sederhana tetapi sesuai dengan kebutuhan saya. Mungkin ini akan membantu yang lain.

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

Saya menulis kelas "TreeMap" kecil berdasarkan "HashMap" yang mendukung penambahan jalur:

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

}

Dapat digunakan untuk menyimpan Tree of type "T" (generic), tetapi tidak (belum) mendukung penyimpanan data tambahan di node-node itu. Jika Anda memiliki file seperti ini:

root, child 1
root, child 1, child 1a
root, child 1, child 1b
root, child 2
root, child 3, child 3a

Kemudian Anda bisa menjadikannya pohon dengan mengeksekusi:

TreeMap<String> root = new TreeMap<>();
Scanner scanner = new Scanner(new File("input.txt"));
while (scanner.hasNextLine()) {
  root.put(scanner.nextLine().split(", "));
}

Dan Anda akan mendapatkan pohon yang bagus. Seharusnya mudah beradaptasi dengan kebutuhan Anda.

Anda dapat menggunakan kelas HashTree yang termasuk dalam Apache JMeter yang merupakan bagian dari Proyek Jakarta.

Kelas HashTree termasuk dalam paket org.apache.jorphan.collections. Meskipun paket ini tidak dirilis di luar proyek JMeter, Anda bisa mendapatkannya dengan mudah:

1) Unduh sumber JMeter .

2) Buat paket baru.

3) Salin di atasnya / src / jorphan / org / apache / jorphan / koleksi /. Semua file kecuali Data.java

4) Salin juga /src/jorphan/org/apache/jorphan/util/JOrphanUtils.java

5) HashTree siap digunakan.

Tidak ada struktur data khusus di Jawa yang sesuai dengan kebutuhan Anda. Persyaratan Anda cukup spesifik dan untuk itu Anda perlu merancang struktur data Anda sendiri. Melihat persyaratan Anda, siapa pun dapat mengatakan bahwa Anda memerlukan semacam n-ary tree dengan beberapa fungsi spesifik. Anda dapat merancang struktur data Anda dengan cara berikut:

1. Struktur simpul pohon akan seperti konten dalam simpul dan daftar anak-anak seperti: class Node {Nilai string; Daftar anak-anak;}
2. Anda perlu mengambil anak-anak dari string yang diberikan, sehingga Anda dapat memiliki 2 metode 1: Node searchNode (String str), akan mengembalikan node yang memiliki nilai yang sama seperti input yang diberikan (gunakan BFS untuk mencari) 2: Daftar getChildren (String str): metode ini secara internal akan memanggil searchNode untuk mendapatkan node yang memiliki string yang sama dan kemudian akan membuat daftar semua nilai string anak-anak dan kembali.
3. Anda juga akan diminta untuk memasukkan string di pohon. Anda harus menulis satu metode say void insert (String parent, String value): ini lagi akan mencari simpul yang memiliki nilai sama dengan induk dan kemudian Anda dapat membuat Node dengan nilai yang diberikan dan menambahkan ke daftar anak-anak ke induk yang ditemukan .

Saya akan menyarankan, Anda menulis struktur simpul dalam satu kelas seperti Class Node {nilai String; Daftarkan anak-anak;} dan semua metode lain seperti pencarian, masukkan dan getChildren di kelas NodeUtils lain sehingga Anda juga dapat melewati root pohon untuk melakukan operasi pada pohon tertentu seperti: class NodeUtils {pencarian Node statis publik (Node root, nilai String) {// lakukan BFS dan kembalikan 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);
  }
}

Saya menulis pustaka pohon yang berfungsi baik dengan Java8 dan tidak memiliki dependensi lain. Ini juga memberikan interpretasi longgar dari beberapa ide dari pemrograman fungsional dan memungkinkan Anda memetakan / menyaring / memangkas / mencari seluruh pohon atau sub pohon.

https://github.com/RutledgePaulV/prune

Implementasinya tidak melakukan sesuatu yang istimewa dengan pengindeksan dan saya tidak menyimpang dari rekursi, jadi ada kemungkinan bahwa dengan kinerja pohon besar akan menurun dan Anda dapat menghancurkan stack. Tetapi jika yang Anda butuhkan adalah pohon langsung dengan kedalaman kecil hingga sedang, saya pikir itu bekerja dengan cukup baik. Ini memberikan definisi kesetaraan yang waras (berbasis nilai) dan juga memiliki implementasi toString yang memungkinkan Anda memvisualisasikan pohon!

Silakan periksa kode di bawah ini, di mana saya telah menggunakan struktur data Tree, tanpa menggunakan kelas Koleksi. Kode mungkin memiliki bug / perbaikan tetapi harap gunakan ini hanya untuk referensi

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

    }

}

Anda dapat menggunakan kelas TreeSet di java.util. *. Ini berfungsi seperti pohon pencarian Biner, jadi sudah diurutkan. Kelas TreeSet mengimplementasikan antarmuka Iterable, Collection dan Set. Anda dapat melintasi pohon dengan iterator seperti set.

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

Anda dapat memeriksa, Java Doc dan lainnya .

Custom Tree mengimplementasikan Tree tanpa menggunakan framework Collection. Ini berisi operasi fundamental berbeda yang diperlukan dalam implementasi 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);             
    }

}