Teori pohon ini sebenarnya adalah suatu mekanisme penyelesaian suatu masalah dengan menganalogikan permasalahan tersebut kedalam struktur pohon untuk memudahkan pencarian solusi masalah tersebut. Teori pohon ini juga merupakan salah satu penerapan konsep graf. Dimana pohon itu dapat didefinisikan sebagai graf tak-berarah terhubung yang tidak mengandung sirkuit.
Kajian struktur data merupakan kajian yang sangat penting dalam bidang informatika. Dan di zaman sekarang ini yang teknologinya semakin berkembang, dibutuhkan struktur data yang efisien yang dapat meningkatkan kinerja program. Teori pohon ini merupakan teori yang sangat berguna dalam struktur data dimana aplikasi aplikasi dari teori pohon ini dapat dijadikanstruktur penyimpanan data yang sangat baik dalam kasus tertentu yang mana kasus tersebut sudah umum ditemui sekarang ini. Oleh karena itu dalam makalah ini akan dijelaskan beberapa aplikasi teori pohon yang dipakai untuk membentuk suatu struktur penyimpanan data yang efisien.
PEMBAHASAN
Jika kita memperhatikan setiap simpul dalam pohon biner, kita bisa menyusun struktur data yang tepat dari simpul-simpul tersebut. Kita dapat melihat bahwa dalam setiap simpul selalu berisi dua buah pointer untuk menunjuk ke cabang kiri dan cabang kanan, dan informasi yang akan disimpan dalamsimpul tersebut. Dengan memperhatikan hal ini, simpul dalam pohon biner disajikan sebagai berikut:
KIRI
INFO
KANAN
Gambar
Sesuai dengan gambar, maka deklarasi list yang sesuai adalah:
typedef char TypeInfo;
typedef struct Simpul *Tree;
struct Simpul { TypeInfo Info;
 tree Kiri, /* cabang kiri */Kanan;
/* cabang kanan */ };
BINARY SEARCH TREE
Binary Tree ini memiliki sifat dimana semua left child harus lebih kecil dari pada right child dan parentnya. Semua right child juga harus lebih besar dari left child serta parentnya. Binary search tree dibuat untuk mengatasi kelemahan pada binary tree biasa, yaitu kesulitan dalam searching / pendarian node tertentu dalam binary tree. Pada dasarnya operasi dalam Binary Search Tree sama dengan Binary Tree biasa, kecuali pada operasi insert, update, dan delete.
Bayangkan apabila kita ingin mencari sebuah data pada sebuah senarai berkait, tentunya tidak ada cara selain mencarinya secara sekuensial dari pointer elemen pertama senarai. Bandingkan jika kita melakukan pencarian di tabel kontigu dan dengan pencarian biner (binary search), tentunya pencarian akan lebih cepat. Dan sekarang bayangkan jika kita ingin melakukan operasi penambahan dan penghapusan elemen senarai.Operasi tersebut akan lebih lambat pada tabel kontigu daripada senarai berkait. Hal ini disebabkan karena operasi penambahan dan penghapusan pada tabel kontigu memerlukan pemindahan banyak entri data setiap saat, dibandingkan dengan senarai berkait yang hanya membutuhkan sedikit permainan pointer.
