Ketahui tentang pokok dan pokok binari dalam masa tiga minit

Dalam medan komputer, [folder] yang kami uruskan setiap hari dan data yang kami simpan dalam pangkalan data adalah semua aplikasi tipikal pokok. Hari ini kita akan belajar tentang definisi yang lebih teoritis bagi pokok dan pokok binari serta beberapa sifat dan cirinya.

Pokok

Daripada contoh di atas dalam kehidupan sebenar, kita dapat melihat bahawa struktur pokok boleh meringkaskan beberapa cirinya.

Pokok ialah set terhingga nod N (N>0) Ia sama ada pokok kosong (N=0) atau pokok tidak kosong T.

Dalam definisi ini, kita perlu menjelaskan dua isu: Pertama, pokok mesti mempunyai nod, dan kedua, mengikut bilangan nod, ia boleh dibahagikan kepada dua jenis: pokok kosong dan pokok tidak kosong . Tetapi ini hanyalah definisi paling asas, ia mempunyai beberapa sifat.

Hanya terdapat satu nod yang dipanggil akar.

Dengan kata lain, pokok ini mesti mengembang dari nod tertentu, iaitu seperti akar pokok. Darinya mula bercabang ke luar.

Kecuali nod akar, nod yang selebihnya boleh dibahagikan kepada m ( m > 0 ) set terhingga terputus T1, T2..., Tm, setiap satunya ialah pokok sendiri, dan Subtree dipanggil akar (SubTree)

Perenggan ini mungkin tidak mudah difahami Sebenarnya, secara terang-terangan, setiap nod hanya mempunyai satu nod unggul dan tidak boleh mempunyai berbilang nod superior. Dengan cara yang sama, tidak boleh ada sebarang sambungan antara nod mendatar, tetapi ia boleh mempunyai berbilang nod bawahan.

Mengenai definisi pokok, kita boleh lihat gambar di bawah.

Gambar di atas hanya menyenaraikan rupa pokok standard dan bukan pokok standard. Antaranya:

• (a) ialah pokok dengan hanya satu nod akar Selagi ada satu nod, ia boleh dipanggil struktur pokok

• (b) ialah struktur pokok standard

• (c) Perhatikan bahawa terdapat garis penghubung antara nod C dan Hnya hanya boleh dipanggil pokok jika ia mempunyai satu nod unggul ini sebenarnya [gambar] yang akan kita pelajari pada masa hadapan

Istilah berkaitan pokok

Berbanding dengan menolak (menolak) dan memunculkan tindanan, dan bergilir dan menyah gilir, syarat pokok yang berkaitan adalah jauh lebih rumit. Apa-apa pun, anda perlu mengingati istilah-istilah ini terlebih dahulu, jika tidak, istilah yang digunakan dalam perkara yang akan dibincangkan kemudian akan membuat anda lebih keliru. Tetapi tidak mengapa jika kita tidak dapat mengingatinya buat masa ini.

• Nod: Nod mungkin mengandungi set data, atau cawangan yang menunjuk ke nod lain, yang boleh dianggap sebagai tempat cawangan (b) A, B, C, D, E, dsb. Ini ialah darjah nod

• : bilangan subpohon yang dimiliki oleh nod dipanggil darjah nod, yang sebenarnya adalah subordinatnya bilangan nod anak ialah darjah Dalam rajah (b), darjah nod C ialah 1 dan darjah nod D ialah 3

• Dasar pokok: darjah. bagi setiap nod dalam pokok Nilai maksimum darjah nod ialah darjah dengan nod anak terbanyak, iaitu darjah pokok dalam rajah ialah 3

• Daun: Darjah A nod ialah 0, iaitu, nod tanpa anak nod (b) K, L, F, G, M, I, J dalam rajah ialah nod daun pokok ini

Ibu bapa dan anak-anak: Nod anak bagi nod ialah anak-anaknya, untuk nod anak ini, nod semasa ialah ibu bapanya (b) Dalam rajah, anak kepada D ialah H , I, J, dan ibu bapa H, I, J ialah D
Tahap: mengira dari nod akar, nod akar ialah tahap pertama, dan anak akar ialah tahap kedua lapisan, dan seterusnya, (b) tahap nod G dalam gambar ialah 3, (a) semua tahap gambar hanyalah 1
Kedalaman (ketinggian) pokok: pada masa ini ini Tahap maksimum pokok, jelas sekali, (b) kedalaman graf ialah 4
Saudara, nenek moyang dan keturunan: nod saudara ialah ibu bapa kepada nod ini ialah nod yang sama; nod Ancestor ialah semua nod yang melalui dalam perjalanan dari nod akar ke nod yang ditentukan adalah semua nod dalam perjalanan dari nod tertentu ke nod sasaran. (b) Dalam gambar, E dan F ialah adik beradik, nenek moyang E ialah A dan B, dan keturunan E ialah K atau L
sepupu: semua pada tahap yang sama Nod dengan ibu bapa yang berbeza adalah sepupu. Juga dalam Rajah (b), sepupu G ialah E dan F. Selain itu, H, I, dan J juga sepupunya

Binari Pokok

Setelah mempunyai pemahaman tertentu tentang konsep pokok, kita akan mempelajari lagi konsep lain, juga dalam struktur data dan algoritma Bentuk pokok yang paling penting: pokok binari.

Secara umumnya, bentuk pokok boleh berubah-ubah Contohnya, satu nod mungkin mempunyai 3 nod anak, manakala nod lain mungkin mempunyai 300 nod anak. Pokok sedemikian tanpa sebarang peraturan sebenarnya akan menjadi sangat menyusahkan untuk dikendalikan, dan definisi pokok binari adalah lebih mudah Selain sifat pokok, ia juga mempunyai satu lagi kandungan: setiap nod pokok binari mempunyai paling banyak dua nod anak, iaitu, darjah keseluruhan pokok binari mestilah 2, dan darjah semua nod tidak akan melebihi 2. Mengenai mengapa pokok binari mudah dikendalikan, kami akan menerangkan secara terperinci sifat-sifat pokok binari dalam bahagian seterusnya. Semua struktur pokok boleh ditukar menjadi pokok binari melalui ubah bentuk biasa tertentu.

Kami juga menggunakan gambar rajah untuk menunjukkan apa itu pokok binari.

Dalam pokok binari, nod anak kiri dan keturunannya boleh dianggap sebagai subpokok kiri nod semasa. Nod kanan dan nod turunannya juga boleh dianggap sebagai subpokok kanan nod semasa. Menurut nod anak nod, terdapat beberapa bentuk pokok binari seperti yang ditunjukkan dalam rajah di atas.

• (a) Pokok ialah pokok dengan hanya satu nod Ia juga boleh dikatakan sebagai pokok binari dengan hanya satu nod

• (b ) Pokok itu ialah pokok binari dengan hanya satu nod kiri

• (c) Pokok itu ialah pokok binari dengan hanya satu nod kanan

• (d ) pokok ialah pokok binari dengan dua nod kiri dan kanan

Sifat pokok binari

Harta 1: Pada aras ke-i pokok binari Terdapat paling banyak 2i-1 nod (i >= 1)

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

Sifat 3: Untuk mana-mana pokok binari T, jika bilangan nod terminal ialah n0 dan bilangan nod dengan darjah 2 ialah n2, maka n0 = n2 1

Sifat 4: Pokok binari lengkap dengan n nod Kedalaman ialah log2n 1

Sifat 5: Jika nod pokok binari lengkap dengan n nod (kedalamannya ialah log2n 1) dinomborkan dalam susunan lapisan (daripada peringkat 1 ke peringkat log2n 1 , setiap lapisan dari kiri ke kanan), kemudian untuk mana-mana nod i (1

1. Jika i = 1, maka nod i ialah akar pokok binari dan tidak mempunyai ibu bapa jika i > tiada anak kiri (nod ​​i ialah titik nod daun); jika tidak, anak kirinya ialah nod 2i
2. Jika 2i 1 > 1
3. Kami tidak akan menjelaskan secara terperinci tentang bukti matematik bagi lima sifat pokok binari di atas Lagipun, tujuan siri artikel ini adalah untuk membolehkan semua orang mempelajari intipati struktur data dan algoritma melalui contoh mudah, dan bukannya menggunakannya secara langsung dan secara kasar, formula matematik digunakan untuk mendapatkan bukti, maka kita boleh mengiranya terus pada gambar.

Untuk hartanah 1, mengikut formula, pokok binari semasa kami hanya boleh mempunyai maksimum 23-1 nod pada tahap ketiga, itu ialah, 4 nod. Hanya boleh ada paling banyak 24-1 pada lapisan ke-4, iaitu 23 = 8 nod
Untuk sifat 2, kedalaman pokok dalam gambar semasa ialah 4, yang Iaitu, terdapat paling banyak 24 - 1 = 15 nod
Untuk sifat 3, kita mula-mula mengira bilangan nod dengan darjah 2. Dalam rajah ini, nod dengan darjah 2 Terdapat 7 titik, iaitu A, B, C, D, E, F, G. Nod pada tahap keempat tidak mempunyai nod anak, iaitu semuanya 0 darjah, juga dipanggil titik terminal (daun nod), jumlah bilangan nod ini ialah 8. Sekarang n2 = 7, mengikut formula sifat kita boleh dapatkan n0 = n2 1 = 7 1 = 8
Bilangan nod dalam graf ialah 15, dan menggunakan formula sifat 4 kita boleh dapatkan Daripada log2n 1 = log215 1 = 3.91 (bulat ke bawah) 1 = 3 1 = 4, kedalaman pokok semasa ialah 4. Harta 4 dan harta 2 boleh dianggap sebagai pelengkap
Untuk hartanah 5, sila beri perhatian kepada nombor di tepi setiap nod Kami akan memilih nod E sebagai contoh. Nod E pada masa ini ialah 5, jadi ibu bapanya ialah 5 / 2 = 2 (dibundarkan ke bawah); anak kiri E ialah 2i, iaitu 2*5=10, dan anak kanan E ialah 2i 1, iaitu 2 *5 1 = 11; Takrifan harta 5 adalah lebih abstrak, dan ia menggunakan nod daun untuk menggambarkan, yang ditujukan kepada keseluruhan pokok binari, tetapi sebenarnya maksudnya adalah sama seperti yang kami jelaskan di sini, anda boleh Mengesahkannya dengan nod lain. Harta 5 sangat penting untuk penggunaan struktur berjujukan untuk menyimpan pokok binari yang akan kita bincangkan nanti!
Sila pastikan untuk menguasai dan mengingati lima sifat pokok binari ini dan maknanya, kerana dalam kajian seterusnya, sama ada susunan pokok binari, struktur simpanan rantai, atau lintasan pokok binari , berkemungkinan terdedah kepada kandungan lima sifat di atas. Ia boleh dikatakan bahawa mereka adalah jiwa yang paling asas dalam pembelajaran pokok binari.

Hutan

Akhir sekali, mari kita fahami secara ringkas apa itu "hutan". Pelbagai pokok disatukan membentuk "hutan". Sama seperti gambarajah penjelasan pokok binari di atas, (a) (b) (c) (d) disatukan dan dilihat secara keseluruhan, ia adalah "hutan", dan dalam "hutan" ini terdapat (a) (b) (c) (d) empat pokok ini.

Tiada kaitan antara pokok-pokok di dalam hutan Jika kita ingin beroperasi atau meredah hutan, kita sering menukar hutan menjadi pokok. Algoritma dan langkah khusus bukanlah fokus kajian kami, jadi semua orang boleh memahaminya. Pelajar yang ingin belajar secara mendalam boleh mencari kandungan yang berkaitan atau merujuk buku teks yang berkaitan.

Ringkasan

Dari susunan dan barisan ke belakang pokok, adakah anda tiba-tiba merasakan bahawa anda telah mengambil langkah besar? Sedikit keliru? Tidak mengapa, kandungan hari ini sebenarnya adalah beberapa kandungan teori yang asas Jika anda boleh memahaminya, fahaminya.

Pembelajaran tidak melibatkan pengulangan proses kemajuan Sudah tentu, semuanya mesti berdasarkan asas. Selepas anda memahami struktur data pokok dan beberapa algoritma traversal yang mudah, kembali untuk memahami konsep ini secara mendalam dan menghafalnya.

Pembelajaran yang disyorkan: tutorial video php

Atas ialah kandungan terperinci Ketahui tentang pokok dan pokok binari dalam masa tiga minit. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!