Binary Tree

Binary tree adalah sebuah struktur data yang menyerupai pohon dan setiap simpulnya memiliki maksimal cabang/anak 2. Pada setiap pohon biner memiliki Root dan Leaf. Root adalah simpul utama yang merupakan simpul awal pada suatu pohon biner. Sedangkan Leaf adalah adalah simpul terakhir yang tidak memiliki cabang lagi.

Tipe-Tipe Pohon Biner

• Perfect Binary Tree

PBT adalah suatu pohon biner yang setiap levelnya memiliki kedalaman yang sama. Terkadang PBT juga termasuk CBT (complete binary tree).

• Complete Binary Tree

CBT adalah suatu pohon biner yang kedalamannya sebesar n atau n-1 untuk beberapa n. Jadi tidak seperti PBT yang harus sama semuanya, melainkan boleh sama ataupun tidak (namun pada simpul kedua dari terakhir saja). Dan dalam penempatan simpulnya diutamakan yang sebelah kiri yang terpenuhi.

• Skewed Binary Tree

SBT merupakan suatu pohon biner yang setiap simpulnya hanya memiliki satu anak atau satu cabang, sehingga membuatnya tidak seimbang.

• Balanced Binary Tree

BBT adalah suatu pohon biner yang tinggi antara anak sebelah kiri dan kanannya hanya berselisih maksimal satu. PBT dan CBT juga merupakan Binary tree yang seimbang.

Untuk melakukan searching dalam binary tree, ada 2 cara:
+Depth First Search (DFS)     :   DFS adalah pencarian berdasarkan kedalamannya.
+Breadth First Search (BFS)   :   BFS adalah pencarian berdasarkan perluasannya.