Tutorial Struktur Data Pohon untuk Pemula

pengantar

Pohon dalam perangkat lunak seperti pohon biologis, tetapi dengan perbedaan berikut:

• Itu ditarik terbalik.
• Ia hanya memiliki satu akar dan tidak memiliki batang.
• Cabang-cabang muncul dari akar.
• Sebuah titik di mana cabang lepas landas dari cabang lain atau akar disebut node.
• Setiap simpul memiliki nilai.

Cabang-cabang pohon perangkat lunak diwakili oleh garis lurus. Contoh yang baik dari pohon perangkat lunak yang mungkin Anda gunakan adalah pohon direktori dari hard disk komputer Anda.

Ada berbagai jenis pohon. Ada pohon umum dari mana pohon lain diturunkan. Pohon lain diturunkan dengan memasukkan kendala ke pohon umum general. Misalnya, Anda mungkin menginginkan pohon di mana tidak lebih dari dua cabang berasal dari sebuah simpul; pohon seperti itu akan disebut Pohon Biner.  Artikel ini menjelaskan pohon umum dan cara mengakses semua simpulnya.

Tautan untuk mengunduh kode diberikan di bagian bawah artikel ini.

Untuk memahami contoh kode dalam artikel ini, Anda harus memiliki pengetahuan dasar tentang JavaScript (ECMAScript). Jika Anda tidak memiliki pengetahuan itu, maka Anda bisa mendapatkannya dari http://www.jaringan luas.com/ChrysanthusForcha-1/ECMAScript-2015-Course.htm

Diagram Pohon Umum

'A' adalah simpul akar; itu adalah simpul tingkat pertama. B, C, D ada di baris kedua; ini adalah node tingkat kedua. E, F, G, H, I, J, K berada di baris ketiga, dan mereka adalah node tingkat ketiga. Baris keempat akan menghasilkan node tingkat keempat, dan seterusnya.

Properti Pohon

- Semua cabang untuk semua level node, memiliki satu sumber, yaitu root node.

- Sebuah pohon memiliki N - 1 cabang, di mana N adalah jumlah total node. Diagram di atas untuk pohon umum memiliki 11 node dan 10 cabang.

- Berbeda dengan manusia, di mana setiap anak memiliki dua orang tua, dengan pohon perangkat lunak, setiap anak hanya memiliki satu orang tua. Node akar adalah orang tua leluhur terbesar. Orang tua dapat memiliki lebih dari satu anak. Setiap simpul, kecuali simpul akar, adalah anak.

Kosakata Pohon

• Node Akar: Ini adalah simpul tertinggi di pohon, dan tidak memiliki induk. Setiap simpul lain memiliki orang tua.
• Node Daun: Simpul daun adalah simpul yang tidak memiliki anak. Mereka biasanya di bagian bawah pohon dan kadang-kadang di sisi kiri dan/atau kanan pohon.
• Kunci: Ini adalah nilai dari sebuah pohon. Ini bisa berupa angka; itu bisa berupa string; itu bahkan bisa menjadi operator seperti + atau - atau x.
• Level: Node root ada di level pertama. Anak-anaknya berada di tingkat kedua; Anak-anak dari simpul tingkat kedua berada di tingkat ketiga, dan seterusnya.
• Simpul Induk: Setiap simpul, kecuali simpul akar, memiliki simpul induk yang terhubung dengannya oleh cabang. Setiap simpul, kecuali simpul akar, adalah simpul anak.
• Node Saudara: Sibling node adalah node yang memiliki parent yang sama.
• Jalur: Cabang-cabang (garis lurus) yang menghubungkan satu simpul ke simpul lain, melalui simpul lain, membentuk jalur. Cabang-cabangnya mungkin atau mungkin bukan panah.
• Simpul Leluhur: Semua simpul yang lebih tinggi yang terhubung ke anak, termasuk simpul induk dan simpul akar, adalah simpul leluhur.
• Node Keturunan: Semua node yang lebih rendah terhubung ke sebuah node, sampai ke daun yang terhubung, adalah node turunan. Node yang dimaksud, bukan bagian dari node turunan. Node yang dimaksud, tidak harus node root root.
• Subpohon: Sebuah simpul ditambah semua turunannya sampai ke daun terkait, membentuk subpohon. Node awal disertakan, dan tidak harus root; jika tidak, itu akan menjadi seluruh pohon.
• Gelar: Jumlah anak yang dimiliki sebuah simpul disebut derajat simpul.

Melintasi Semua Node Pohon

Semua simpul pohon dapat diakses untuk membaca atau mengubah nilai simpul apa pun. Namun, ini tidak dilakukan secara sembarangan. Ada tiga cara untuk melakukan ini, yang semuanya melibatkan Depth-First Traversal sebagai berikut:

1) Dalam Urutan: Sederhananya, dalam skema ini, subpohon kiri dilalui terlebih dahulu; kemudian, simpul akar diakses; kemudian, subpohon kanan dilalui. Skema ini dilambangkan sebagai kiri->root->kanan. Gambar 1 ditampilkan kembali di sini untuk referensi mudah:

Dengan asumsi bahwa ada dua saudara per node; lalu kiri->root->kanan berarti, Anda mengakses node terendah dan paling kiri terlebih dahulu, lalu induk node, dan kemudian saudara kandung kanan. Bila ada lebih dari dua saudara kandung, ambil simpul pertama sebagai simpul kiri dan simpul kanan lainnya sebagai simpul kanan. Untuk pohon umum di atas, subpohon kiri bawah diakses untuk memiliki, [EBF]. Ini adalah subpohon. Induk dari subpohon ini adalah A; jadi, A selanjutnya diakses untuk memiliki [EBF]A. Selanjutnya, subpohon [GCHI] diakses untuk memiliki subpohon yang lebih besar, [[EBF]A[GCHI]]. Anda dapat melihat profil kiri->root->kanan menggambarkan dirinya sendiri. Subpohon kiri besar ini akan memiliki subpohon, [JDK] di sebelah kanannya untuk menyelesaikan traversing untuk mendapatkan, [[EBF]A[GCHI]] [JDK].

2) Pra-Pesan: Sederhananya, dalam skema ini node root diakses terlebih dahulu, kemudian subtree kiri dilalui berikutnya, dan kemudian subtree kanan dilalui. Skema ini dilambangkan sebagai root->left->right. Gambar 1 ditampilkan kembali di sini untuk referensi mudah.

Dengan asumsi bahwa ada dua saudara per node; lalu root->left->right artinya, Anda mengakses root terlebih dahulu, lalu anak langsung kiri, dan kemudian anak langsung kanan. Bila ada lebih dari dua saudara kandung, ambil simpul pertama sebagai simpul kiri dan simpul kanan lainnya sebagai simpul kanan. Anak paling kiri dari anak kiri adalah yang selanjutnya diakses. Untuk pohon umum di atas, subpohon akarnya adalah [ABCD]. Di sebelah kiri subpohon ini, Anda memiliki subpohon, [EF], memberikan urutan akses, [ABCD][EF]. Di sebelah kanan subpohon yang lebih besar ini, Anda memiliki dua subpohon, [GHI] dan [JK], memberikan urutan lengkapnya, [ABCD][EF][GHI][JK]. Anda dapat melihat profil root->kiri->kanan menggambarkan dirinya sendiri.

3) Post-Order: Sederhananya, dalam skema ini, subtree kiri dilalui terlebih dahulu, kemudian subtree kanan dilalui, dan kemudian root diakses. Skema ini disimbolkan sebagai kiri->kanan->root. Gambar 1 ditampilkan kembali di sini untuk referensi mudah.

Untuk pohon ini subpohonnya adalah, [EFB], [GHIC], [JKD] dan [A] yang membentuk barisan, [EFB], [GHIC], [JKD][A]. Anda dapat melihat profil root kiri->kanan->menggambarkan dirinya sendiri.

Menciptakan Pohon

Pohon di atas akan dibuat menggunakan ECMAScript, yang seperti JavaScript versi terbaru. Setiap node adalah array. Elemen pertama dari setiap node array adalah induk dari node, array lain. Elemen node lainnya adalah anak-anak dari node, dimulai dari anak paling kiri. Ada peta ECMAScript yang menghubungkan setiap array dengan string (huruf) yang sesuai. Segmen kode pertama adalah: