Penjelasan terperinci tentang pokok binari struktur data JavaScript dan algoritma_Pengetahuan asas

Konsep pokok binari

Pokok Binari ialah set terhingga bagi n (n>=0) nod Set itu sama ada set kosong (pokok binari kosong), atau ia terdiri daripada nod akar dan dua pokok yang saling bercabang terdiri daripada subpokok kiri dan subpokok kanan nod akar.

Ciri-ciri pokok binari

Setiap nod mempunyai paling banyak dua subpohon, jadi tiada nod dengan darjah lebih besar daripada 2 dalam pepohon binari. Setiap nod dalam pepohon binari ialah objek, dan setiap nod data mempunyai tiga penunjuk, iaitu penunjuk kepada induk, anak kiri dan anak kanan. Setiap nod disambungkan antara satu sama lain melalui penunjuk. Hubungan antara penunjuk yang disambungkan ialah hubungan ibu bapa-anak.

Takrifan nod pokok binari

Nod pokok binari ditakrifkan seperti berikut:

Salin kod Kod adalah seperti berikut:

struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};

Lima bentuk asas pokok binari

Pokok binari kosong
Hanya ada satu nod akar
Nod akar hanya mempunyai subpokok kiri
Nod akar hanya mempunyai subpokok kanan
Nod akar mempunyai kedua-dua subpokok kiri dan kanan

Hanya terdapat dua situasi untuk pokok biasa dengan tiga nod: dua lapisan atau tiga lapisan. Tetapi kerana pokok binari perlu membezakan kiri dan kanan, ia akan berkembang menjadi lima bentuk berikut:

Pokok Binari Khas

Pokok Condong

Seperti yang ditunjukkan dalam gambar ke-2 dan ke-3 dalam gambar terakhir di atas.

Pokok Binari Penuh

Dalam pokok binari, jika semua nod cawangan meninggalkan subpokok dan subpokok kanan, dan semua daun berada pada tahap yang sama, pokok binari sedemikian dipanggil pokok binari penuh. Seperti yang ditunjukkan di bawah:

Pokok Binari Lengkap

Pokok binari yang lengkap bermakna bahagian kiri tahap terakhir penuh, bahagian kanan mungkin penuh atau tidak, dan kemudian tahap selebihnya penuh. Pokok binari dengan kedalaman k dan bilangan nod 2^k - 1 ialah pokok binari penuh (pokok binari lengkap). Ia adalah pokok dengan kedalaman k dan tiada celah.

Ciri-ciri pokok binari yang lengkap ialah:

Nod daun hanya boleh muncul pada dua peringkat bawah.

Daun yang paling rendah mesti tertumpu pada kedudukan berterusan kiri.

Pada lapisan kedua terakhir, jika terdapat nod daun, ia mesti berada dalam kedudukan berterusan di sebelah kanan.

Jika darjah nod ialah 1, maka nod itu hanya meninggalkan anak.

Pokok binari dengan pokok nod yang sama, pokok binari lengkap mempunyai kedalaman terkecil.

Nota: Pokok binari penuh mestilah pokok binari lengkap, tetapi pokok binari lengkap tidak semestinya pokok binari penuh.

Algoritma adalah seperti berikut:

Salin kod Kod adalah seperti berikut:

bool is_complete(pokok *akar)
{
beratur q;
pokok *ptr;
// Lakukan lintasan pertama keluasan (laluan tahap) dan letakkan nod NULL ke dalam baris gilir
q.push(root); Manakala ((ptr = q.pop()) != NULL)
{ 
           q.tolak(ptr->kiri); 
           q.push(ptr->kanan); 
}  
// Tentukan sama ada terdapat sebarang nod yang belum dilawati

Manakala (!q.is_empty())
{ 
ptr = q.pop();
// Jika terdapat nod bukan NULL yang tidak dilawati, pokok itu mempunyai lubang dan merupakan pokok binari yang tidak lengkap

Jika (NULL != ptr)

                                                                                                                                     pulangan palsu;                                                                                                                                                                                      }  

kembali benar;
}

Sifat pokok binari

Sifat 1 pokok binari: Terdapat paling banyak 2^(i-1) nod (i>=1) pada aras ke-i pokok binari

Sifat 2 pokok binari: Pokok binari dengan kedalaman k mempunyai paling banyak 2^k-1 nod (k>=1)

Struktur penyimpanan berjujukan pokok binari

Struktur storan berurutan bagi pokok binari menggunakan tatasusunan satu dimensi untuk menyimpan setiap nod dalam pokok binari, dan lokasi penyimpanan nod boleh mencerminkan hubungan logik antara nod.

Senarai terpaut binari

Memandangkan kebolehgunaan storan berjujukan tidak kukuh, kita mesti mempertimbangkan struktur storan rantai. Mengikut amalan antarabangsa, penyimpanan pokok binari secara amnya menggunakan struktur simpanan rantai.

Setiap nod pokok binari mempunyai paling banyak dua anak, jadi adalah idea semula jadi untuk mereka bentuk medan data dan dua medan penunjuk untuknya. Kami memanggil senarai terpaut tersebut sebagai senarai terpaut binari.

Pelintasan pokok binari

Melintasi pokok binari bermakna bermula dari nod akar dan melawat semua nod dalam pokok binari dalam susunan tertentu supaya setiap nod dilawati sekali dan hanya sekali.

Terdapat tiga cara untuk melintasi pokok binari, seperti berikut:

(1) Prapesan traversal (DLR), mula-mula lawati nod akar, kemudian lintasi subpokok kiri, dan akhirnya melintasi subpokok kanan. Singkatan akar-kiri-kanan.

(2) In-order traversal (LDR), mula-mula melintasi subpokok kiri, kemudian melawati nod akar, dan akhirnya melintasi subtree kanan. Disingkatkan sebagai kiri-akar-kanan.

(3) Postorder traversal (LRD), mula-mula melintasi sub pokok kiri, kemudian melintasi subtree kanan, dan akhirnya melawat nod akar. Disingkatkan sebagai akar kiri-kanan.

Preorder traversal:

Jika pokok binari kosong, tiada operasi kembali, jika tidak, nod akar dilawati dahulu, kemudian subpokok kiri dilalui dalam prapesanan, dan kemudian subpokok kanan dilalui dalam prapesanan.

Turutan rentas ialah: A B D H I E J C F K G

Salin kod Kod adalah seperti berikut:

//Pre-order traversal
fungsi prapesanan(nod){
Jika(!nod == null){
          putstr(node.show() " ");
          prapesan(nod.kiri);
          prapesan(node.kanan);
}
}

Perjalanan mengikut urutan:

Jika pepohon kosong, tiada operasi kembali, jika tidak bermula dari nod akar (perhatikan bahawa nod akar tidak dilawati dahulu), lalui subpokok kiri nod akar mengikut tertib, kemudian lawati nod akar, dan akhirnya Traverse subtree kanan mengikut tertib.

Turutan rentas ialah: H D I B E J A F K C G

Salin kod Kod adalah seperti berikut:

//Gunakan rekursi untuk melaksanakan traversal tertib
fungsi inOrder(nod){
Jika(!(nod ​​== null)){
inOrder(node.left);//Lawati subpokok kiri dahulu
          putstr(node.show() " ");//Lawati nod akar sekali lagi
inOrder(node.right);//Akses terakhir ke subpokok kanan
}
}

Perjalanan pasca pesanan:

Jika pokok itu kosong, operasi tanpa operasi kembali jika tidak, subpokok kiri dan kanan dilalui dari kiri ke kanan, mula-mula daun dan kemudian nod, dan akhirnya nod akar dilawati.

Turutan rentas ialah: H I D J E B K F G C A

Salin kod Kod adalah seperti berikut:

//Perjalanan pasca pesanan
fungsi postOrder(nod){
Jika(!nod == null){
PostOrder(node.left);
         postOrder(node.right);
           putStr(node.show() " ");
}
}

Laksanakan pepohon carian binari

Pokok carian binari (BST) terdiri daripada nod, jadi kami mentakrifkan objek nod Nod seperti berikut:

Salin kod Kod adalah seperti berikut:

fungsi Nod(data,kiri,kanan){
This.data = data;
This.left = left;//Simpan pautan nod kiri
This.right = right;
This.show = tunjukkan;
}

function show(){
Kembalikan this.data;//Paparkan data yang disimpan dalam nod
}

Cari nilai maksimum dan minimum

Mencari nilai minimum dan maksimum pada BST adalah sangat mudah, kerana nilai yang lebih kecil sentiasa pada nod anak kiri, untuk mencari nilai minimum pada BST, hanya melintasi subpokok kiri sehingga nod terakhir ditemui

Cari nilai minimum

Salin kod Kod adalah seperti berikut:

fungsi getMin(){
var current = this.root;
While(!(current.left == null)){
Semasa = semasa.kiri;
}
Kembalikan data semasa;
}

Kaedah ini merentasi subpokok kiri BST satu demi satu sehingga ia melintasi ke nod paling kiri BST, yang ditakrifkan sebagai:

Salin kod Kod adalah seperti berikut:

current.left = null;

Pada masa ini, nilai yang disimpan pada nod semasa ialah nilai minimum

Cari nilai maksimum

Mencari nilai maksimum pada BST hanya memerlukan merentasi subpokok kanan sehingga nod terakhir ditemui, dan nilai yang disimpan pada nod ini ialah nilai maksimum.

Salin kod Kod adalah seperti berikut:

fungsi getMax(){
var current = this.root;
Manakala(!(semasa.kanan == null)){
            semasa = semasa.kanan;
}
Kembalikan data semasa;
}