Dalam kehidupan pemrograman, kami selalu menemukan struktur pohon. Dalam beberapa hari terakhir, kita hanya perlu mengoperasikan struktur pohon, jadi kita mencatat metode dan proses operasi kita sendiri. Sekarang misalkan ada pohon seperti ini, (tidak masalah apakah itu pohon biner atau tidak, prinsip -prinsipnya sama)
1. Prioritas kedalaman
Singkatan bahasa Inggris adalah DFS, yaitu pencarian pertama yang kedalaman.
Pencarian kedalaman-pertama adalah metode yang lebih umum digunakan pada tahap awal perayap pengembangan. Tujuannya adalah untuk mencapai node daun dari struktur yang dicari (mis. File HTML yang tidak mengandung hyperlink). Dalam file HTML, ketika hyperlink dipilih, file HTML tertaut akan melakukan pencarian kedalaman-pertama, yaitu, rantai terpisah harus dicari secara penuh sebelum mencari hasil hyperlink yang tersisa. Pencarian prioritas kedalaman mengikuti hyperlink pada file HTML sampai tidak dapat diperdalam lebih lanjut, kemudian kembali ke file HTML tertentu, dan terus memilih hyperlink lain dalam file HTML. Ketika tidak ada hyperlink lain yang tersedia, pencarian telah berakhir. Prosesnya hanya untuk masuk lebih dalam ke setiap jalur cabang yang mungkin sampai tidak dapat lebih dalam, dan setiap node hanya dapat diakses sekali. Sebagai contoh di atas, hasil traversal kedalaman-pertama adalah: A, B, D, E, I, C, F, G, H. (dengan asumsi bahwa sisi kiri simpul anak dibiarkan terlebih dahulu).
Prioritas kedalaman digunakan untuk melintasi setiap node, dan struktur data seperti tumpukan diperlukan. Karakteristik tumpukan adalah untuk keluar lebih dulu dan kemudian keluar. Seluruh proses traversal adalah sebagai berikut:
Pertama, tekan simpul A ke tumpukan, stack (a);
Pop Up Node A dan tekan node anak A dan B ke dalam tumpukan pada saat yang sama. Pada saat ini, B berada di atas tumpukan, tumpukan (B, C);
Pop Up Node B dan tekan node anak B dan D ke tumpukan. Pada saat ini, D ada di bagian atas tumpukan, tumpukan (d, e, c);
Pop up node D, tidak ada node anak yang ditekan, dan E berada di bagian atas tumpukan, tumpukan (E, C);
Pop Up Node E dan Tekan E'S Child Node I ke Stack (I, C);
... pada gilirannya, dan traversal akhir selesai. Kode Java kira -kira sebagai berikut:
public void depthFirst () {stack <map <string, object >> nodestack = new stack <peta <string, objek >> (); peta <string, objek> node = hashmap baru <string, objek> (); nodestack.add (node); while (! nodestack.isempty ()) {node = nodestack.pop (); System.out.println (node); // Dapatkan simpul anak dari node. Untuk pohon biner, ini adalah untuk mendapatkan simpul anak kiri dan simpul anak yang tepat dari daftar node <peta <string, objek >> anak -anak = getChildren (node); if (anak -anak! = Null &&! Anak -anak.isempty ()) {for (peta anak: anak -anak) {nodestack.push (anak);}}}}}}}}}} {nodestack.2. Prioritas luas
Singkatan bahasa Inggris adalah BFS, yang berarti luasnya penelitian pertama. Menurut uji proses, setiap lapisan node diakses secara bergantian, dan setelah mengakses satu lapisan, setiap node hanya dapat mengaksesnya sekali. Untuk contoh di atas, hasil traversal pertama adalah: A, B, C, D, E, F, G, H, I (dengan asumsi bahwa setiap lapisan node diakses dari kiri ke kanan).
Prioritas luas digunakan untuk melintasi setiap node, dan struktur data seperti antrian diperlukan. Karakteristik antrian adalah yang pertama, pertama, dan pada kenyataannya, ia juga dapat menggunakan antrian ganda. Perbedaannya adalah bahwa node dapat dimasukkan dan muncul pada posisi pertama antrian endapan ganda. Seluruh proses traversal adalah sebagai berikut:
Pertama masukkan simpul A ke antrian, antrian (a);
Pop Up Node A dan masukkan node anak B dan C dari A ke dalam antrian. Pada saat ini, B berada di awal antrian dan C berada di akhir antrian, antrian (B, C);
Pop Up Node B dan masukkan node anak D dan E B OF B ke dalam antrian pada saat yang sama. Pada saat ini, C berada di awal antrian dan E berada di akhir antrian, antrian (C, D, E);
Pop up node C dan masukkan node anak f, g, h dari C ke dalam antrian. Pada saat ini, D adalah kepala antrian dan H berada di akhir antrian, antrian (d, e, f, g, h);
Pop Up Node D, D tidak memiliki node anak, pada saat ini E berada di kepala antrian, h berada di ekor antrian, antrian (e, f, g, h);
... pada gilirannya, dan traversal akhir selesai. Kode Java kira -kira sebagai berikut:
public void breadfirst () {deque > nodedeque = arraydeque baru > (); Peta node = hashmap baru (); nodedeque.add (node); while (! nodedeque.isempty ()) {node = nodedeque.peekfirst (); System.out.println (node); // Dapatkan simpul anak dari simpul. Untuk pohon biner, simpul anak kiri dan simpul anak yang tepat dari simpul adalah untuk mendapatkan daftar simpul. > anak -anak = getchildren (node); if (anak -anak! = null &&! anak -anak }}}} // antrian ujung ganda digunakan di sini, yang sama dengan menggunakan antrian Meringkaskan
Di atas adalah semua konten dari artikel ini tentang contoh kode implementasi Java-pertama dan luas, dan saya harap ini akan membantu semua orang. Teman yang tertarik dapat terus merujuk ke topik terkait lainnya di situs ini. Jika ada kekurangan, silakan tinggalkan pesan untuk menunjukkannya. Terima kasih teman atas dukungan Anda untuk situs ini!