Pohon biner

Pohon atau tree adalah salah satu bentuk graph terhubung yang tidak mengandung
sirkuit. Karena merupakan graph terhubung, maka pada pohon selalu terdapat path
atau jalur yang menghubungkan setiap dua simpul dalam pohon. Kali ini kita sampai
pada pembahasan suatu bentuk pohon, yang dilengkapi dengan apa yang disebut “akar”
atau “root”. Pohon semacam ini disebut pohon berakar atau rooted tree. Selanjutnya,
lebih khusus lagi dibahas tentang pohon berakar yang disebut “pohon binar” atau
“binary tree”.
Sebuah pohon binar T didefinisikan terdiri atas sebuah himpunan hingga elemen
yang disebut simpul (node), sedemikian sehingga:
(a) T adalah hampa (disebut pohon null) atau;
(b) T mengandung simpul R yang dipilih (dibedakan dari yang lain), disebut “akar”
atau “root” dari T, dan simpul sisanya membentuk 2 pohon binar (subpohon kiri
dan subpohon kanan dari akar R) T1 dan T2 yang saling lepas.