|
#ALIH [[Pohon biner]]
[[Berkas:Binary_tree.svg|ka|jmpl|192x192px|A labeled binary tree of size 9 and height 3, with a root node whose value is 2. The above tree is unbalanced and not sorted.]]
Dalam ilmu komputer, sebuah pohon biner adalah struktur data pohon di mana setiap node memiliki paling banyak dua anak, yang disebut sebagai anak kiri dan anak kanan. Definisi rekursif hanya menggunakan teori himpunan gagasan adalah bahwa (non-kosong) pohon biner adalah tiga (L, S, R), di mana L dan R adalah pohon biner atau himpunan kosong dan S adalah satu set tunggal. Beberapa penulis memungkinkan pohon biner menjadi himpunan kosong juga.<span class="cx-segment" data-segmentid="22"></span>
Dari perspektif teori grafik, biner (dan K-ary) pohon seperti yang didefinisikan di sini sebenarnya arborescences. Sebuah pohon biner sehingga dapat juga disebut bifurcating arborescence-istilah yang benar-benar muncul di beberapa buku-buku pemrograman yang sangat tua, sebelum terminologi ilmu komputer modern menang. Hal ini juga memungkinkan untuk menafsirkan sebuah pohon biner sebagai diarahkan, bukan grafik diarahkan, dalam hal pohon biner adalah memerintahkan, berakar pohon. Beberapa penulis menggunakan berakar pohon biner bukan pohon biner untuk menekankan fakta bahwa pohon berakar, tetapi seperti yang didefinisikan di atas, pohon biner selalu berakar. Sebuah pohon biner adalah kasus khusus dari pohon K-ary memerintahkan, di mana k adalah 2.<span class="cx-segment" data-segmentid="34"></span>
Dalam komputasi, pohon biner jarang digunakan semata-mata untuk struktur mereka. Jauh lebih khas adalah untuk mendefinisikan fungsi pelabelan pada node, yang menghubungkan beberapa nilai untuk setiap node. Pohon biner berlabel cara ini digunakan untuk mengimplementasikan pohon pencarian biner dan tumpukan biner, dan digunakan untuk pencarian yang efisien dan penyortiran. Penunjukan node non-root sebagai kiri atau kanan anak bahkan ketika hanya ada satu anak hal hadir dalam beberapa aplikasi, khususnya adalah penting dalam pohon pencarian biner. Dalam matematika, apa yang disebut pohon biner dapat bervariasi secara signifikan dari penulis ke penulis. Beberapa menggunakan definisi yang biasa digunakan dalam ilmu komputer, tetapi yang lain mendefinisikannya sebagai setiap non-daun memiliki tepat dua anak dan tidak selalu order (sebagai kiri / kanan) anak-anak baik.<span class="cx-segment" data-segmentid="46"></span>
== Definisi ==
=== Definisi rekursif ===
Cara lain untuk mendefinisikan pohon biner penuh adalah definisi rekursif. Sebuah pohon biner penuh adalah baik:<span class="cx-segment" data-segmentid="70"></span>
* Sebuah titik tunggal.
* Sebuah grafik yang dibentuk dengan mengambil dua (penuh) pohon biner, menambahkan sebuah sudut, dan menambahkan tepi diarahkan dari titik baru ke akar setiap pohon biner.
Ini juga tidak menetapkan urutan anak-anak, tetapi tidak memperbaiki akar tertentu.
Untuk benar-benar mendefinisikan pohon biner secara umum, kita harus memungkinkan untuk kemungkinan bahwa hanya satu dari anak-anak mungkin kosong. Artefak, yang dalam beberapa buku teks disebut pohon biner diperpanjang diperlukan untuk tujuan itu. Sebuah pohon biner diperpanjang demikian rekursif didefinisikan sebagai:<span class="cx-segment" data-segmentid="81"></span>
* Himpunan kosong adalah pohon biner diperpanjang
* ika T1 dan T2 yang diperpanjang pohon biner, kemudian dilambangkan dengan T1 • T2 pohon biner diperpanjang diperoleh dengan menambahkan r akar terhubung ke kiri untuk T1 dan ke kanan untuk T2 dengan menambahkan tepi ketika sub-pohon yang tidak kosong.
== References ==
=== Citations ===
{{Reflist|33em}}
[[Kategori:Struktur data]]
| 