Pohon biner - Riwayat revisi

Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

2026-08-23T10:22:23Z

Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

← Revisi sebelumnya		Revisi per 23 Agustus 2026 10.22
Baris 1:		Baris 1:
			[[File:Binary_tree.svg\|thumb\|right\|280px\|Binary tree]]

	Dalam [[ilmu komputer]], sebuah '''pohon biner''' ''('''binary tree''')'' adalah sebuah [[Pohon (struktur data)\|pohon]] [[struktur data]] di mana setiap [[Pohon (struktur data)#Simpul (node)\|simpul]] memiliki paling banyak dua [[Pohon (struktur data)\|anak]]. Secara khusus anaknya dinamakan ''kiri'' dan ''kanan''. Penggunaan secara umum pohon biner adalah [[Pohon biner terurut]], yang lainnnya adalah [[heap biner]].		Dalam [[ilmu komputer]], sebuah '''pohon biner''' ''('''binary tree''')'' adalah sebuah [[Pohon (struktur data)\|pohon]] [[struktur data]] di mana setiap [[Pohon (struktur data)#Simpul (node)\|simpul]] memiliki paling banyak dua [[Pohon (struktur data)\|anak]]. Secara khusus anaknya dinamakan ''kiri'' dan ''kanan''. Penggunaan secara umum pohon biner adalah [[Pohon biner terurut]], yang lainnnya adalah [[heap biner]].

Baris 8:		Baris 10:

	== Definisi ==		== Definisi ==

	=== Definisi rekursif ===		=== Definisi rekursif ===
	Cara lain untuk mendefinisikan pohon biner penuh adalah definisi rekursif. Sebuah pohon biner penuh adalah baik:		Cara lain untuk mendefinisikan pohon biner penuh adalah definisi rekursif. Sebuah pohon biner penuh adalah baik:
Baris 62:		Baris 63:

	Pohon biner dapat juga disimpan sebagai [[struktur data implisit]] dalam [[array]], dan jika pohon tersebut merupakan sebuah pohon biner lengkap, metode ini tidak boros tempat. Dalam penyusunan yang rapat ini, jika sebuah simpul memiliki indeks ''i'', anaknya dapat ditemukan pada indeks ke-2''i''+1 dan 2''i''+2, meskipun ayahnya (jika ada) ditemukan pada indeks ''[[Fungsi lantai\|lantai]]((i-1)/2)'' (asumsikan akarnya memiliki indeks kosong). Metode ini menguntungkan dari banyak penyimpanan yang rapat dan memiliki referensi lokal yang lebih baik, tersitimewa selama sebuah ''preorder traversal''. Bagaimanapun juga, ini terlalu mahal untuk perkembangannya dan boros tempat sebanding dengan 2<sup>''h''</sup> - ''n'' untuk sebuah pohon dengan tinggi ''h'' dengan ''n''simpul.		Pohon biner dapat juga disimpan sebagai [[struktur data implisit]] dalam [[array]], dan jika pohon tersebut merupakan sebuah pohon biner lengkap, metode ini tidak boros tempat. Dalam penyusunan yang rapat ini, jika sebuah simpul memiliki indeks ''i'', anaknya dapat ditemukan pada indeks ke-2''i''+1 dan 2''i''+2, meskipun ayahnya (jika ada) ditemukan pada indeks ''[[Fungsi lantai\|lantai]]((i-1)/2)'' (asumsikan akarnya memiliki indeks kosong). Metode ini menguntungkan dari banyak penyimpanan yang rapat dan memiliki referensi lokal yang lebih baik, tersitimewa selama sebuah ''preorder traversal''. Bagaimanapun juga, ini terlalu mahal untuk perkembangannya dan boros tempat sebanding dengan 2<sup>''h''</sup> - ''n'' untuk sebuah pohon dengan tinggi ''h'' dengan ''n''simpul.


	Dalam bahasa dengan ''[[tagged union]]'' seperti [[Bahasa pemrograman ML\|ML]], sebuah simpul pohon sering kali sebuah ''tagged union'' dari dua jenis simpul, di mana yang satu merupakan data dari 3-tupel, anak kiri, dan anak kanan, dan yang lain di mana sebuah daun, yang tidak memuat data dan fungsi seperti nilai nol dalam bahasa dengan ''penunjuk (pointers)''		Dalam bahasa dengan ''[[tagged union]]'' seperti [[Bahasa pemrograman ML\|ML]], sebuah simpul pohon sering kali sebuah ''tagged union'' dari dua jenis simpul, di mana yang satu merupakan data dari 3-tupel, anak kiri, dan anak kanan, dan yang lain di mana sebuah daun, yang tidak memuat data dan fungsi seperti nilai nol dalam bahasa dengan ''penunjuk (pointers)''
Baris 70:		Baris 70:

	=== Pre-order, in-order, dan post-order traversal ===		=== Pre-order, in-order, dan post-order traversal ===

	Pre-order, in-order, dan post-order traversal mengunjungi setiap simpul dalam sebuah pohon dengan pengunjungan secara berulang-ulang pada sub pohon kiri dan kanan dari akarnya. Jika akarnya dikunjungi sebelum sub pohonnya, ini merupakan preoder. Jika akarnya dikunjungi sesudah sub pohonnya, ini dinamakan postorder dan jika akarnya dikunjungi di antara sub pohonnya, dinamakan inorder. In-order traversal sangat berguna dalam [[pohon biner terurut]], di mana ''traversal'' ini mengunjungi simpul dalam urutan yang meningkat.		Pre-order, in-order, dan post-order traversal mengunjungi setiap simpul dalam sebuah pohon dengan pengunjungan secara berulang-ulang pada sub pohon kiri dan kanan dari akarnya. Jika akarnya dikunjungi sebelum sub pohonnya, ini merupakan preoder. Jika akarnya dikunjungi sesudah sub pohonnya, ini dinamakan postorder dan jika akarnya dikunjungi di antara sub pohonnya, dinamakan inorder. In-order traversal sangat berguna dalam [[pohon biner terurut]], di mana ''traversal'' ini mengunjungi simpul dalam urutan yang meningkat.

Baris 80:		Baris 79:

	== Penyandian ==		== Penyandian ==

	=== Penyandian ringkas ===		=== Penyandian ringkas ===
	Sebuah ''struktur data ringkas'' adalah sesuatu yang mengambil tempat minimum mutlak yang mungkin, yang berdiri sebagai [[teori informasi]] bawah. Jumlah dari pohon biner yang berbeda pada <math>n</math> simpul adalah <math>\mathrm{C}_{n}</math>, [[Bilangan Catalan]] ke-<math>n</math> (asumsikan kita melihat pohon dengan ''struktur'' yang identik sebagai sebuah kesamaan). Untuk besarnya <math>n</math>, ini berkisar kira-kira <math>4^{n}</math>; sehingga kita membutuhkan setidaknya kira-kira <math>\log_{2}4^{n} = 2n</math> bit untuk menyalinnya. Oleh sebab itu sebuah pohon biner ringkas hanya membutuhkan 2 bit setiap simpul.		Sebuah ''struktur data ringkas'' adalah sesuatu yang mengambil tempat minimum mutlak yang mungkin, yang berdiri sebagai [[teori informasi]] bawah. Jumlah dari pohon biner yang berbeda pada <math>n</math> simpul adalah <math>\mathrm{C}_{n}</math>, [[Bilangan Catalan]] ke-<math>n</math> (asumsikan kita melihat pohon dengan ''struktur'' yang identik sebagai sebuah kesamaan). Untuk besarnya <math>n</math>, ini berkisar kira-kira <math>4^{n}</math>; sehingga kita membutuhkan setidaknya kira-kira <math>\log_{2}4^{n} = 2n</math> bit untuk menyalinnya. Oleh sebab itu sebuah pohon biner ringkas hanya membutuhkan 2 bit setiap simpul.
Baris 118:		Baris 116:

	Sebagai contoh, dalam sebuah pohon bagian kirinya, A memiliki 6 anak {B,C,D,E,F,G}. Ini dapat diubah manjadi sebuah pohon biner bagian kanan.		Sebagai contoh, dalam sebuah pohon bagian kirinya, A memiliki 6 anak {B,C,D,E,F,G}. Ini dapat diubah manjadi sebuah pohon biner bagian kanan.


	Pohon biner dapat dianggap sebagai pohon asli yang membujur kesamping, dengan tepi kirinya yang berwarna hitam menggambarkan ''anak pertama'' dan tepi kanannya yang berwarna biru menggambarkan ''saudara selanjutnya''. Daun dari bagian kiri pohon ini dapat dituliskan dalam Lips sebagai:		Pohon biner dapat dianggap sebagai pohon asli yang membujur kesamping, dengan tepi kirinya yang berwarna hitam menggambarkan ''anak pertama'' dan tepi kanannya yang berwarna biru menggambarkan ''saudara selanjutnya''. Daun dari bagian kiri pohon ini dapat dituliskan dalam Lips sebagai:
Baris 130:		Baris 127:
	* [[Pohon biner terurut]]		* [[Pohon biner terurut]]

	== ~~Referensi~~ ==		== Sumber dan atribusi ==
	* [[Donald Knuth]]. ''The art of computer programming vol 1. Fundamental Algorithms'', Edisi Ketiga. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.3, khususnya subsections 2.3.1–2.3.2 (hal.318–348).

			Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Pohon+biner&oldid=29248703 Wikipedia bahasa Indonesia], revisi 29248703 (2026-05-19T14:06:58Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Gambar pada artikel ini bersumber dari Wikimedia Commons dan mengikuti ketentuan lisensi masing-masing berkas. Mohon gunakan konten dan media secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

			<!-- WIKI_UNISSULA_PRESENTATION_V4 -->
	~~== Sumber dan atribusi ==~~

	~~Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Pohon+biner&oldid=29248703 Wikipedia bahasa Indonesia], revisi 29248703 (2026~~-05-~~19T14:06:58Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi~~-~~BerbagiSerupa (CC BY~~-~~SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.~~

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29248703; atribusi sumber disertakan.

2026-08-23T09:43:15Z

Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29248703; atribusi sumber disertakan.

Halaman baru

Dalam [[ilmu komputer]], sebuah '''pohon biner''' ''('''binary tree''')'' adalah sebuah [[Pohon (struktur data)|pohon]] [[struktur data]] di mana setiap [[Pohon (struktur data)#Simpul (node)|simpul]] memiliki paling banyak dua [[Pohon (struktur data)|anak]]. Secara khusus anaknya dinamakan ''kiri'' dan ''kanan''. Penggunaan secara umum pohon biner adalah [[Pohon biner terurut]], yang lainnnya adalah [[heap biner]].

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.

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.

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.

== Definisi ==

=== Definisi rekursif ===
Cara lain untuk mendefinisikan pohon biner penuh adalah definisi rekursif. Sebuah pohon biner penuh adalah baik:
* 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:
* Himpunan kosong adalah pohon biner diperpanjang
* jika 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.

== Definisi untuk pohon berakar ==
* Sebuah '''panah langsung''' mengacu pada penghubung dari [[simpul ayah|ayah]] ke [[simpul anak|anak]] nya (panah di gambar dalam pohon).
* [[Pohon (struktur data)#Akar (Root nodes)|Akar]] dari pohon adalah [[Pohon (struktur data)#Simpul (nodes)|simpul]] tanpa ayah. Terdapat paling banyak satu akar dalam pohon berakar.
* Sebuah [[Pohon (struktur data)#Daun (Leaf nodes)|daun]] adalah simpul yang tidak memiliki anak.
* '''Kedalaman''' sebuah simpul n adalah panjang jalan dari akar ke simpul. Himpunan semua simpul pada kedalaman yang diberikan kadang-kadang dinamai dengan '''Tingkat''' ''('''Level''')'' dari pohon. Akar memiliki kedalaman kosong.
* '''Tinggi sebuah pohon''' adalah panjang jalan dari akar ke daun-daunnya.
* '''Saudara''' adalah simpul yang memiliki ayah yang sama
* Jika terdapat sebuah jalan dari simpul '''p''' ke simpul '''q''', di mana simpul '''p''' lebih dekat ke akar daripada '''q''', maka '''p''' adalah '''leluhur''' dari '''q''' dan '''q''' adalah '''keturunan''' '''p'''.
* '''Lebar''' dari sebuah simpul adalah jumlah keturunan termasuk simpul itu sendiri.

== Jenis pohon biner ==
* Sebuah '''pohon biner berakar''' ''('''rooted binary tree''')'' adalah sebuah [[Pohon (struktur data)|pohon]] berakar di mana setiap simpul paling banyak mempunyai dua anak
* Sebuah '''pohon biner penuh''' ''('''full binary tree''')'', atau '''pohon biner asli''' ''('''proper binary tree''')'', adalah sebuah pohon di mana setiap simpul mempunyai nol atau dua anak.
* Sebuah '''pohon biner sempurna''' ''('''perfect binary tree''')'' (atau kadang-kadang '''pohon biner lengkap''' ''('''complete binary tree''')'' adalah sebuah '''pohon biner penuh''' di mana semua ''daun'' memiliki ''kedalaman'' yang sama.
* Sebuah '''pohon biner lengkap''' ''('''complete binary tree''')'' dapat didefinisikan juga sebagai sebuah '''pohon biner penuh''' di mana semua daunnya memiliki kedalaman ''n'' atau ''n-1'' untuk beberapa ''n''. Agar sebuah pohon dapat menjadi sebuah '''pohon biner lengkap''', semua anak pada ''tingkat'' terakhir harus menempati titik terkiri secara teratur, dengan tidak ada titik yang menganggur di antara keduanya. Sebagai contoh, jika dua simpul pada tingkat terbawah masing-masing menempati sebuah titik dengan suatu titik kosong di antara keduanya, tetapi sisa simpul anaknya terhimpit tanpa titik di antaranya, maka pohon tersebut tidak dapat membentuk sebuah pohon biner lengkap karena titik kosong tersebut.
* Sebuah '''pohon biner lengkap berakar''' ''('''rooted complete binary tree''')'' dapat dikenali dengan [[magma bebas]].
* Sebuah '''pohon biner hampir lengkap''' ''('''almost complete binary tree''')'' adalah sebuah pohon diaman setiap simpul yang mempunyai anak kanan juga memiliki anak kiri. Memiliki anak kiri tidak memerlukan sebuah simpul untuk mempunyai anak kanan. Penjelasan lainnya, sebuah '''pohon biner hampir lengkap''' adalah sebuah pohon di mana untuk sebuah anak kanan, selalu terdapat anak kiri, tetapi untuk sebuah anak kiri, tidak selalu terdapat sebuah anak kanan.
* Jumlah simpul '''n''' dalam pohon biner lengkap dapat dihitung dengan menggunakan rumus: '''n = 2^(h+1)-1''' di mana '''h''' adalah tinggi dari pohon.
* Jumlah daun '''n''' dalam sebuah pohon biner lengkap dapat dihitung dengan menggunakan rumus: '''n = 2^h''' di mana '''h''' adalah tinggi dari pohon.

== Definisi dalam teori graf ==
Sebuah pohon biner adalah grafik asiklis yang terhubung di mana setiap tingkatan dari sudut tidak lebih dari 3. Ini dapat ditunjukan bahwa dalam pohon biner manapun, terdapat persis dua atau lebih simpul dengan tingkat satu daripada yang terdapat dengan tingkat tiga, tetapi bisa terdapat angka apa saja dari simpul dengan tingkat dua. Sebuah '''pohon biner berakar''' merupakan sebuah grafik yang mempunyai satu dari sudutnya dengan tingkat tidak lebih dari dua sebagai akar.

Dengan akar yang dipilih, setiap sudut akan memiliki ayah khusus, dan diatas dua anak; bagaimanapun juga, sejauh ini terdapat keterbatasan informasi untuk membedakan antara anak kiri atau kanan. Jika kita membuang keperluan yg tak terkoneksi, membolehkan bermacam koneksi dalam komponen di gafik, kita memanggil struktur sebuah [[Pohon (struktur data)#Hutan|hutan]].

Sebuah jalan lain untuk mendefinisikan pohon biner melalui definisi [[rekursif]] pada grafik langsung. Sebuah pohon biner dapat berarti:
* Sebuah sudut tunggal.
* Sebuah graf yang dibentuk dengan mengambil dua pohon biner, menambahkan sebuah sudut, dan menambahkan sebuah panah langsung dari sudut yang baru ke akar dari setiap pohon biner.
Ini juga tidak menentujan susunan anak, tetapi memperbaiki akar tertentu.

== Kombinatorik ==
Kelompok dari sepasang simpul dalam sebuah pohon dapat digambarkan sebagai pasangan dari [[huruf|aksara]] dalam tanda kurung. Oleh sebab itu, ''(a,b)'' menunjukan pohon biner di mana sub pohon kirinya adalah ''a'' sedangkan sub pohon kanannya adalah ''b''. Benang dari tanda kurung yang seimbang mungkin dapat digunakan untuk menunjukan pohon biner pada umumnya. Himpunan dari semua benang yang mungkin yang terdiri dari keseluruhan tanda kurung yang seimbang dikenal sebagal [[bahasa Dyck]].

Diketahui ''n+1'' simpul, jumlah seluruh jalan di mana simpul tersebut dapat disusun kedalam sebuah pohon biner dengan sebuah [[bilangan Catalan]] <math>C_n</math>. Sebagai contoh, <math>C_2=2</math> adalah pernyataan bahwa ''(ab)c'' dan ''a(bc)'' merupakan dua pohon biner yang mungkin, yang memiliki 3 simpul.

Kemampuan untuk menggambarkan pohon biner sebagai benang dari simbol-simbol dan tanda kurung secara tidak langsung menyatakan bahwa pohon biner dapat mewakili elemen dari [[magma (algebra)|magma]]. Sebaliknya, himpunan dari semua pohon biner yang mungkin, bersama-sama dengan operasi natural memasangkan pohon dari satu ke yang lain, dari sebuah magma, [[magma bebas]].

Memberikan benang yang menggambarkan sebuah pohon biner, operator untuk mendapatkan sub pohon kiri dan kanan kadang-kadang mengacu sebagai [[CAR dan CDR]].

== Metode untuk menyimpan pohon biner ==
Pohon biner dapat dikonstruksi dari [[bahasa pemrograman]] primitif dalam berbagai cara. Dalam bahasa yang menggunakan [[record (ilmu komputer)|records]] dan [[referensi]], pohon biner secara khas dikonstruksi dengan mengambil sebuah struktur simpul pohon yang memuat beberapa data dan referensi ke anak kiri dan anak kanan. Kadang-kadang itu juga memuat sebuah referensi ke ayahnya yang khas. Jika sebuah simpul mempunyai kurang dari dua anak, beberapa penunjuk anak dapat diatur kedalam nilai nol khusus, atau ke sebuah simpul [[sentinel]].

Pohon biner dapat juga disimpan sebagai [[struktur data implisit]] dalam [[array]], dan jika pohon tersebut merupakan sebuah pohon biner lengkap, metode ini tidak boros tempat. Dalam penyusunan yang rapat ini, jika sebuah simpul memiliki indeks ''i'', anaknya dapat ditemukan pada indeks ke-2''i''+1 dan 2''i''+2, meskipun ayahnya (jika ada) ditemukan pada indeks ''[[Fungsi lantai|lantai]]((i-1)/2)'' (asumsikan akarnya memiliki indeks kosong). Metode ini menguntungkan dari banyak penyimpanan yang rapat dan memiliki referensi lokal yang lebih baik, tersitimewa selama sebuah ''preorder traversal''. Bagaimanapun juga, ini terlalu mahal untuk perkembangannya dan boros tempat sebanding dengan 2<sup>''h''</sup> - ''n'' untuk sebuah pohon dengan tinggi ''h'' dengan ''n''simpul.

Dalam bahasa dengan ''[[tagged union]]'' seperti [[Bahasa pemrograman ML|ML]], sebuah simpul pohon sering kali sebuah ''tagged union'' dari dua jenis simpul, di mana yang satu merupakan data dari 3-tupel, anak kiri, dan anak kanan, dan yang lain di mana sebuah daun, yang tidak memuat data dan fungsi seperti nilai nol dalam bahasa dengan ''penunjuk (pointers)''

== Metode iterasi pohon biner ==
Sering kali, seseorang berkeinginan untuk mengunjungi simpul dalam pohon dan menjalankan perintahnya disana. Terdapat beberapa penyusunan umum di mana simpul-simpuk tersebut dapat dikunjungi, dan setiap simpul memiliki sifat-sifat yang berguna yang dimanfaatkan dalam algoritma yang berdasarkan pada pohon biner.

=== Pre-order, in-order, dan post-order traversal ===

Pre-order, in-order, dan post-order traversal mengunjungi setiap simpul dalam sebuah pohon dengan pengunjungan secara berulang-ulang pada sub pohon kiri dan kanan dari akarnya. Jika akarnya dikunjungi sebelum sub pohonnya, ini merupakan preoder. Jika akarnya dikunjungi sesudah sub pohonnya, ini dinamakan postorder dan jika akarnya dikunjungi di antara sub pohonnya, dinamakan inorder. In-order traversal sangat berguna dalam [[pohon biner terurut]], di mana ''traversal'' ini mengunjungi simpul dalam urutan yang meningkat.

=== Depth-first order ===
Dalam ''Depth-first order'', kita selalu berusaha sebisa mungkin untuk mengunjungi simpul terjauh dari akar, tetapi dengan peringatan bahwa itu haruslah sebuah simpul anak yang telah dikunjungi. Tidak seperti pencarian ''depth-first order'' dalam graf, tidak diperlukan untuk mengingat seluruh simpul yang telah dikunjungi, karena sebuah pohon tidak dapat memuat siklus. ''Pre-order'' merupakan kasus khusus untuk ini.

=== Breadth-first order ===
Dibandingkan dengan ''depth-first order'', ''breadth-first order'', yang selalu berusaha untuk mengnjungi simpul terdekat dengan akar yang belum dikunjunginya.

== Penyandian ==

=== Penyandian ringkas ===
Sebuah ''struktur data ringkas'' adalah sesuatu yang mengambil tempat minimum mutlak yang mungkin, yang berdiri sebagai [[teori informasi]] bawah. Jumlah dari pohon biner yang berbeda pada <math>n</math> simpul adalah <math>\mathrm{C}_{n}</math>, [[Bilangan Catalan]] ke-<math>n</math> (asumsikan kita melihat pohon dengan ''struktur'' yang identik sebagai sebuah kesamaan). Untuk besarnya <math>n</math>, ini berkisar kira-kira <math>4^{n}</math>; sehingga kita membutuhkan setidaknya kira-kira <math>\log_{2}4^{n} = 2n</math> bit untuk menyalinnya. Oleh sebab itu sebuah pohon biner ringkas hanya membutuhkan 2 bit setiap simpul.

Salah satu penggambaran sederhana yang masih berhubungan dengan ini adalah mengunjungi simpul dari pohon dengan ''preoder'', meletakkan "1" untuk sebuah simpul dalan dan "0" untuk sebuah daun. [http://theory.csail.mit.edu/classes/6.897/spring03/scribe_notes/L12/lecture12.pdf] Jika pohon ini memuat data, kita dapat menyimpanya secara serempak dalam sebuah [[array]] yang berurutan dengan ''preoder''. Fungsi ini memenuhi:

'''function''' EncodeSuccinct(''node'' n, ''bitstring'' structure, ''array'' data) {
'''if''' n = ''nil'' '''then'''
append 0 to structure;
'''else'''
append 1 to structure;
append n.data to data;
EncodeSuccinct(n.left, structure, data);
EncodeSuccinct(n.right, structure, data);
}

''String'' ''structure'' hanya memiliki <math>2n + 1</math> bit pada bagian akhir, di mana <math>n</math> adalah angka dari simpul dalam; kita bahkan tidak memerlukan untuk menyimpan panjangnya. Untuk menunjukkan bahwa tidak ada informasi yang hilang, kita dapat mengubah hasilnya kembali seperti pohon aslinya seperti ini:

'''function''' DecodeSuccinct(''bitstring'' structure, ''array'' data) {
remove first bit of ''structure'' and put it in ''b''
'''if''' b = 1 '''then'''
create a new node ''n''
remove first element of data and put it in n.data
n.left = DecodeSuccinct(structure, data)
n.right = DecodeSuccinct(structure, data)
'''return''' n
'''else'''
'''return''' nil
}

Penggambaran secara ringkas dan rumit memungkinkan tidak hanya penyimpanan yang rapi pada pohon tetapi bahkan operasi yang berguna secara langsung pada pohon tersebut, meskipun mereka masih dalam bentuk yang ringkas.

=== Penyandian pohon ''n''-er sebagai pohon biner ===
Terdapat sebuah pemetaan satu-satu antara pohon terurut general dan pohon biner, yang biasanya digunakan oleh [[Lisp (bahasa pemrograman)|Lisp]] untuk menggambarkan pohon terurut general sebagai pohon biner. Setiap simpul ''N'' dalam pohon terurut terhubung ke sebuah simpul ''N'' dalam pohon biner; anak kiri dari ''N'' merupakan simpul yang terhubung ke anak pertama dari ''N'', dan anak kanan dari ''N'' merupakan simpul yang terhubung ke saudara selanjutnya dari ''N'' yang merupakan simpul selanjutnya dalam urutan di antara anak-anaknya dari ayahnya ''N''

Suatu cara untuk menyelesaikan ini adalah bahwa setiap anak simpul berada dalam sebuah [[linked list]], dihubungkan bersama dengan bidang ''kanan'' mereka, dan simpul yang hanya memiliki sebuah petunjuk ke awalnya atau kepala dari daftar ini, melalui bidang ''kiri'' nya.

Sebagai contoh, dalam sebuah pohon bagian kirinya, A memiliki 6 anak {B,C,D,E,F,G}. Ini dapat diubah manjadi sebuah pohon biner bagian kanan.

Pohon biner dapat dianggap sebagai pohon asli yang membujur kesamping, dengan tepi kirinya yang berwarna hitam menggambarkan ''anak pertama'' dan tepi kanannya yang berwarna biru menggambarkan ''saudara selanjutnya''. Daun dari bagian kiri pohon ini dapat dituliskan dalam Lips sebagai:

:(((M N) H I) C D ((O) (P)) F (L))

yang akan diimplementasikan ke memori sebagai pohon biner kanan, tanpa huruf apapun pada simpul itu yang telah memiliki anak.

== Lihat pula ==
* [[Pohon (struktur data)]]
* [[Pohon biner terurut]]

== Referensi ==
* [[Donald Knuth]]. ''The art of computer programming vol 1. Fundamental Algorithms'', Edisi Ketiga. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.3, khususnya subsections 2.3.1–2.3.2 (hal.318–348).

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Pohon+biner&oldid=29248703 Wikipedia bahasa Indonesia], revisi 29248703 (2026-05-19T14:06:58Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.