Mengenal Tree Dalam Struktur Data

Apa itu Tree?

Tree adalah tipe struktur data yang sifatnya non-linier dan berbentuk hierarki. Tree disebut struktur data non-liniar karena data tidak disimpan secara berurutan, tetapi diorganisir hierarkis. Analogi dengan pohon keluarga menjelaskan hubungan antara simpul induk (atas) dan simpul anak (bawah). Setiap simpul tree menyimpan nilai dan referensi ke simpul lain sebagai child node, dihubungkan oleh edge atau garis. 
Dalam implementasinya, pointer sering digunakan. Sebuah simpul dapat memiliki beberapa child node, tetapi hanya dapat dicapai melalui satu node, dan jika tidak memiliki child node, disebut leaf node. Tree sebagai struktur data efektif dalam menyimpan dan mengatur data di komputer, dengan Binary Tree sebagai jenis yang umum, memiliki maksimal 2 child node.

Istilah-istilah pada Tree

• Node : Entitas pada struktur data tree yang mengandung sebuah nilai dan pointer yang menunjuk simpul di bawahnya (child node).
• Child Node : Simpul atau Node turunan dari simpul di atasnya.
• Leaf Node : simpul yang tidak memiliki child node dan merupakan node yang paling bawah dalam struktur data tree. Simpul ini biasa disebut juga sebagai external node.
• Root : simpul teratas dari sebuah tree.
• Internal Node : istilah untuk menyebut simpul yang memiliki minimal satu child node.
• Edge : Edge merujuk pada garis yang menghubungkan antara dua buah simpul dalam tree. Jika sebuah tree memiliki N node maka tree tersebut akan memiliki (N-1) edge. Hanya ada satu jalur dari setiap simpul ke simpul lainnya.
• Height of Node : Jumlah edge dari sebuah node ke leaf node yang paling dalam.
• Depth of Node : Banyaknya edge dari root ke sebuah node.
• Height of Tree : Dapat diartikan sebagai panjang jalur terpanjang dari simpul akar ke simpul daun dari seuah tree.
• Degree of Node : Jumlah cabang yang melekat pada simpul disebut Degree of node atau derajat simpul. Derajat simpul pada sebuah leaf node adalah 0. 
• Degree of Tree : Derajat maksimum simpul di antara semua simpul pada tree.
• Subtree : setiap simpul dari tree beserta turunannya.

Contoh Implementasi Tree

    
class TreeNode {
    int key;
    TreeNode left, right;

    public TreeNode(int item) {
        key = item;
        left = right = null;
    }
}

public class BinaryTree {
    TreeNode root;

    public BinaryTree() {
        root = null;
    }

    void insert(int key) {
        root = insertRec(root, key);
    }

    TreeNode insertRec(TreeNode root, int key) {
        if (root == null) {
            root = new TreeNode(key);
            return root;
        }

        if (key < root.key) {
            root.left = insertRec(root.left, key);
        } else if (key > root.key) {
            root.right = insertRec(root.right, key);
        }

        return root;
    }

    void inorderTraversal(TreeNode root) {
        if (root != null) {
            inorderTraversal(root.left);
            System.out.print(root.key + " ");
            inorderTraversal(root.right);
        }
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();

        int[] keys = {8, 3, 10, 1, 6, 14, 4, 7, 13};

        for (int key : keys) {
            tree.insert(key);
        }

        System.out.println("Inorder Traversal:");
        tree.inorderTraversal(tree.root);
    }
}

    
  

Output:

    
Inorder Traversal:
1 3 4 6 7 8 10 13 14