Rumah  >  Artikel  >  hujung hadapan web  >  Kuasai algoritma utama kedalaman struktur pokok JavaScript dalam satu artikel

Kuasai algoritma utama kedalaman struktur pokok JavaScript dalam satu artikel

WBOY
WBOYke hadapan
2022-07-25 17:45:082451semak imbas

Artikel ini membawakan anda pengetahuan yang berkaitan tentang javascript Ia terutamanya memperkenalkan algoritma kedalaman struktur pokok JavaScript Struktur pepohon boleh dikatakan sebagai salah satu struktur data yang paling biasa di bahagian hadapan , seperti Mari kita lihat pada pokok DOM, pemilihan lata dan komponen pokok Saya harap ia akan membantu semua orang.

Kuasai algoritma utama kedalaman struktur pokok JavaScript dalam satu artikel

[Cadangan berkaitan: tutorial video javascript, bahagian hadapan web]

Apakah itu pokok

Dalam kehidupan sebenar, saya percaya semua orang biasa dengan pokok, sama ada pokok willow, poplar atau pic Boleh dikatakan pokok boleh dilihat di mana-mana dalam kehidupan kita, pokok adalah sejenis lapisan Model abstrak struktur ,

adalah seperti yang ditunjukkan di bawah:

Terdapat banyak aplikasi struktur pokok, Sebagai contoh, struktur organisasi syarikat boleh diwakili oleh pokok, seperti yang ditunjukkan di bawah:

Selain daripada struktur organisasi, struktur pokok juga boleh digunakan seperti salasilah, wilayah dan bandar, dan lain-lain untuk menyatakan.

Istilah pokok

Terdapat banyak istilah untuk pokok, seperti yang ditunjukkan di bawah:

  • Pokok : Satu set terhingga n (n≥0) nod Apabila n=0, ia dipanggil pokok kosong;
  • nod 🎜>Bilangan subpokok
  • , sebagai contoh, darjah nod B ialah 2, dan darjah nod A ialah 3; : darjah maksimum antara semua nod pokok, Contohnya, dalam gambar di atas, darjah pokok ialah 3 nod daun :
  • Nod dengan darjah 0; juga dipanggil nod daun
  • ;
  • Nod anak
  • : seperti yang ditunjukkan di atas; >Nod akar : seperti yang ditunjukkan di atas;
  • Kedalaman pokok: Tahap maksimum semua nod dalam pokok
  • . Contohnya, kedalaman pokok dalam gambar di atas ialah 3; kedalaman
  • Tahap
  • : Sebagai contoh, tahap nod E ialah 3, tahap nod. ialah
  • nod induk tahap 1, dan tahap nod akar ialah 1; contohnya, laluan A→H ialah ;
  • Panjang laluan : dari satu nod ke satu nod Jarak , contohnya, laluan A→H ialah 3.
  • Pokok dalam JavaScriptStruktur pepohon boleh dikatakan sebagai salah satu struktur data yang paling biasa di bahagian hadapan, seperti pepohon DOM, pemilihan lata, komponen pepohon, dsb. ;JavaScript tidak menyediakan struktur data pepohon, tetapi kita boleh mensimulasikan pepohon melalui objek dan tatasusunan,
  • Sebagai contoh, kod berikut: A D H
  • Idea pelaksanaannya adalah seperti berikut:

Akses nod akar;

Teruskan traversal mendalam-pertama (rekursi)

nod akar

kod pelaksanaan adalah seperti berikut:

const tree = {
  value: 'A',
  children: [
    {
      value: 'B',
      children: [
        { value: 'E', children: null },
        { value: 'F', children: null },
      ],
    },
    {
      value: 'C',
      children: [{ value: 'G', children: null }],
    },
    {
      value: 'D',
      children: [
        { value: 'H', children: null },
        { value: 'I', children: null },
      ],
    },
  ],
}

seperti yang anda lihat, dan Rajah Susunan dalam adalah konsisten, yang bermaksud tiada masalah dengan algoritma kami.

Keluasan Didahulukan

Apa yang dipanggil keutamaan keluasan adalah untuk melawati nod yang paling hampir dengan nod akar dalam urutan urutan traversalnya adalah seperti berikut:

Idea pelaksanaan adalah seperti berikut:

  • Buat baris gilir dan tambahkan nod akar pada baris gilir; >Turunkan kepala baris gilir dan aksesnya;
  • Tambahkan yang pertama children pada baris gilir
Ulang langkah 2 dan 3 sehingga baris gilir kosong.

Kod pelaksanaan adalah seperti berikut:
function dfs(root) {
  console.log(root.value)
  root.children && root.children.forEach(dfs) // 与下面一致
  // if (root.children) {
  //   root.children.forEach(child => {
  //     dfs(child)
  //   })
  // }
}
dfs(tree) // 这个tree就是前面定义的那个树
/* 结果
A
B
E
F
C
G
D
H
I
*/

Seperti yang anda lihat, ia konsisten dengan susunan dalam gambar, yang bermaksud terdapat tiada masalah dengan algoritma kami.

[Cadangan berkaitan: tutorial video javascript,

bahagian hadapan web

]

Atas ialah kandungan terperinci Kuasai algoritma utama kedalaman struktur pokok JavaScript dalam satu artikel. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan:
Artikel ini dikembalikan pada:jb51.net. Jika ada pelanggaran, sila hubungi admin@php.cn Padam