Binary Tree

Pohon biner adalah jenis pohon yang memiliki ke khasan, yaitu jumlah anak setiap simpul maksimal dibatasi dua buah saja.

1. Node

Pada dasarnya pohon biner sama saja dengan list hanya saja koneksinya lebih dari 1. Biasanya node  tree terdiri dari 2 bagian, data dan koneksi. Pada pohon biner terdapat koneksinya adalah koneksi kiri (anak kiri) dan koneksi kanan (anak kanan).

   Gambar 1. Representasi Node

• Data adalah nilai yang disimpan didalam node dan biasanya tipe datanya adalah tipe data primitif.
• Sedangkan L adalah koneksi yang menghubungkan dengan Node sebelah kiri.
• dan R adalah koneksi yang menghubungkan dengan Node sebelah kanan.

Ada juga Node yang memiliki 3 koneksi, yaitu kanan, kiri dan parent.

Gambar 2. Node dengan 3 koneksi

Parent adalah koneksi yang menghubungkan Node dengan Node orang tuanya. Sehingga anaknya bisa mengetahui data orang tuanya. Berbeda dengan Gambar 1, hanya orang tua yang mengenali anak tetapi tidak sebaliknya.

2. Pohon

Sebuah pohon harus memiliki akar atau root. Root dari sebuah pohon tidak boleh lepas karena root adalah pangkal dari sebuah pohon. Jika kita mengetahui pangkal sebuah pohon maka otomatis kita bisa menngunjungi semua node pada pohon tersebut.

Jenis-Jenis Binary Tree

1. Full Binary Tree
   Pohon biner yang semua nodenya (kecuali leaf) pasti memiliki 2 anak dan tiap subtree memiliki tinggi pohon yang sama.
   
2. Complete Binary Tree
   Pohon biner yang mirip dengan full binary tree tetapi tiap subtree memiliki selisih ketinggian minimal 1. Contoh tinggi pohon kiri 2 dan pohon kanan 1. maka selisihnya adalah 1. Jika selisih 1 maka pohon di bawah ini dapat diseput pohon complete.
   
3. Skewed Binary Tree
   Pohon biner yang semua nodenya hanya memiliki 1 anak dan pohonnya condong. Misal condongnya ke kiri maka semua node hanya memiliki anak kiri semua begitu juga sebaliknya.