Berbagi teknologi

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Artikel ini akan dimulai dengan konsep terkait pohon dan pohon biner untuk membantu kita mempelajari lebih lanjut tentang pohon biner.

🌈个人主页：Itu pelayannya
🌈C语言笔记专栏：Catatan bahasa C
🌈C++笔记专栏： Catatan C++
🌈初阶数据结构笔记专栏： Catatan struktur data dasar

🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅

1. Konsep dan struktur pohon

Pohon adalah struktur data non-linier yang terdiri darin(n>=0)Node terbatas membentuk suatu himpunan dengan hubungan hierarkis. Namun, pohon tersebut bernilai kecil dalam praktiknya, namun pohon biner memiliki nilai praktis yang lebih besar (alasan mengapa himpunan ini disebut pohon adalah karena akarnya menghadap ke atas dan daunnya menghadap ke atas. menghadap ke bawah. Kelihatannya seperti pohon)

• Ada node khusus yang disebut root node. Root node tidak memiliki node pendahulunya.
• Kecuali node root, node yang tersisa dibagi menjadiM(M>0)himpunan yang terputus-putusT1、T2、....、Tm, yang masing-masing setnyaTi(1<=i<=m) Ini adalah subpohon lain dengan struktur yang mirip dengan pohon. Node akar dari setiap subpohon mempunyai satu dan hanya satu pendahulu, dan dapat mempunyai 0 atau lebih penerus.
• Pohon didefinisikan secara rekursif, dan pada saat yang sama perlu dilakukan kehati-hatian.dalam struktur pohonTidak boleh ada perpotongan antar subpohon, jika tidak maka tidak akan menjadi struktur pohon

1.1 Konsep terkait pohon

• Derajat simpul: Banyaknya subpohon yang terdapat dalam suatu simpul disebut derajat simpul; seperti terlihat pada gambar di atas: A adalah 6
• Simpul daun atau simpul terminal: Node yang berderajat 0 disebut node daun; Seperti terlihat pada gambar di atas: Node seperti B, C, H, I... adalah node daun.
• Node non-terminal atau node cabang: Simpul yang derajatnya bukan 0; Seperti yang ditunjukkan pada gambar di atas: simpul seperti D, E, F, G... adalah simpul cabang.
• Node induk atau simpul induk: Jika suatu node berisi node anak, maka node tersebut disebut node induk dari node turunannya. Seperti terlihat pada gambar di atas: A adalah node induk dari B
• simpul anak atau simpul anak: Node akar dari subpohon yang ditampung oleh sebuah node disebut node anak dari node tersebut; Seperti yang ditunjukkan pada gambar di atas: B adalah node anak dari A
• Node saudara: Node dengan node induk yang sama disebut node saudara; seperti yang ditunjukkan di atas: B dan C adalah node saudara.
• derajat pohon: Dalam sebuah pohon, derajat simpul terbesar disebut derajat pohon; seperti gambar di atas: derajat pohon adalah 6
• tingkat simpul: Mulai dari definisi root, root level pertama, node anak dari root level kedua, dan seterusnya.
• tinggi atau kedalaman pohon: Level maksimum node di pohon; seperti yang ditunjukkan di atas: tinggi pohon adalah 4
• simpul sepupu: Node-node yang orang tuanya berada pada level yang sama adalah sepupu satu sama lain; seperti yang ditunjukkan pada gambar di atas: H dan I adalah node saudara satu sama lain.
• Nenek moyang simpul: Semua node pada cabang dari akar hingga node; seperti yang ditunjukkan pada gambar di atas: A adalah nenek moyang dari semua node
• keturunan : Setiap node dalam subpohon yang berakar pada node tertentu disebut turunan dari node tersebut.Seperti yang ditunjukkan di atas: semua node adalah keturunan A
• hutan: Himpunan m (m>0) pohon yang saling lepas disebut hutan.

2. Representasi penyimpanan pohon

Karena struktur pohon lebih kompleks daripada tabel linier, metode penyimpanannya lebih merepotkan. Hal ini diperlukan untuk menyimpan rentang nilai dan hubungan antar node.

Berikut beberapa metode berdasarkan pengetahuan sebelumnya:

• Setiap anak memiliki alamat dan dapat menyimpan data melalui array penunjuk (ruangnya tetap, dan ada masalah biaya dan ruang saat mengajukan permohonan ruang baru)
• Untuk optimasi metode pertama, array pointer digunakan sebagai tabel urutan untuk menyimpan anak-anak, yang memecahkan masalah ruang tetap.
• Solusi yang disarankan yang umum digunakan: metode saudara kiri dan saudara kanan (saudara sulung mengambil anak kedua, dan anak kedua mengambil anak ketiga, sehingga kedua orang tua tidak perlu capek-capek)

typedef int DataType;
struct Node
{
    struct Node* _firstChild1; // 第一个孩子结点
    struct Node* _pNextBrother; // 指向其下一个兄弟结点
    DataType _data; // 结点中的数据域
};
1
2
3
4
5
6
7

Tentu saja cara-cara di atas tidak terbatas, ada juga ekspresi orang tua, ekspresi anak, ekspresi orang tua anak, ekspresi saudara anak, dll.Di sini kita akan memahami secara singkat yang paling umum digunakanrepresentasi saudara laki-laki

3. Konsep pohon biner

Pohon biner adalah himpunan simpul yang berhingga. Himpunan ini mungkin mempunyai dua situasi:

1. pohon kosong
2. Terdiri dari sebuah simpul akar ditambah dua pohon biner yang disebut subpohon kiri dan subpohon kanan (subpohon tersebut dapat berupa pohon kosong)

Dua kesimpulan dapat diambil dari gambar tersebut:

1. Tidak ada simpul dengan derajat lebih besar dari 2 dalam pohon biner

2. Subpohon dari pohon biner dapat dibagi menjadi subpohon kiri dan kanan, dan urutannya tidak dapat dibalik, sehingga pohon biner adalah pohon terurut.

Melihat: Untuk pohon biner apa pun, ia terdiri dari situasi berikut (Situasi pohon kosong paling mudah untuk dilupakan)

3.1 Pohon biner di dunia nyata (Anda harus membungkuk beberapa kali saat melihatnya)

4. Pohon biner khusus

• pohon biner penuh :Pohon biner adalah pohon biner penuh jika jumlah node di setiap lapisan mencapai maksimum. Dengan kata lain, level pohon biner adalah K, dan jumlah node adalah 2^{Bahasa Inggris: K}-1, maka itu adalah pohon biner penuh
• pohon biner lengkap : Pohon biner lengkap adalah struktur data yang sangat efisien. Pohon biner lengkap diturunkan dari pohon biner penuh. Untuk pohon biner dengan tinggi K dan n simpul, disebut pohon biner lengkap jika dan hanya jika setiap simpul berkorespondensi satu-ke-satu dengan simpul-simpul yang diberi nomor dari 1 hingga n pada pohon biner lengkap dengan tinggi K.

Untuk meringkas secara singkat:

• Setiap level pohon biner penuh sudah penuh

• Jika tinggi pohon biner lengkap adalah n, maka level n-1 pertama sudah penuh, namun level terakhir mungkin belum penuh.Tapi itu harus terus menerus dari kiri ke kanan

• Pohon biner lengkap adalah struktur data yang sangat efisien, dan pohon biner penuh adalah tipe khusus pohon biner lengkap.

• Pohon biner penuh merupakan syarat perlu dan cukup untuk pohon biner lengkap

4.1 Situasi yang tidak termasuk dalam pohon biner lengkap

Ini adalah pohon biner biasa, yang tidak kontinu dari kiri ke kanan.

5. Struktur penyimpanan pohon biner

Pohon biner umumnya dapat disimpan dalam dua struktur, satu adalah struktur berurutan dan yang lainnya adalah struktur rantai.

5.1 Penyimpanan berurutan

Penyimpanan struktur berurutan adalah menggunakan array untuk menyimpan,Umumnya, array hanya cocok untuk merepresentasikan pohon biner lengkap. , karena jika pohon biner tidak penuh, maka akan terjadi pemborosan ruang. Pada kenyataannya, hanya heap yang akan menggunakan array untuk penyimpanan. Penyimpanan sekuensial pohon biner secara fisik adalah array dan secara logis merupakan pohon biner. Untuk menyelesaikan pertanyaan berikutnya, kita perlu menggunakan kombinasi array fisik dan pohon biner logis untuk menyelesaikan pertanyaan.

5.2 Hubungan subskrip reguler antara node induk dan anak (penting)

• leftchild = parent * 2 + 1;

• rightchild = paretn * 2 +2;

• parent = (child - 1) / 2;(Tidak membedakan anak kiri dan kanan)

• Mengenai poin ketiga, berdasarkan alasan pribadi,leftchildSubskrip dibagi menjadileftchild- 1Dan1,untukleftchild-1untukparentberlangganan dua kali, untuk(child - 1) / 2Operator akan melakukannyaleftchildKeluarkan sebagai1Dibagi sebagian dengan 2, bilangan bulatnya adalah 0,leftchild -1Sebagiannya dapat dilihat sebagaileftchild,Danrightchild与leftchild相差1,Karenarightchild = leftchild - 1dan melalui atasleftchild - 1 ~= leftchild, dapat disimpulkan bahwarightchild = leftchild(在进行/2运算，取整数情况下)

5.3 Penyimpanan rantai

Struktur penyimpanan tertaut dari pohon biner mengacu pada penggunaan daftar tertaut untuk mewakili pohon biner, yaitu menggunakan rantai untuk menunjukkan hubungan logis elemen. Metode yang biasa dilakukan adalah setiap node dalam daftar tertaut terdiri dari tiga bidang, yaitu bidang data dan bidang penunjuk kiri dan kanan. Penunjuk kiri dan kanan digunakan untuk memberikan alamat penyimpanan titik tautan di mana anak kiri dan anak kanan dari node tersebut terletak masing-masing.Struktur rantai dibagi menjadi rantai biner dan rantai bercabang tiga. Saat ini, kita biasanya menggunakan rantai biner dalam penelitian kita. Nanti, ketika kita mempelajari struktur data tingkat tinggi seperti pohon merah-hitam, rantai bercabang tiga akan digunakan.

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
        struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
    struct BinTreeNode* _pParent; // 指向当前节点的双亲
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5.4 Ringkasan

Penyimpanan struktur berurutan disimpan melalui array.Umumnya, array hanya cocok untuk pohon biner lengkap. Pohon biner tidak lengkap tidak cocok untuk penyimpanan struktur array. . Namun kenyataannya, array hanya digunakan untuk penyimpanan ketika heap digunakan, dan sebagian besar disimpan melalui struktur rantai.

alasannya adalah:

1. Pertama-tama, kita perlu mengetahui bahwa pohon biner memiliki struktur logis tersendiri yang berbeda dari struktur data lainnya dan cocok untuk menambah, menghapus, memeriksa, dan memodifikasi data heap, karena memakan banyak ruang dan logika. lebih kompleks.Jika struktur kompleks seperti itu digunakan untuk menyimpan data, hal ini bukannya tanpa banyak manfaat. , akan lebih baik menggunakan tabel berurutan untuk menyimpan data dari awal. Pada saat yang sama, secara umum, struktur pohon biner bersifat rekursif, dan akan lebih sulit untuk mengimplementasikannya secara non-rekursif.
2. Kepadatan elemen penyimpanan dalam pohon biner biasa mungkin sangat rendah, dan struktur penyimpanan yang berkelanjutan akan menyebabkan banyak ruang yang terbuang.
3. Heap diurutkan berdasarkan "atribut heap", yang menentukan posisi node di pohon (dijelaskan dalam pengenalan heap di bawah)

---

Di atas adalah seluruh isi artikel ini. Terima kasih semuanya telah membaca! Berikut catatan Dian Xiaoer tentang struktur data dasar, semoga dapat membantu Anda dalam mempelajari struktur data dasar!