STRUKTUR DATA TREE

- Deskripsi Tree

—  Kumpulan node yang saling terhubung satu sama lain dalam suatu kesatuan yang membentuk layakya struktur sebuah pohon.

—  Struktur pohon adalah suatu cara merepresentasikan suatu struktur hirarki (one-to-many) secara grafis yang mirip sebuah pohon, walaupun pohon tersebut hanya tampak sebagai kumpulan node-node dari atas ke bawah.

—  Suatu struktur data yang tidak linier yang menggambarkan hubungan yang hirarkis (one-to-many) dan tidak linier antara elemen-elemennya.

- Contoh penggunaan struktur pohon :

• Silsilah keluarga
• Parse Tree (pada compiler)
• Struktur File
• Pertandingan

Struktur Pohon

- Operasi-operasi Pada Tree

• —  Insert: menambah node ke dalam Tree secara rekursif.  Jika data yang akan dimasukkan lebih besar daripada elemen root, maka akan diletakkan di node sebelah kanan, sebaliknya jika lebih kecil maka akan diletakkan di node sebelah kiri.  Untuk data pertama akan menjadi elemen root.
• —  Find: mencari node di dalam Tree secara rekursif sampai node tersebut ditemukan dengan menggunakan variable bantuan ketemu.  Syaratnya adalah tree tidak boleh kosong.
• —  Traverse: yaitu operasi kunjungan terhadap node-node dalam pohon dimana masing-masing node akan dikunjungi sekali.
• —  Count: menghitung jumlah node dalam Tree.
• —  Height : mengetahui kedalaman sebuah Tree.
• —  Find Min dan Find Max : mencari nilai terkecil dan terbesar pada Tree.
• —  Child : mengetahui anak dari sebuah node (jika punya).
•   Daun/leaf : Simpul yang derajat = 0 disebut daun / leaf
•   Hubungan antar simpul : bapak, ,anak, paman, dll
•   Tingkat (level)
•   Derajat (degree)
•   Tinggi (height)/kedalaman (depth) : height = tingkat maksimum – 1
•    Ancestor : semua simpul yang terdapat pada lintasan/jalur dari akar sampai simpul tersebut
•    Forest (Hutan) : kumpulan sejumlah pohon yang tidak saling berhubungan

- Jenis Tree

• Berdasarkan banyaknya anak :

1. binary tree / pedigree chart : Complete Binary Tree tingkat N,Skewed BinaryTree
2. Non Binary Tree (N-ary) & lineal chart

• Dari pentingnya urutan Isi :

1. Ordered tree
2. non ordered tree

- Jenis Traverse

1. —  PreOrder: cetak node yang dikunjungi, kunjungi left, kunjungi right
2. —  InOrder: kunjungi left, cetak node yang dikunjungi, kunjungi right
3. —  PostOrder: kunjungi left, kunjungi right, cetak node yang dikunjungi.

- Cara Penulisan Tree :

• 1. Diagram venn
• 2. Notasi Kurung

- Representasi Lojik

Type Infotype : …………{terdefinisi}

Type address : ………{terdefinisi, sesuai dengan representasi fisik}

Type Node : < Info : Infotype,

Left : address,

Right : address >

Type BinTree : address

Jika P adalah binary tree, maka

Left (P) : mendapatkan alamat cabang kiri dari P

right (P) : mendapatkan alamat cabang kanan dari P

info (P) : mendapatkan bagian info dari node yang ditunjuk P

PRIMITIF-PRIMITIF

• Make Tree

• Menyisipkan simpul baru pada binary search Tree

• Pengecekan predikat penting

- Algoritma Traversal Tree