Dalam tutorial ini, anda akan belajar mengenai struktur data pokok. Anda juga akan belajar mengenai pelbagai jenis pokok dan istilah yang digunakan dalam pokok.
Pokok adalah struktur data hierarki tidak linier yang terdiri daripada nod yang dihubungkan oleh tepi.
Pokok
Mengapa Struktur Data Pokok?
Struktur data lain seperti tatasusunan, senarai terpaut, timbunan, dan barisan adalah struktur data linear yang menyimpan data secara berurutan. Untuk melakukan operasi dalam struktur data linier, kerumitan waktu meningkat dengan peningkatan ukuran data. Tetapi, ia tidak dapat diterima dalam dunia komputasi masa kini.
Struktur data pokok yang berbeza memungkinkan akses yang lebih cepat dan lebih mudah ke data kerana struktur data tidak linear.
Terminologi Pokok
Node
Node adalah entiti yang mengandungi kunci atau nilai dan menunjuk ke nod turunannya.
Nod terakhir dari setiap jalur disebut simpul daun atau nod luaran yang tidak mengandungi pautan / penunjuk ke nod anak.
Node yang mempunyai sekurang-kurangnya simpul anak disebut nod dalaman .
Hujung
Ini adalah penghubung antara mana-mana dua nod.
Nod dan tepi pokok
Akar
Ia adalah simpul pokok paling atas.
Ketinggian Node
Ketinggian nod adalah bilangan tepi dari simpul ke daun paling dalam (iaitu jalan terpanjang dari simpul ke simpul daun).
Kedalaman Node
Kedalaman nod adalah bilangan tepi dari akar ke nod.
Tinggi Pokok
Ketinggian Pokok adalah ketinggian simpul akar atau kedalaman simpul paling dalam.
Tinggi dan kedalaman setiap nod di pokok
Darjah Node
Tahap nod adalah jumlah cabang nod tersebut.
Hutan
Kumpulan pokok terasing disebut hutan.
Membuat hutan dari pokok
Anda boleh membuat hutan dengan memotong akar pokok.
Jenis Pokok
- Pokok Perduaan
- Pokok Carian Binari
- Pokok AVL
- B-Pokok
Melintasi Pokok
Untuk melakukan operasi pada pokok, anda perlu mencapai nod tertentu. Algoritma traversal pokok membantu dalam meninjau nod yang diperlukan di pokok.
Untuk mengetahui lebih lanjut, sila lawati melintasi pokok.
Aplikasi Pokok
- Binary Search Pohon (BST) digunakan untuk memeriksa dengan cepat sama ada unsur terdapat dalam satu set atau tidak.
- Heap adalah sejenis pokok yang digunakan untuk jenis timbunan.
- Versi pokok yang diubahsuai yang disebut Tries digunakan dalam penghala moden untuk menyimpan maklumat penghalaan.
- Pangkalan data yang paling popular menggunakan B-Trees dan T-Trees, yang merupakan varian struktur pokok yang kami pelajari di atas untuk menyimpan data mereka
- Penyusun menggunakan pokok sintaks untuk mengesahkan sintaks setiap program yang anda tulis.
