POHON (TREE)

Definisi Rekurens Dari Pohon:

Sebuah pohon adalah himpunan terbatas tidak kosong, dengan elemen yang dibedakan sebagai berikut :
1.     Sebuah elemen yang dibedakan dari yang lain yang disebut sebagai AKAR (root) dari pohon
2.     Elemen yang lain (jika masih ada) dibagi-bagi menjadi beberapa sub himpunan yang disjoint dan masing-masing sub himpunan tersebut adalah pohon yang disebut sebagai sub pohon dari pohon tersebut.

Sifat sifat pohon:

1. Jika Pohon mempunyai simpul sebanyak n,maka banyaknya ruas atau edge adalah n-1
2. Mempunyai simpul khusus yang di sebut root,jika simpul tersebut mempunyai derajat keluar >=0,dan derajat masuk = 0
3. Mempunyai simpul yang disebut daun/leaf,jika simpul tersebut berderajat keluar = 0,dan berderajat masuk = 1
4. Setiap simpul mempunyai Tingkatan/level yang dimulai dari root yang levelnya =1,sampai dengan  level ke-n yang berada pada daun yang paling bawah.simpul yang mempunyai level sama di sebut bersaudara
5. Pohon mempunyai ketinggian atau kedalaman atau height ,yang merupakan level tertinggi.
6. Pohon mempunyai berat atau weight,yang banyaknya daun pada pohon.

Beberapa Istilah:

1.      Hutan adalah sequence (list) dari pohon.

2.      Simpul (Node) Simpul adalah elemen dari pohon yang memungkinkan akses pada sub pohon dimana simpul tersebut berfungsi sebagai Akar

3.      Cabang   adalah hubungan antara Akar dengan sub pohon

4.      Ayah, Akar  dari sebuah pohon adalah Ayah dari sub pohon

5.       Anak , dari sebuah pohon adalah Sub pohon.

6.       Saudara  adalah simpul-simpul yang mempunyai Ayah yang sama

7.       Daun adalah simpul terminal dari pohon. Semua simpul  selain Daun adalah simpul bukan terminal

8.      Jalan (Path) adalah suatu urutan tertentu dari Cabang

9.      Derajat
Derajat sebuah pohon adalah banyaknya anak dari  dari pohon tersebut.
Jika sebuah simpul berderajat N disebut     pohon N-aire
1 disebut pohon 1-aire/uner
2 disebut pohon 2-aire/biner

Struktur Pohon Biner

Sebuah pohon biner (Binary Tree) adalah himpunan terbatas yang :
Mungkin kosong atau terdiri dari sebuah simpul yang disebut sebagai Akar dan dua buah himpunan lain yang disjoint yang merupakan pohon biner yang disebut sebagai Sub Pohon Kiri (Left) dan Sub Pohon Kanan (Right) dari pohon biner tersebut. Pohon biner merupakan tipe yang sangat penting  dari struktur data dan banyak dijumpai  dalam berbagai terapan. Karakteristik yang  dimiliki oleh pohon biner adalah bahwa     setiap simpul paling banyak hanya   memiliki  dua buah anak, dan mungkin tidak punya anak.

Karakteristik Pohon binar

1. Setiap simpul paling banyak hanya memiliki dua buah anak.
2. Derajat tertinggi dari setiap simpul adalah dua
3. Dibedakan antara cabang kiri dan cabang kanan
4. Dimmungkinkan tidak memiliki simpul

dibawah ini contoh pohon binar dengan cabang kiri dan kanan

Istilah pada pohon binar(binary tree)

• Pohon binar penuh (full binary tree)

semua simpul (kecuali daun) memiliki dua anak dan tiap cabang memiliki panjang ruas yang sama

• Pohon Binar lengkap(complate binary tree)

hampir sama dengan pohon biner penuh,bedanya tiap cabang memiliki ruas berbeda

• Pohon biner Similer

Dua pohon yang memiliki struktur sama tapi informasinya berbeda

• Pohon biner Ekivalent

Dua pohon yang memiliki struktur sama dan informasi yang sama.

• Pohon biner Miring(skewed Tree)

Dua pohon yang semua simpulnya mempunyai satu anak /turunan kecuali daun.

deklarasi Pohon Biner dengan program C++

Dalam setiap simpul selalu berisi dua buah pointer untuk menunjuk ke arah cabang kiri dan cabang kanan dan informasi yang akan di simpan .

Penyajian Pohon Binar (binary tree)

• Tree dapat dibuat dengan menggunakan linked list secara rekursif
• linked list yang digunakan adalah double linked list non circural
• data yang pertama kali masuk akan menjadi node root
• data yang lebih kecil dari node root akan masuk dan menempati node kiri dari node root,sedangkan jika lebih besar akan masuk dan menempati node sebelah kanan node root