STRUKTUR DATA TREE

• Ba
  
• 
  
  
• 
  

Dalam ilmu komputer , pohon adalah tipe data abstrak yang digunakan secara luas yang mewakili struktur pohon hierarkis dengan sekumpulan simpul yang terhubung . Setiap simpul di pohon dapat dihubungkan ke banyak anak (tergantung pada jenis pohon), tetapi harus dihubungkan ke tepat satu induk, ^[ 1 ] kecuali untuk simpul akar , yang tidak memiliki induk (yaitu, simpul akar sebagai simpul paling atas dalam hierarki pohon). Batasan-batasan ini berarti tidak ada siklus atau "loop" (tidak ada simpul yang dapat menjadi leluhurnya sendiri), dan juga bahwa setiap anak dapat diperlakukan seperti simpul akar dari sub-pohonnya sendiri, menjadikan rekursi sebagai teknik yang berguna untuk traversal pohon . Berbeda dengan struktur data linear , banyak pohon tidak dapat direpresentasikan oleh hubungan antara simpul-simpul tetangga (simpul induk dan anak dari suatu simpul yang dipertimbangkan, jika ada) dalam satu garis lurus (disebut tepi atau tautan antara dua simpul yang berdekatan).

Pohon yang tidak diurutkan ini memiliki nilai yang tidak unik (misalnya, nilai 2 ada di node yang berbeda, tidak hanya di satu node) dan bersifat non-biner (hanya hingga dua node anak per node induk dalam pohon biner). Node akar di bagian atas (dengan nilai 2 di sini), tidak memiliki induk karena merupakan node tertinggi dalam hierarki pohon.

Pohon biner adalah jenis yang umum digunakan, yang membatasi jumlah anak untuk setiap induk hingga maksimal dua. Ketika urutan anak ditentukan, struktur data ini sesuai dengan pohon terurut dalam teori grafik . Nilai atau penunjuk ke data lain dapat dikaitkan dengan setiap simpul di pohon, atau terkadang hanya dengan simpul daun , yang tidak memiliki simpul anak.

Tipe data abstrak (ADT) dapat direpresentasikan dalam sejumlah cara, termasuk daftar induk dengan penunjuk ke anak, daftar anak dengan penunjuk ke induk, atau daftar simpul dan daftar terpisah relasi induk-anak (tipe spesifik dari daftar ketetanggaan ). Representasi mungkin juga lebih rumit, misalnya menggunakan indeks atau daftar leluhur untuk kinerja.

Pohon sebagaimana digunakan dalam komputasi serupa tetapi dapat berbeda dari konstruksi matematika pohon dalam teori grafik , pohon dalam teori himpunan , dan pohon dalam teori himpunan deskriptif .