Kuasai algoritma depth-first struktur pohon JavaScript dalam satu artikel

Apa itu pohon?

Dalam kehidupan nyata, saya yakin semua orang pasti mengenal pohon. Baik itu pohon willow, pohon poplar, atau pohon persik, dapat dikatakan bahwa pohon dapat dilihat di mana saja dalam kehidupan kita, pohon adalah sebuah abstraksi dari struktur hierarki ,

seperti yang ditunjukkan di bawah ini:

Ada banyak penerapan struktur pohon. Misalnya, struktur organisasi suatu perusahaan dapat direpresentasikan dengan pohon, seperti yang ditunjukkan di bawah ini:

Selain struktur organisasi, hal-hal seperti silsilah keluarga, provinsi dan kota, dll. dapat direpresentasikan menggunakan struktur pohon.

Terminologi pohon

Ada banyak istilah untuk pohon, seperti yang ditunjukkan di bawah ini:

• Pohon : himpunan berhingga yang terdiri dari n (n≥0) simpul. Jika n=0 , maka disebut pohon kosong;
• derajat simpul : jumlah subpohon dari suatu simpul derajat simpul A adalah 3;
• derajat pohon : derajat maksimum di antara semua simpul pada pohon. Misalnya, pada gambar di atas, derajat simpul
• daun adalah
3;
• , disebut juga simpul daun ;
• simpul anak : seperti yang ditunjukkan pada gambar di atas;
• simpul saudara :
• Seperti yang ditunjukkan pada gambar di atas; simpul akar : seperti yang ditunjukkan pada gambar di atas
• kedalaman pohon : tingkat maksimum di antara semua simpul di pohon, misalnya kedalaman pohon pada gambar di atas adalah 3;
• level node : misalnya level node E adalah 3, dan level node adalah level Node induk + 1, level node akar adalah 1 ;
• jalur : saluran dari satu node ke node lain , misalnya jalur A→H adalah ADH ;
• panjang jalur : jarak dari satu node ke node lain , misalnya jalur A→H Itu 3.

Struktur pohon dalam JavaScript

dapat dikatakan sebagai salah satu struktur data yang paling umum di front-end, seperti pohon DOM, pemilihan berjenjang, komponen pohon, dll.

JavaScript tidak menyediakan struktur data pohon, namun dapat kita gunakan objek dan Array untuk mensimulasikan pohon,

seperti kode berikut:

const tree = {
  nilai: 'A',
  anak-anak: [
    {
      nilai: 'B',
      anak-anak: [
        { nilai: 'E', anak: null },
        { nilai: 'F', anak: null },
      ],
    },
    {
      nilai: 'C',
      anak: [{ nilai: 'G', anak: null }],
    },
    {
      nilai: 'D',
      anak-anak: [
        { nilai: 'H', anak: null },
        { nilai: 'Saya', anak: null },
      ],
    },
  ],
}

Keuntungan dari algoritma penjelajahan luas dan kedalaman

Depth-first

Yang disebut algoritma penjelajahan kedalaman-pertama adalah mencari cabang-cabang pohon sedalam mungkin. Urutan traversalnya adalah sebagai berikut:

Ide implementasinya adalah sebagai berikut:

• kunjungi node root;
• lanjutkan traversal kedalaman-pertama (rekursi) dari children dari node root;

kode implementasinya adalah sebagai berikut:

function dfs(root) {
  konsol.log(root.nilai)
  root.children && root.children.forEach(dfs) // Konsisten dengan yang berikut // if (root.children) {
  // root.children.forEach(anak => {
  //dfs(anak)
  // })
  // }
}
dfs(pohon) //Pohon ini adalah pohon yang didefinisikan sebelumnya/* Hasil A
B
E
F
C
G
D
H
SAYA
*/

Seperti yang Anda lihat, urutannya sesuai dengan gambar, artinya tidak ada masalah dengan algoritma kami.

Prioritas luas

Yang disebut prioritas luas adalah mengunjungi node yang paling dekat dengan node akar secara berurutan. Urutan traversalnya adalah sebagai berikut:

Ide implementasinya adalah sebagai berikut:

• Buat antrian, tambahkan simpul akar ke antrian;
• dequeue kepala antrian dan aksesnya,
• tambahkan
• children dari kepala antrian ke antrian secara berurutan;
• antriannya kosong.

Kode implementasinya adalah sebagai berikut:

function bfs(root) {
  // 1. Buat antrian baru dan tambahkan node ke antrian const q = [root]
  // 4 Ulangi sambil (q.length > 0) {
    const node = q.shift() // 2 kepala antrian di-dequeued console.log(node.value)
    // 3 anak, ketua tim, ditambahkan ke node tim.children &&
      node.children.forEach(anak => {
        q.push(anak)
      })
  }
}
bfs(pohon)
/* Hasil A
B
C
D
E
F
G
H
SAYA
*/

Seperti yang Anda lihat, urutannya sesuai dengan gambar, artinya tidak ada masalah dengan algoritma kami.