[Powered by Google Translate] [Seksyen 7] [Kurang Selesa] [Nate Hardison] [Universiti Harvard] [Ini adalah CS50.] [CS50.TV] 

Selamat datang ke Seksyen 7. Terima kasih kepada taufan Sandy, bukannya mempunyai seksyen biasa minggu ini, kita lakukan ini berjalan-melalui, melalui seksyen soalan. Saya akan mengikuti bersama-sama dengan Masalah Set 6 Spesifikasi, dan pergi melalui semua soalan dalam Seksyen seksyen Soalan. Jika terdapat sebarang pertanyaan, sila pos ini pada CS50 Bincangkan. 

Baiklah. Mari kita mulakan. Sekarang saya melihat 3 halaman Spesifikasi Set Masalah. Kami akan mula bercakap tentang pokok binari kerana mereka mempunyai banyak kaitan dengan set masalah minggu ini - Pokok pengekodan Huffman. Salah satu struktur data yang sangat pertama kita bercakap tentang di CS50 adalah array. Ingatlah bahawa array adalah urutan elemen - semua jenis yang sama - yang disimpan di sebelah antara satu sama lain dalam ingatan. Jika saya mempunyai pelbagai integer yang saya boleh menarik menggunakan gaya ini kotak-nombor integer - Katakan saya mempunyai 5 dalam kotak pertama, saya mempunyai 7 di kedua, maka saya mempunyai 8, 10, dan 20 dalam kotak yang terakhir. Ingat, kedua-dua benar-benar baik perkara tentang array ini adalah bahawa kita mempunyai akses ini berterusan masa kepada mana-mana elemen tertentu  dalam pelbagai jika kita tahu indeks. Sebagai contoh, jika saya mahu merebut elemen ketiga dalam array - pada indeks 2 menggunakan sistem berasaskan sifar pengindeksan kami - Saya benar-benar hanya perlu untuk melakukan pengiraan matematik mudah, melompat ke kedudukan itu dalam array, tarik keluar 8 yang disimpan di sana, dan saya baik untuk pergi. 

Salah satu daripada perkara-perkara buruk tentang array ini - bahawa kita bercakap tentang apabila kita membincangkan dikaitkan senarai - adalah bahawa jika saya mahu memasukkan unsur ke dalam array ini, Saya akan perlu untuk melakukan beberapa beralih sekitar. Sebagai contoh, ini pelbagai di sini dalam perintah disusun - disusun dalam tertib menaik - 5, 7, maka 8, kemudian 10, dan kemudian 20 - tetapi jika saya mahu memasukkan nombor 9 ke array ini, Saya akan perlu untuk beralih beberapa elemen untuk membuat ruang. Kita boleh menarik ini di sini. Saya akan mempunyai untuk bergerak 5, 7, dan maka 8; mewujudkan jurang di mana saya boleh meletakkan 9, dan kemudian 10 dan 20 boleh pergi ke kanan daripada 9. Ini adalah jenis sakit kerana dalam senario kes terburuk - apabila kita perlu untuk memasukkan sama ada di awal atau di akhir array, bergantung kepada bagaimana kita beralih - kita mungkin akhirnya perlu untuk mengalihkan semua unsur-unsur bahawa kita sedang menyimpan dalam array. 

Jadi, apa cara sekitar ini? Cara sekitar ini adalah untuk pergi ke kaedah berkaitan senarai kami di mana - bukannya menyimpan 5 elemen, 7, 8, 10, dan 20 semua bersebelahan antara satu sama lain dalam ingatan - apa yang kita bukannya tidak telah menyimpan mereka jenis mana-mana kita mahu untuk menyimpan mereka dalam nod senarai berpaut yang saya menarik di sini, jenis ad-hoc. Dan kemudian kita disambungkan mereka bersama-sama menggunakan petunjuk seterusnya. Saya boleh mempunyai penunjuk dari 5 kepada 7, penunjuk daripada 7 kepada 8, penunjuk dari 8 ke 10, dan akhirnya, penunjuk dari 10 kepada 20, dan kemudian penunjuk nol pada 20 menunjukkan bahawa tiada apa-apa kiri. Trade-off yang kita ada di sini adalah bahawa sekarang jika kita mahu memasukkan nombor 9 ke dalam senarai diisih kami, semua yang perlu kita lakukan adalah mewujudkan nod baru dengan 9, wayar sehingga ke titik ke tempat yang sesuai, dan kemudian semula wayar 8 yang menunjukkan turun kepada 9. Itu cukup pantas, dengan anggapan kita tahu di mana kita mahu memasukkan 9. Tetapi trade-off dalam pertukaran untuk ini adalah bahawa sekarang kami telah kehilangan akses malar masa kepada mana-mana elemen tertentu dalam struktur data kami. Sebagai contoh, jika saya ingin mencari elemen keempat dalam senarai ini berpaut, Saya akan mempunyai untuk memulakan pada awal-awal senarai dan bekerja cara saya melalui mengira nod oleh nod sehingga saya mendapati yang keempat. 

Dalam usaha untuk mendapatkan akses prestasi yang lebih baik daripada senarai berkaitan - tetapi juga mengekalkan beberapa faedah yang kita terpaksa dari segi masa kemasukan dari senarai berkaitan - pokok binari akan perlu untuk menggunakan memori yang lebih sedikit. Secara khususnya, bukan hanya mempunyai satu penunjuk dalam nod pokok binari - seperti senarai berpaut-nod tidak - kita akan menambah penunjuk kedua kepada nod pokok binari. Bukannya hanya mempunyai satu penunjuk kepada elemen seterusnya, kita akan mempunyai penunjuk kepada kanak-kanak kiri dan kanak-kanak yang betul. 

Mari melukis gambar untuk melihat apa yang sebenarnya kelihatan seperti. Sekali lagi, saya akan menggunakan kotak-kotak dan anak panah. Satu nod pokok binari akan bermula dengan hanya kotak yang mudah. Ia akan mempunyai ruang untuk nilai, dan kemudian ia juga akan mempunyai ruang untuk kanak-kanak kiri dan kanak-kanak yang betul. Saya akan melabelkan mereka di sini. Kami akan mempunyai anak kiri, dan kemudian kita akan mempunyai kanak-kanak yang betul. Terdapat banyak cara yang berbeza untuk melakukan ini. Kadang-kadang untuk ruang dan kemudahan, Saya sebenarnya akan menarik ia seperti yang saya lakukan di sini di bahagian bawah di mana saya akan mempunyai nilai di atas, dan kemudian kanak-kanak yang betul di bawah kanan, dan kanak-kanak kiri di bawah kiri. Akan kembali kepada gambarajah ini atas, kita mempunyai nilai di atas, maka kita mempunyai penunjuk kiri-anak, dan kemudian kita mempunyai penunjuk hak kanak-kanak. 

Dalam Spesifikasi Set Masalah, kita bercakap mengenai lukisan nod yang mempunyai nilai 7, dan kemudian penunjuk kiri kanak-kanak itu adalah batal, dan penunjuk hak-anak itu adalah batal. Kita boleh menulis NULL modal di dalam ruang bagi kedua-dua kanak-kanak kiri dan kanak-kanak yang betul, atau kita boleh menarik ini slash pepenjuru melalui setiap kotak untuk menunjukkan bahawa ia adalah batal. Saya akan berbuat demikian hanya kerana itulah mudah. Apa yang anda lihat di sini adalah dua cara diagramming nod pokok binari yang sangat mudah di mana kita mempunyai nilai 7 dan tunjuk ajar anak batal. 

Bahagian kedua ceramah spesifikasi kami tentang bagaimana dengan dikaitkan senarai - ingat, kita hanya terpaksa untuk berpegang kepada unsur yang pertama dalam senarai ingat seluruh senarai - dan begitu juga, dengan pokok binari, kita hanya perlu untuk berpegang kepada satu penunjuk kepada pokok dalam usaha untuk mengekalkan kawalan ke atas keseluruhan struktur data. Ini elemen khas pokok dipanggil nod akar pokok itu. Sebagai contoh, jika nod satu - nod ini mengandungi nilai 7 dengan penunjuk kiri dan kanan anak null - nilai hanya di pokok kami, maka ini akan menjadi nod akar kita. Ia adalah permulaan yang sangat pokok kami. Kita boleh melihat ini sedikit lebih jelas apabila kita mula menambah lebih nod ke pokok kita. Biar saya tarik sehingga halaman baru. 

Sekarang kita pergi untuk menarik pokok yang mempunyai 7 pada akar, dan 3 dalam anak kiri, dan 9 dalam kanak-kanak yang betul. Sekali lagi, ini adalah agak mudah. Kami telah mendapat 7, lukiskan nod bagi 3, nod for 9, dan saya akan menetapkan penunjuk kiri-anak 7 menuding kepada nod mengandungi 3, dan penunjuk-anak kanan nod yang mengandungi 7 nod mengandungi 9. Sekarang, sejak 3 dan 9 tidak mempunyai mana-mana kanak-kanak, kita pergi untuk menetapkan semua petunjuk anak mereka menjadi batal. Sini, akar pokok kita sepadan dengan nod mengandungi nombor 7. Anda boleh melihat bahawa jika semua yang kita ada adalah penunjuk kepada nod akar itu, maka kita boleh berjalan melalui pokok kami dan mengakses nod kedua-dua kanak-kanak - kedua-dua 3 dan 9. Tidak perlu untuk mengekalkan petunjuk untuk setiap nod tunggal pada pokok itu. Baiklah. Sekarang kita pergi untuk menambah nod lain kepada gambarajah ini. Kami akan menambah nod mengandungi 6, dan kita akan menambah ini sebagai kanak-kanak yang betul nod mengandungi 3. Untuk berbuat demikian, saya akan memadam bahawa penunjuk nol dalam 3 nod dan wayar sehingga ia menuding kepada nod mengandungi 6. Baiklah. 

Pada ketika ini, marilah kita pergi lebih sedikit istilah. Untuk memulakan, sebab bahawa ini dipanggil pokok binari khususnya adalah bahawa ia mempunyai dua penunjuk kanak-kanak. Terdapat lain-lain jenis pokok yang mempunyai lebih banyak petunjuk kanak-kanak. Khususnya, anda melakukan 'cuba' dalam Set Masalah 5. Anda akan melihat bahawa dalam mencuba bahawa, anda mempunyai 27 penunjuk berbeza kepada kanak-kanak yang berbeza - salah satu bagi setiap 26 huruf dalam abjad Inggeris, dan kemudian 27 untuk apostrofe - demikian, itu serupa kepada sejenis pokok. Tetapi di sini, sejak binari itu, kita hanya mempunyai dua penunjuk kanak-kanak. 

Di samping itu kepada nod akar ini bahawa kita bercakap tentang, kita juga telah telah membuang seluruh istilah ini 'kanak-kanak.' Apakah maknanya untuk satu nod untuk menjadi kanak-kanak nod lain? Ia bermaksud bahawa nod kanak-kanak adalah seorang kanak-kanak nod lain jika itu nod lain mempunyai salah satu petunjuk kanak-kanak bersedia untuk menunjukkan kepada nod tersebut. Untuk meletakkan ini ke dalam terma yang lebih konkrit, jika 3 ditunjukkan oleh salah satu penunjuk anak 7, maka 3 adalah kanak-kanak 7. Jika kita memikirkan apa yang anak-anak 7 - baik, kita melihat bahawa 7 mempunyai penunjuk kepada 3 dan penunjuk hingga 9, jadi 9 dan 3 kanak-kanak 7. Sembilan tidak mempunyai anak kerana petunjuk kanak-kanak adalah batal, dan 3 hanya mempunyai seorang kanak-kanak, 6. Enam juga tidak mempunyai anak kerana kedua-dua petunjuk yang adalah batal, yang kita akan menarik sekarang. 

Selain itu, kita juga bercakap mengenai ibu bapa nod tertentu, dan ini adalah, seperti yang anda harapkan, sebaliknya perihal kanak-kanak ini. Setiap nod mempunyai hanya satu ibu bapa bukan dua seperti yang anda jangkakan dengan manusia. Sebagai contoh, ibu bapa 3 ialah 7. Ibu bapa 9 adalah juga 7, dan ibu bapa 6 3. Tidak banyak kepadanya. Kami juga mempunyai terma untuk bercakap tentang datuk nenek dan cucu, dan lebih amnya kita bercakap mengenai nenek moyang dan keturunan nod tertentu. Moyang nod atau nenek moyang, sebaliknya, nod - semua nod yang terletak di jalan dari akar ke nod tersebut. Sebagai contoh, jika saya mencari di 6 nod, maka nenek moyang akan menjadi kedua-dua 3 dan 7. Nenek moyang 9, sebagai contoh, adalah - jika saya mencari di 9 nod - maka moyang 9 hanyalah 7. Dan keturunan adalah tepat sebaliknya. Jika saya mahu melihat semua keturunan 7, maka saya perlu melihat semua nod bawahnya. Jadi, saya mempunyai 3, 9, dan 6 semua sebagai keturunan 7. 

Istilah terakhir yang kita akan bercakap tentang adalah idea ini menjadi adik-beradik. Adik-beradik - jenis berikut bersama-sama atas terma keluarga - adalah nod yang berada di tahap yang sama di pokok itu. Jadi, 3 dan 9 adik-beradik kerana mereka berada di tahap yang sama dalam pokok itu. Mereka kedua-duanya mempunyai ibu bapa yang sama, 7. 6 tidak mempunyai adik-beradik kerana 9 tidak mempunyai apa-apa kanak-kanak. Dan 7 tidak mempunyai apa-apa adik-beradik kerana ia adalah akar pokok kami, dan terdapat hanya pernah 1 akar. Selama 7 hingga mempunyai adik-beradik di sana akan menjadi nod di atas 7. Terdapat akan menjadi ibu bapa 7, di mana 7 tidak lagi akan menjadi akar pokok. Kemudian bahawa ibu bapa baru 7 juga akan perlu untuk mempunyai anak, dan kanak-kanak itu kemudian akan menjadi adik-beradik daripada 7. 

Baiklah. Bergerak ke atas. Apabila kita memulakan perbincangan kami pokok binari, kita bercakap tentang bagaimana kita akan menggunakan mereka untuk mendapat kelebihan berbanding kedua-dua tatasusunan dan senarai yang berkaitan. Dan cara kita pergi untuk berbuat demikian adalah dengan harta ini pesanan. Kami mengatakan bahawa pokok binari diperintahkan, mengikut spesifikasi, jika untuk setiap nod dalam pokok kami, semua keturunan di sebelah kiri - kanak-kanak kiri dan semua keturunan anak kiri - mempunyai nilai-nilai yang lebih rendah, dan semua nod di sebelah kanan - kanak-kanak yang betul dan semua keturunan kanak-kanak yang betul - mempunyai nod yang lebih besar daripada nilai nod semasa yang kita sedang melihat. Hanya untuk kesederhanaan, kita akan menganggap bahawa tidak ada mana-mana nod pendua di pokok kita. Sebagai contoh, dalam pokok ini kita tidak akan berurusan dengan kes di mana kita mempunyai nilai 7 pada akar  dan kemudian kita juga mempunyai nilai 7 tempat lain di pokok itu. Dalam kes ini, anda akan melihat bahawa pokok ini memang diperintahkan. Kami mempunyai 7 nilai pada akar. Semua kiri 7 - jika saya membatalkan semua tanda-tanda kecil di sini - segala-galanya ke kiri 7 - 3 dan 6 - nilai-nilai kedua-duanya adalah kurang daripada 7, dan segala-galanya yang betul - yang hanya 9 ini - adalah lebih besar daripada 7. 

Ini bukan pokok hanya diperintahkan yang mengandungi nilai-nilai, tetapi mari kita lukiskan lebih sedikit daripada mereka. Terdapat sebenarnya adalah sekumpulan keseluruhan cara-cara yang boleh kita lakukan ini. Saya akan menggunakan trengkas hanya untuk menjaga perkara-perkara yang mudah di mana - bukannya mengeluarkan seluruh kotak dan anak panah - Saya hanya akan menarik nombor dan tambah anak panah yang menghubungkan mereka. Untuk memulakan, kita hanya akan menulis pokok asal kita sekali lagi di mana kita mempunyai 7, dan kemudian 3, dan kemudian 3 menunjukkan kembali kepada hak kepada 6, dan 7 mempunyai seorang kanak-kanak yang betul adalah 9. Baiklah. Apa cara lain yang kita boleh menulis pokok ini? Sebaliknya mempunyai 3 menjadi anak kiri 7, kita juga boleh mempunyai 6 menjadi anak kiri 7, dan kemudian 3 menjadi anak kiri 6. Yang akan kelihatan seperti pokok ini di sini di mana saya telah mendapat 7, 6, maka 3, dan 9 di sebelah kanan. Kita juga tidak perlu mempunyai 7 sebagai nod akar kami. Kita juga boleh mempunyai 6 sebagai nod akar kita. Apa yang akan kelihatan seperti? Jika kita pergi untuk mengekalkan harta yang diperintahkan, segala-galanya ke kiri sebanyak 6 telah menjadi kurang daripada ia. Terdapat hanya satu kemungkinan, dan itulah 3. Tetapi kemudian sebagai kanak-kanak yang betul 6, kita mempunyai dua kemungkinan. Pertama, kita boleh mempunyai 7 dan kemudian 9, atau kita boleh menarik - seperti saya kira-kira untuk melakukan di sini - di mana kita mempunyai 9 sebagai kanak-kanak yang betul daripada 6, dan kemudian 7 sebagai anak kiri daripada 9. 

Sekarang, 7 dan 6 tidak nilai hanya boleh dilakukan untuk akar. Kita juga boleh mempunyai 3 berada di akar. Apakah yang akan berlaku jika 3 adalah pada akar? Di sini, perkara mendapatkan sedikit menarik. Tiga tidak mempunyai sebarang nilai yang kurang daripada itu, supaya seluruh sebelah kiri pokok itu hanya akan menjadi batal. Terdapat tidak akan menjadi apa-apa di sana. Ke kanan, kita boleh menyenaraikan perkara-perkara dalam tertib menaik. Kita boleh mempunyai 3, maka 6, maka 7, kemudian 9. Atau, kita boleh melakukan 3, maka 6, maka 9, maka 7. Atau, kita boleh melakukan 3, maka 7, kemudian 6, kemudian 9. Atau, 3, 7 - sebenarnya tidak, kita tidak boleh melakukan 7 lagi. Itulah satu perkara kami di sana. Kita boleh melakukan 9, dan kemudian dari 9 kita boleh lakukan 6 dan kemudian 7. Atau, kita boleh melakukan 3, maka 9, kemudian 7, dan kemudian 6. 

Satu perkara yang menarik perhatian anda di sini adalah bahawa pokok-pokok adalah sedikit pelik-cari. Khususnya, jika kita melihat 4 pokok di sebelah kanan - Saya akan mengelilingi mereka, di sini - pokok-pokok kelihatan hampir tepat seperti senarai berkaitan. Setiap nod mempunyai hanya seorang kanak-kanak, dan sebagainya kita tidak mempunyai apa-apa struktur ini seperti pokok yang kita lihat, sebagai contoh,  dalam pokok ini satu tunggal di sini di sebelah kiri bahagian bawah. Pokok-pokok sebenarnya dipanggil merosot pokok binari, dan kita akan bercakap tentang ini lebih di masa depan - terutamanya jika anda pergi untuk mengambil kursus sains komputer lain. Ini pokok merosot. Mereka tidak sangat berguna kerana, sesungguhnya, struktur ini meminjamkan sendiri  untuk lookup serupa dengan senarai dikaitkan kali. Kita tidak dapat untuk mengambil kesempatan daripada memori tambahan - ini penunjuk tambahan - kerana struktur kita menjadi buruk dalam cara ini. Bukannya pergi dan menarik keluar pokok binari yang mempunyai 9 pada akar, yang merupakan kes terakhir yang kita akan mempunyai, kami sebaliknya, pada ketika ini, akan bercakap sedikit tentang istilah ini lain yang kita gunakan apabila bercakap tentang pokok-pokok, yang dipanggil ketinggian. 

Ketinggian pokok adalah jarak dari akar kepada nod yang paling-jauh, atau sebaliknya bilangan hop yang anda akan perlu membuat untuk bermula dari akar dan kemudian berakhir pada nod yang paling jauh di pokok itu. Jika kita lihat di beberapa pokok-pokok yang kami telah disediakan di sini, kita dapat melihat bahawa jika kita mengambil pokok ini di sudut kiri atas dan kita bermula pada 3, maka kita perlu membuat 1 hop untuk sampai kepada 6, hop kedua untuk mendapatkan kepada 7, dan hop ketiga untuk mendapatkan kepada 9. Jadi, ketinggian pokok ini adalah 3. Kita boleh melakukan senaman sama untuk pokok-pokok lain yang digariskan dengan hijau ini, dan kita lihat bahawa ketinggian semua pokok-pokok juga memang 3. Itu sebahagian daripada apa yang membuatkan mereka merosot - bahawa ketinggian mereka adalah hanya satu kurang daripada bilangan nod di seluruh pokok. Jika kita melihat pokok ini lain yang dikelilingi dengan warna merah, di sisi lain, kita lihat bahawa nod daun paling jauh adalah 6 dan 9 - daun menjadi orang-nod yang tidak mempunyai anak. Jadi, untuk mendapatkan dari nod akar sama ada 6 atau 9, kita perlu membuat satu hop untuk mendapatkan kepada 7 dan kemudian hop kedua untuk mendapatkan kepada 9, dan begitu juga, hanya hop kedua daripada 7 untuk mendapatkan kepada 6. Jadi, ketinggian pokok ini di sini adalah hanya 2. Anda boleh kembali dan berbuat demikian untuk semua pokok-pokok yang lain yang kita telah dibincangkan sebelum ini bermula dengan 7 dan 6, dan anda akan mendapati bahawa ketinggian semua pokok-pokok juga 2. 

Sebab kita telah bercakap tentang mengarahkan pokok binari dan mengapa mereka sejuk kerana anda boleh mencari melalui mereka dalam cara yang sangat serupa dengan mencari lebih pelbagai disusun. Ini adalah di mana kita bercakap tentang mendapatkan masa pencarian yang lebih baik senarai lebih mudah dikaitkan. Dengan senarai berkaitan - jika anda mahu untuk mencari elemen tertentu - anda berada pada terbaik akan melakukan beberapa jenis carian linear di mana anda bermula pada awal senarai dan hop satu demi satu - satu nod oleh satu nod - melalui senarai keseluruhan sehingga anda mencari apa sahaja yang anda sedang mencari. Manakala, jika anda mempunyai pokok binari yang disimpan dalam format ini bagus, anda sebenarnya boleh mendapatkan lebih banyak carian binari berlaku di mana anda membahagi dan menakluk dan carian melalui separuh pokok pada setiap langkah yang sesuai. Mari kita lihat bagaimana bahawa kerja-kerja. 

Jika kita mempunyai - sekali lagi, akan kembali kepada pokok asal kita - kita mula pada 7, kita mempunyai 3 di sebelah kiri, 9 di sebelah kanan, dan di bawah 3, kami mempunyai 6. Jika kita mahu mencari nombor 6 dalam pokok ini, kita akan bermula di akar. Kami akan membandingkan nilai kita sedang mencari untuk, katakan 6, kepada nilai yang disimpan di dalam nod bahawa kita sedang melihat, 7, mendapati bahawa 6 memang kurang daripada 7, jadi kita akan bergerak ke kiri. Jika nilai 6 telah lebih daripada 7, kita akan telah sebaliknya berpindah ke kanan. Sejak kita tahu bahawa kerana struktur pokok binari kita diperintahkan - semua nilai kurang daripada 7 akan disimpan ke kiri 7, tidak perlu bersusah payah mencari melalui sebelah kanan pokok. Apabila kita bergerak ke kiri dan kami kini pada nod mengandungi 3, yang boleh kita lakukan bahawa perbandingan yang sama sekali lagi di mana kita bandingkan 3 dan 6. Dan kita dapati bahawa manakala 6 - nilai yang kita cari - adalah lebih besar daripada 3, kita boleh pergi ke sebelah kanan nod mengandungi 3. Tiada sebelah kiri di sini, jadi kita boleh diabaikan bahawa. Tetapi kita hanya tahu bahawa kerana kita sedang melihat pokok itu sendiri, dan kita dapat melihat bahawa pokok itu tidak mempunyai anak. 

Ia juga agak mudah untuk mencari 6 dalam pokok ini jika kita melakukannya diri kita sebagai manusia, tetapi mari kita mengikuti proses ini mekanikal seperti komputer akan lakukan untuk benar-benar memahami algoritma. Pada ketika ini, kami sedang mencari di nod yang mengandungi 6, dan kita sedang mencari nilai 6, demikian, sesungguhnya, kami telah menemui nod yang sesuai. Kami mendapati nilai 6 di pokok kita, dan kita boleh menghentikan carian kami. Pada ketika ini, bergantung kepada apa yang berlaku, kita boleh katakan, ya, kami telah menemui nilai 6, ia wujud di pokok kita. Atau, jika kita sedang merancang untuk memasukkan nod atau melakukan sesuatu, kita boleh berbuat demikian pada ketika ini. 

Mari kita buat pasangan lebih lookup hanya untuk melihat bagaimana kerja-kerja ini. Mari kita melihat apa yang berlaku jika kita adalah untuk mencuba dan mencari nilai 10. Jika kita melihat nilai 10, kita akan bermula di akar. Kami ingin melihat bahawa 10 adalah lebih besar daripada 7, jadi kita akan bergerak ke kanan. Kami ingin sampai kepada 9 dan bandingkan 9 kepada 10 dan melihat bahawa 9 memang kurang daripada 10. Jadi sekali lagi, kita akan cuba untuk bergerak ke kanan. Tetapi pada masa ini, kita akan melihat bahawa kita berada di nod nol. Tiada apa-apa di sana. Tiada apa-apa di mana 10 harus. Ini adalah di mana kita boleh melaporkan kegagalan - bahawa terdapat sesungguhnya tidak 10 di pokok itu. Dan akhirnya, mari kita pergi melalui kes di mana kita sedang cuba untuk mencari 1 dalam pokok itu. Ini adalah serupa dengan apa yang berlaku jika kita melihat sehingga 10, kecuali bukannya pergi ke kanan, kita akan pergi ke kiri. Kami bermula pada 7 dan melihat bahawa 1 adalah kurang daripada 7, jadi kami bergerak ke kiri. Kami mendapat kepada 3 dan melihat bahawa 1 adalah kurang daripada 3, jadi sekali lagi kita cuba untuk bergerak ke kiri. Pada ketika ini kita mempunyai nod batal, jadi sekali lagi kita boleh melaporkan kegagalan. 

Jika anda ingin mengetahui lebih lanjut mengenai pokok binari, terdapat sekumpulan keseluruhan masalah menyeronokkan sedikit yang boleh anda lakukan dengan mereka. Saya cadangkan mengamalkan lukisan daripada gambar rajah ini satu demi satu dan mengikuti melalui semua langkah-langkah yang berbeza, kerana ini akan datang dalam berguna super bukan sahaja apabila anda melakukan pengekodan Huffman masalah set tetapi juga dalam kursus-kursus yang akan datang - hanya belajar bagaimana untuk menarik keluar struktur data dan berfikir melalui masalah dengan pen dan kertas atau, dalam kes ini, iPad dan stilus. 

Pada ketika ini walaupun, kita akan bergerak ke atas untuk melakukan beberapa amalan kod dan sebenarnya bermain dengan pokok-pokok binari dan lihat. Saya akan bertukar kembali ke komputer saya. Untuk bahagian ini seksyen itu, dan bukannya menggunakan CS50 Run atau CS50 Ruang, Saya akan menggunakan perkakas. 

Berikutan bersama-sama dengan spesifikasi Set Masalah, Saya melihat bahawa saya sepatutnya untuk membuka perkakas, pergi ke folder Dropbox saya, membuat folder yang dipanggil Seksyen 7, dan kemudian mewujudkan fail yang dipanggil binary_tree.c. Di sini kita pergi. Saya telah mendapat perkakas sudah terbuka. Saya akan tarik sehingga terminal. Saya akan pergi ke folder Dropbox, membuat direktori yang dipanggil Seksyen 7, dan melihat ia benar-benar kosong. Sekarang saya akan untuk membuka binary_tree.c. Baiklah. Di sini kita pergi - fail kosong. 

Mari kita kembali kepada spesifikasi. Spesifikasi meminta untuk mencipta definisi jenis baru bagi nod pokok binari yang mengandungi nilai int - seperti nilai-nilai yang kita menarik dalam diagramming kami sebelum. Kami akan menggunakan ini boilerplate typedef bahawa kita telah dilakukan di sini bahawa anda harus mengiktiraf daripada Set Masalah 5 - jika anda melakukannya cara jadual hash program pengeja menakluk. Anda juga perlu mengiktiraf ia dari seksyen minggu lepas di mana kita bercakap mengenai senarai yang dipautkan. Kami telah mendapat ini typedef nod struct, dan kami telah diberikan ini nod struct ini nama nod struct terlebih dahulu supaya kita boleh merujuk kepada ia kerana kita akan mahu mempunyai petunjuk nod struct sebagai sebahagian daripada struct kami, tetapi kami telah kemudian dikelilingi ini - atau sebaliknya, disertakan ini - dalam typedef supaya, kemudian dalam kod, kita boleh merujuk kepada struct ini hanya sebagai nod bukannya nod struct. 

Ini akan menjadi sangat serupa dengan definisi berseorangan berkaitan senarai yang kita lihat minggu lepas. Untuk melakukan ini, mari kita mulakan dengan menulis boilerplate. Kita tahu bahawa kita perlu mempunyai nilai integer, jadi kita akan dimasukkan ke dalam nilai int, dan kemudian bukannya mempunyai hanya satu penunjuk kepada elemen seterusnya - seperti yang kita lakukan dengan senarai secara tunggal berkaitan - kita akan mempunyai petunjuk anak kiri dan kanan. Itu agak mudah juga - struct nod kanak-kanak * kiri; dan struct nod * kanak-kanak yang betul;. Sejuk. Yang kelihatan seperti satu permulaan yang cukup baik. Mari kita kembali kepada spesifikasi. 

Sekarang kita perlu mengisytiharkan * nod pembolehubah global untuk akar pokok. Kami akan membuat global ini sama seperti kita membuat penunjuk pertama dalam senarai dikaitkan juga global kami. Ini adalah supaya dalam fungsi yang kita menulis kita tidak perlu untuk memastikan lulus sekitar akar ini - walaupun kita akan melihat bahawa jika anda mahu untuk menulis fungsi-fungsi rekursif, ia mungkin lebih baik untuk tidak lulus di sekeliling sebagai global di tempat pertama dan bukannya memulakan tempatan dalam fungsi utama anda. Tetapi, kami akan melakukannya global untuk memulakan. Sekali lagi, kita akan memberikan beberapa ruang, dan saya akan mengisytiharkan akar * nod. Hanya untuk memastikan bahawa saya tidak meninggalkan ini tidak diisytiharkan, saya akan menetapkan ia sama untuk menyeimbangkan. Kini, fungsi utama - yang kami akan menulis benar-benar cepat di sini - int utama (int argc, malar char * argv []) - dan saya akan mula mengisytiharkan pelbagai argv saya sebagai malar hanya supaya saya tahu bahawa hujah mereka adalah hujah bahawa saya mungkin tidak mahu untuk mengubah suai. Jika saya mahu mengubah mereka saya mungkin perlu membuat salinan mereka. Anda akan melihat ini banyak dalam kod. Ia adalah denda sama ada cara. Ia adalah baik untuk meninggalkan ia sebagai - tinggalkan malar jika anda ingin. Saya biasanya meletakkan ia dalam hanya supaya saya mengingatkan diri  bahawa saya mungkin tidak mahu mengubah hujah-hujah mereka. 

Seperti biasa, saya akan menyertakan pulangan 0 selaras pada akhir utama. Di sini, saya akan memulakan nod akar saya. Sebagaimana keadaannya sekarang, saya telah mendapat pointer yang ditetapkan untuk menyeimbangkan, jadi ia menunjuk pada apa-apa. Dalam usaha untuk benar-benar mula membina nod, Saya mula-mula perlu untuk memperuntukkan memori untuk itu. Saya akan berbuat demikian dengan membuat ingatan pada timbunan menggunakan malloc. Saya akan menetapkan akar yang sama dengan hasil malloc, dan saya akan menggunakan pengendali sizeof untuk mengira saiz nod. Sebab itu saya menggunakan nod sizeof berbanding, katakan, melakukan sesuatu seperti ini - malloc (4 + 4 +4) atau malloc 12 - adalah kerana saya ingin kod saya untuk menjadi seperti yang serasi sebagai mungkin. Saya mahu menjadi mampu untuk mengambil fail ini c, menyusun perkakas, dan kemudian menyusun pada Mac 64-bit - atau pada seni bina yang sama sekali berbeza - dan saya mahu semua ini untuk bekerja sama. 

Jika saya membuat andaian mengenai saiz pembolehubah - saiz int atau saiz penunjuk - maka saya juga membuat andaian mengenai jenis seni bina di mana kod saya berjaya boleh mengumpul apabila berjalan. Sentiasa gunakan sizeof berbanding manual menjumlahkan bidang struct. Sebab lain adalah bahawa terdapat juga mungkin padding bahawa pengkompil meletakkan ke dalam struct. Walaupun hanya menjumlahkan bidang individu bukan sesuatu yang anda biasanya mahu lakukan, jadi, memadam garisan itu. Kini, untuk benar-benar memulakan ini nod akar, Saya akan mempunyai untuk palam dalam nilai-nilai bagi setiap bidang yang berbeza. Sebagai contoh, untuk nilai yang saya tahu saya mahu memulakan hingga 7, dan buat masa sekarang saya akan menetapkan kanak-kanak kiri menjadi batal dan kanak-kanak yang betul juga menjadi batal. Hebat! Kami telah dilakukan bahawa sebahagian daripada spesifikasi. 

Spesifikasi turun di bahagian bawah halaman 3 meminta saya untuk mewujudkan tiga nod lagi - satu mengandungi 3, satu yang mengandungi 6, dan satu dengan 9 - dan kemudian wayar mereka supaya ia kelihatan sama seperti gambar rajah pokok kami bahawa kita telah bercakap tentang sebelumnya. Mari kita berbuat demikian cukup cepat di sini. Anda akan melihat benar-benar cepat bahawa saya akan mula menulis sekumpulan kod pendua. Saya akan mewujudkan * nod dan saya akan memanggilnya 3. Saya akan menetapkan ia sama dengan malloc (sizeof (nod)). Saya akan menetapkan tiga> value = 3. Tiga -> left_child = NULL, tiga -> kanan _child = NULL; serta. Itu kelihatan agak serupa untuk Memulakan akar, dan itulah apa Saya akan perlu lakukan jika saya mula Memulakan 6 dan 9 serta. Saya akan melakukan yang benar-benar cepat di sini - sebenarnya, saya akan melakukan satu salinan dan tampal sedikit, dan memastikan bahawa saya - mengapa.  Kini, saya telah mendapat ia disalin dan saya boleh pergi ke hadapan dan menetapkan ini sama dengan 6. Anda boleh melihat bahawa ini mengambil seketika dan tidak super cekap. Dalam hanya sedikit, kami akan menulis fungsi yang akan melakukan ini untuk kita. Saya mahu menggantikan ini dengan 9, gantikan dengan 6. 

Sekarang kita telah mendapat semua nod kami diwujudkan dan dimulakan. Kami telah mendapat akar kita menetapkan sama hingga 7, atau mengandungi nilai 7, kami mengandungi nod 3, nod kita mengandungi 6, dan nod kami yang mengandungi 9. Pada ketika ini, semua yang perlu kita lakukan adalah segala-galanya wayar sehingga. Sebab saya dimulakan semua petunjuk untuk menyeimbangkan hanya supaya saya memastikan bahawa Saya tidak mempunyai apa-apa petunjuk yang tidak diisytiharkan di sana oleh kemalangan. Dan juga kerana, pada ketika ini, saya hanya perlu untuk benar-benar menyambung nod antara satu sama lain - kepada orang-orang yang mereka sebenarnya disambungkan kepada - saya tidak perlu untuk pergi melalui dan membuat pasti bahawa semua nulls berada di sana di tempat-tempat yang sesuai. 

Bermula pada akar, saya tahu bahawa anak kiri akar ialah 3. Saya tahu bahawa kanak-kanak yang betul akar ialah 9. Selepas itu, satu-satunya kanak-kanak lain yang saya telah meninggalkan bimbang tentang adalah kanak-kanak kanan 3, yang adalah 6. Pada ketika ini, ia semua kelihatan agak baik. Kami akan memadam beberapa ayat-ayat ini. Sekarang segala-galanya kelihatan agak baik. Mari kita kembali spesifikasi kami dan lihat apa yang kita perlu lakukan seterusnya. 

Pada ketika ini, kita perlu menulis satu fungsi yang dipanggil 'mengandungi' dengan prototaip 'Mengandungi bool (int nilai)'. Dan ini mengandungi fungsi akan kembali benar  jika pokok yang ditunjukkan oleh akar pembolehubah global kami  mengandungi nilai yang diluluskan ke dalam fungsi dan palsu sebaliknya. Mari kita pergi ke hadapan dan melakukan bahawa. Ini akan menjadi sama seperti lookup yang kita lakukan dengan tangan pada iPad hanya sedikit lalu. Mari kita zoom kembali dalam sedikit dan tatal ke atas. Kami akan meletakkan fungsi ini betul-betul di atas fungsi utama kita supaya kita tidak perlu melakukan apa-apa jenis prototaip. Jadi, bool mengandungi (int nilai). Terdapat kita pergi. Ada pengisytiharan boilerplate kami. Hanya untuk memastikan bahawa ini akan menyusun, Saya akan pergi ke hadapan dan hanya menetapkan ia sama untuk kembali palsu. Sekarang fungsi ini hanya tidak akan berbuat apa-apa dan sentiasa melaporkan bahawa nilai yang kita cari tidak di pokok itu. 

Pada ketika ini, ia mungkin idea yang baik - kerana kita telah menulis sejumlah besar kod dan kita tidak cuba menguji lagi - untuk memastikan bahawa ia semua menyusun. Terdapat beberapa perkara yang perlu kita lakukan untuk memastikan bahawa ini sebenarnya akan menyusun. Pertama, lihat jika kita telah menggunakan mana-mana fungsi dalam mana-mana perpustakaan yang telah kita belum dimasukkan. Fungsi kami telah digunakan setakat ini adalah malloc, dan kemudian kami telah juga telah menggunakan jenis ini - jenis ini tidak standard yang dipanggil 'bool' - yang dimasukkan ke dalam fail pengepala bool standard. Kita pasti mahu termasuk bool.h standard bagi jenis bool, dan kita juga mahu # termasuk lib.h standard untuk perpustakaan standard yang termasuk malloc, dan bebas, dan semua itu. Jadi, zum keluar, kita akan berhenti. Mari kita cuba dan pastikan bahawa ini sebenarnya tidak menyusun. Kita lihat bahawa ia, maka kita berada di landasan yang betul. 

Mari kita membuka binary_tree.c lagi. Ia menyusun. Mari kita pergi ke bawah dan pastikan bahawa kita memasukkan beberapa panggilan kepada fungsi Mengandungi kami - hanya untuk memastikan bahawa semua baik dan baik. Sebagai contoh, apabila kita melakukan lookup di pokok kami awal, kita cuba untuk melihat sehingga 6 nilai, 10, dan 1, dan kita tahu bahawa 6 berada di pokok itu, 10 tidak di pokok itu, dan 1 bukan di pokok itu sama ada. Mari kita gunakan mereka panggilan sampel sebagai satu cara untuk mengetahui sama ada atau tidak fungsi Mengandungi kita bekerja. Dalam usaha untuk berbuat demikian, saya akan menggunakan fungsi printf, dan kita pergi untuk mencetak hasil panggilan untuk mengandungi. Saya akan dimasukkan ke dalam rentetan "mengandungi (% d) = kerana  kita akan palam dalam nilai yang kita pergi untuk mencari, dan =% s \ n "dan menggunakannya sebagai rentetan format kami. Kami hanya akan melihat - literal mencetak pada skrin - apa yang kelihatan seperti panggilan fungsi. Ini sebenarnya bukanlah panggilan fungsi.  Ini adalah hanya rentetan yang direka untuk kelihatan seperti panggilan fungsi. 

Sekarang, kita pergi untuk palam dalam nilai. Kami akan cuba mengandungi pada 6, dan kemudian apa yang kita akan lakukan di sini adalah menggunakan bahawa pengendali pertigaan. Mari kita lihat - mengandungi 6 - jadi, sekarang saya telah terkandung 6 dan jika mengandungi 6 adalah benar, rentetan bahawa kita akan menghantar kepada watak format% s akan menjadi rentetan "benar". Mari kita tatal lebih sedikit. Jika tidak, kita mahu menghantar rentetan "palsu" jika mengandungi 6 pulangan palsu. Ini adalah sedikit bodoh-cari, tetapi saya memikirkan saya juga mungkin menggambarkan apa pengendali pertigaan kelihatan seperti kerana kita tidak pernah melihat ia untuk seketika. Ini akan menjadi yang bagus, cara yang berguna untuk mengetahui jika fungsi Mengandungi kami bekerja. Saya akan skrol kembali ke kiri, dan saya akan salin dan tampal baris ini beberapa kali. Ia berubah beberapa nilai-nilai sekitar, jadi ini akan menjadi 1, dan ini akan menjadi 10. 

Pada ketika ini kita telah mendapat fungsi Mengandungi bagus. Kami telah mendapat beberapa ujian, dan kita akan melihat jika ini semua kerja. Pada ketika ini kita telah menulis beberapa kod lagi. Masa untuk berhenti keluar dan memastikan bahawa segala-galanya masih menyusun. Berhenti keluar, dan sekarang mari kita cuba membuat pokok binari lagi. Nah, ia kelihatan seperti kita telah mendapat ralat, dan kita telah mendapat ini jelas mengisytiharkan fungsi perpustakaan printf. Nampaknya kita perlu pergi dalam dan # include standardio.h. Dan dengan itu, segala-galanya harus mengumpul. Kami semua yang baik. Sekarang mari kita cuba berlari pokok binari dan lihat apa yang berlaku. Di sini kita,. / Binary_tree, dan kita lihat bahawa, seperti yang kita harapkan - kerana kita telah tidak dilaksanakan mengandungi lagi, atau sebaliknya, kami baru sahaja dimasukkan ke dalam penyata palsu - kita lihat bahawa ia hanya kembali palsu untuk mereka semua, supaya semua bekerja untuk sebahagian besar yang agak baik. 

Mari kita kembali dalam dan benar-benar melaksanakan mengandungi pada ketika ini. Saya akan tatal ke bawah, mengezum masuk, dan - ingat, algoritma yang kita digunakan adalah bahawa kita bermula pada nod akar dan kemudian pada setiap nod yang kita hadapi, kita melakukan perbandingan, dan berdasarkan perbandingan yang sama ada kita bergerak kepada anak kiri atau kanak-kanak yang betul. Ini akan kelihatan sangat serupa dengan kod carian binari bahawa kita menulis awal dalam jangka. Apabila kita bermula, kita tahu bahawa kita mahu berpegang kepada nod semasa bahawa kita melihat, dan nod semasa akan dimulakan ke nod akar. Dan sekarang, kita akan menyimpan melalui pokok itu, dan ingat bahawa keadaan kita berhenti -  apabila kita benar-benar bekerja melalui contoh oleh tangan - ialah apabila kita menghadapi nod nol, tidak apabila kita melihat seorang kanak-kanak nol, tetapi apabila kita sebenarnya berpindah ke nod dalam pokok dan mendapati bahawa kita berada di nod nol. Kami akan melelar sehingga kini tidak sama untuk menyeimbangkan. Dan apa yang kita akan lakukan? Kami akan menguji jika (kini -> nilai == nilai), maka kita tahu bahawa kita telah benar-benar menemui nod yang kita sedang mencari. Jadi di sini, kita boleh kembali benar. Jika tidak, kita mahu melihat sama ada atau tidak nilai adalah kurang daripada nilai. Jika nilai nod semasa adalah kurang daripada nilai kita sedang mencari, kita akan bergerak ke kanan. Jadi, kini = kini -> right_child; dan selainnya, kita pergi untuk bergerak ke kiri. kini kini = -> left_child;. Agak mudah. 

Anda mungkin mengenali gelung yang kelihatan sangat serupa ini dari gelintaran perduaan awal dalam jangka, kecuali maka kita telah berurusan dengan rendah, pertengahan, dan tinggi. Di sini, kita hanya perlu melihat pada nilai semasa, jadi ia adalah baik dan mudah. Mari kita pastikan kod ini bekerja. Pertama, pastikan ia menyusun. Kelihatan seperti ia. Mari kita cuba berjalan ia. Dan demi sesungguhnya, ia mencetak keluar segala-galanya yang kita harapkan. Ia mendapati 6 di pokok itu, tidak mendapati 10 kerana 10 bukan di pokok itu, dan tidak mencari 1 sama ada kerana 1 juga tidak di pokok itu. Barangan sejuk. 

Baiklah. Mari kita kembali spesifikasi kami dan lihat apa yang seterusnya. Kini, ia mahu menambah beberapa lebih nod ke pokok kita. Ia mahu menambah 5, 2, dan 8, dan memastikan bahawa kita mengandungi kod masih berfungsi seperti yang diharapkan. Mari kita pergi berbuat demikian. Pada ketika ini, bukannya melakukan menjengkelkan bahawa salinan dan tampal sekali lagi, mari menulis fungsi sebenarnya mewujudkan nod. Jika kita tatal ke bawah sepanjang jalan utama, kita melihat bahawa kita telah melakukan ini kod yang sangat serupa berulang-ulang kali setiap kali kita mahu mencipta nod. 

Mari kita menulis fungsi yang sebenarnya akan membina nod untuk kita dan kembalikan. Saya akan memanggilnya build_node. Saya akan membina nod dengan nilai tertentu. Zum masuk sini. Perkara pertama yang saya akan lakukan sebenarnya mewujudkan ruang untuk nod pada timbunan. Jadi, nod * n = malloc (sizeof (nod)); n -> nilai = nilai; dan kemudian di sini, saya hanya akan memulakan semua bidang untuk menjadi nilai-nilai yang sesuai. Dan pada akhir sangat, kami akan kembali nod kami. Baiklah. Satu perkara yang perlu diambil perhatian adalah bahawa fungsi ini di sini akan kembali penunjuk kepada memori yang telah timbunan-diperuntukkan. Apa yang baik tentang perkara ini ialah bahawa nod ini sekarang - kita perlu mengisytiharkan pada timbunan itu kerana jika kita mengisytiharkan ia pada timbunan kita tidak akan dapat melakukannya dalam fungsi ini seperti ini. Memori yang akan keluar dari skop dan akan menjadi tidak sah jika kita cuba untuk mengakses ia kemudian. Sejak kita mengisytiharkan timbunan-ingatan diperuntukkan, kita akan perlu menjaga membebaskan kemudian untuk program kami untuk tidak bocor memori apa-apa. Kami telah punting bahawa untuk segala-galanya dalam kod hanya demi kesederhanaan pada masa itu, tetapi jika anda pernah menulis fungsi yang kelihatan seperti ini di mana anda telah mendapat - beberapa memanggilnya malloc atau realloc di dalam - anda ingin memastikan bahawa anda meletakkan beberapa jenis komen di sini yang mengatakan, hey, anda tahu, mengembalikan nod timbunan diperuntukkan yang dimulakan dengan nilai yang diluluskan dalam. Dan kemudian anda mahu pastikan yang anda dimasukkan ke dalam sejenis nota yang mengatakan pemanggil mesti membebaskan memori yang dikembalikan. Cara itu, jika seseorang yang pernah pergi dan menggunakan fungsi itu, mereka tahu bahawa apa sahaja yang mereka mendapat kembali daripada fungsi yang pada satu ketika akan perlu dibebaskan. 

Mengandaikan bahawa semua adalah baik dan baik di sini, kita boleh pergi ke dalam kod kami dan menggantikan semua ayat-ayat ini di sini dengan panggilan untuk membina fungsi nod kami. Marilah kita melakukan yang benar-benar cepat. Bahagian satu bahawa kita tidak akan untuk menggantikan bahagian ini turun di sini di bawah mana kita sebenarnya wayar nod ke titik antara satu sama lain, kerana itu kita tidak boleh lakukan dalam fungsi kami. Tetapi, mari kita buat root = build_node (7); nod * tiga = build_node (3); nod * enam = build_node (6); nod * 9 = build_node (9);. Dan sekarang, kita juga mahu untuk menambah nod bagi - nod * 5 = build_node (5); nod * 8 = build_node (8); dan apa nod lain? Mari kita lihat di sini. Kami ingin juga menambah 2 - nod * dua = build_node (2); Baiklah. Pada ketika ini, kita tahu bahawa kita telah mendapat 7, 3, 9, dan 6 semua berwayar sehingga sewajarnya, tetapi apa yang kira-kira 5, 8, dan 2? Untuk memastikan segala-galanya dalam perintah yang sesuai, kita tahu bahawa kanak-kanak yang betul 3 ialah 6. Jadi, jika kita akan menambah 5, 5 dengan juga tergolong dalam sebelah kanan pokok yang 3 adalah akar, jadi 5 tergolong sebagai kanak-kanak kiri 6. Kita boleh melakukan ini dengan mengatakan, enam -> left_child = 5; dan kemudian 8 tergolong sebagai kanak-kanak kiri 9, jadi sembilan> left_child = 8; dan kemudian 2 adalah anak kiri 3, jadi kita boleh berbuat demikian di sini - wahai Muhammad -> left_child = dua;. Jika anda tidak cukup mengikuti bersama-sama dengan itu, saya cadangkan anda menarik ia keluar sendiri. 

Baiklah. Mari kita menyimpan ini. Mari kita pergi keluar dan pastikan ia menyusun, dan kemudian kita boleh menambah dalam panggilan Mengandungi kami. Kelihatan seperti segala-galanya masih menyusun. Mari kita pergi dan menambah dalam beberapa mengandungi panggilan. Sekali lagi, saya akan melakukan sedikit salin dan tampal. Sekarang mari mencari 5, 8, dan 2. Baiklah. Mari kita pastikan bahawa ini semua kelihatan baik masih. Hebat! Simpan dan berhenti. Sekarang mari kita membuat, menyusun, dan sekarang mari kita berlari. Daripada keputusan, ia kelihatan seperti semua yang bekerja hanya bagus dan baik. Hebat! Jadi sekarang kita telah mendapat Mengandungi kami berfungsi ditulis. Mari kita bergerak ke atas dan mula bekerja pada bagaimana untuk memasukkan nod ke pokok kerana, seperti yang kita lakukan sekarang, perkara-perkara yang tidak sangat cantik. 

Jika kita kembali kepada spesifikasi, ia meminta kita untuk menulis fungsi yang dipanggil memasukkan - sekali lagi, kembali bool sama ada atau tidak kita sebenarnya boleh memasukkan nod ke pokok - dan kemudian nilai untuk memasukkan ke dalam pokok itu dinyatakan sebagai hujah hanya kepada fungsi memasukkan kami. Kami akan kembali benar jika kita memang boleh memasukkan nilai nod mengandungi ke pokok itu, yang bermaksud bahawa kita, satu, mempunyai memori yang cukup, dan kemudian dua, nod yang tidak sudah wujud di pokok sejak ingat, kita tidak akan mempunyai nilai-nilai yang sama dalam pokok, hanya untuk membuat perkara yang mudah. Baiklah. Kembali kepada kod. Buka. Zum dalam sedikit, kemudian tatal ke bawah. Mari kita meletakkan fungsi memasukkan betul-betul di atas Mengandungi. Sekali lagi, ia akan dipanggil masukkan bool (int nilai). Memberikan ruang yang lebih sedikit, dan kemudian, sebagai lalai, mari kita dimasukkan ke dalam penyata palsu pada akhir sangat. Sekarang turun di bawah, mari kita pergi ke hadapan dan bukannya manual membina nod utama diri kita dan pendawaian mereka sehingga ke titik antara satu sama lain seperti yang kita sedang lakukan, kita akan bergantung pada fungsi memasukkan kami untuk berbuat demikian. Kami tidak akan bergantung pada fungsi memasukkan kami untuk membina pokok keseluruhan dari awal lagi, tetapi kita akan menghilangkan garisan ini - we'll mengulas keluar ayat-ayat ini - yang membina 5 nod, 8, dan 2. Dan sebaliknya, kita akan memasukkan panggilan kepada fungsi memasukkan kami memastikan bahawa sebenarnya berfungsi. Di sini kita pergi. 

Sekarang kita telah mengulas ayat-ayat ini. Kami hanya mempunyai 7, 3, 9, dan 6 di pokok kita pada ketika ini. Untuk memastikan bahawa ini adalah semua bekerja, kita boleh mengezum keluar, membuat pokok binari kami, menjalankannya, dan kita dapat melihat bahawa mengandungi kini memberitahu kita bahawa kita benar-benar betul - 5, 8, dan 2 adalah tidak lagi di pokok itu. Kembali kepada kod, dan bagaimana kita akan memasukkan? Ingat apa yang kita lakukan apabila kita sebenarnya memasukkan 5, 8, dan 2 sebelumnya. Kami bermain bahawa permainan Plinko mana kita bermula pada akar, pergi ke satu pokok dengan satu demi satu sehingga kita mendapati jurang yang sesuai, dan kemudian kita berwayar dalam nod di tempat yang sesuai. Kami akan melakukan perkara yang sama. Ini adalah pada dasarnya seperti menulis kod yang kita digunakan dalam mengandungi fungsi untuk mencari tempat di mana nod harus, dan kemudian kita hanya akan memasukkan nod di sana. Mari kita mulakan berbuat demikian. 

Jadi kita mempunyai nod * kini = akar; kami hanya akan mengikuti mengandungi kod sehingga kita mendapati bahawa ia tidak cukup bekerja untuk kita. Kami akan pergi melalui pokok manakala elemen semasa tidak adalah batal, dan jika kita dapati nilai yang kini adalah sama dengan nilai yang kita sedang cuba untuk memasukkan - baik, ini adalah salah satu kes di mana kita sebenarnya tidak boleh memasukkan nod ke pokok itu kerana ini bermakna kita mempunyai nilai pendua. Di sini kita sebenarnya akan kembali palsu. Sekarang, lain jika nilai kini adalah kurang daripada nilai, sekarang kita tahu bahawa kita bergerak ke kanan  kerana nilai tergolong dalam separuh kanan pokok kini. Jika tidak, kita akan bergerak ke kiri. Itulah pada asasnya Mengandungi kami berfungsi di sana. 

Pada ketika ini, apabila kita telah selesai ini gelung sementara, penunjuk kini kita akan menunjuk untuk menyeimbangkan jika fungsi telah tidak sudah dikembalikan. Oleh itu, Kami mempunyai kini di tempat di mana kita mahu untuk memasukkan nod baru. Apa lagi yang perlu dilakukan adalah untuk benar-benar membina nod baru, yang kita boleh lakukan cukup mudah. Kita boleh menggunakan membina super berguna kami nod fungsi, dan sesuatu yang kita tidak lakukan sebelum ini - kita hanya jenis mengambil untuk diberikan tetapi sekarang kita akan lakukan hanya untuk memastikan - kami akan menguji untuk memastikan bahawa nilai yang dikembalikan oleh nod baru sebenarnya tidak batal, kerana kita tidak mahu untuk memulakan mengakses memori yang jika ia adalah batal. Kita boleh menguji untuk memastikan bahawa nod baru tidak sama dengan null. Atau sebaliknya, kita hanya boleh melihat jika ia benar-benar adalah batal, dan jika ia adalah batal, maka kita hanya boleh kembali palsu awal. 

Pada ketika ini, kita perlu wayar nod baru ke tempat yang sesuai di pokok itu. Jika kita melihat kembali di utama dan di mana kita sebenarnya pendawaian di nilai sebelum ini, kita lihat bahawa cara kita melakukannya apabila kita mahu meletakkan 3 di pokok itu telah kita diakses anak kiri akar. Apabila kita meletakkan 9 di pokok itu, kita terpaksa untuk mengakses kanak-kanak yang betul akar. Kami terpaksa mempunyai penunjuk kepada ibu bapa untuk meletakkan nilai baru ke dalam pokok itu. Menatal sandaran untuk memasukkan, itu tidak akan agak bekerja di sini kerana kita tidak mempunyai penunjuk ibu bapa. Apa yang kita mahu menjadi mampu lakukan adalah, pada ketika ini, memeriksa nilai ibu bapa dan lihat - baik, Astaga, jika nilai ibu bapa adalah kurang daripada nilai semasa, maka anak hak ibu bapa harus menjadi nod baru; sebaliknya, anak kiri ibu bapa harus menjadi nod baru. Tetapi, kita tidak mempunyai penunjuk induk agak lagi. 

Dalam usaha untuk mendapatkan ia, kita sebenarnya akan mempunyai untuk mengesan kerana kita pergi melalui pokok dan mencari tempat yang sesuai dalam gelung di atas kami. Kita boleh berbuat demikian dengan menatal kembali ke atas fungsi memasukkan kami dan pengesanan lain penuding dipanggil ibu bapa. Kami akan menetapkan ia sama untuk menyeimbangkan mulanya, dan kemudian setiap kali kita pergi melalui pokok itu, kita akan menetapkan penunjuk ibu bapa untuk dipadankan penunjuk semasa. Tetapkan ibu bapa sama untuk kini. Dengan cara ini, setiap kali kita pergi melalui, kita akan memastikan bahawa sebagai penunjuk semasa mendapat incremented penunjuk induk berikut - hanya satu tahap lebih tinggi daripada penunjuk semasa dalam pokok itu. Itu semua kelihatan agak baik. 

Saya fikir satu perkara yang kita akan mahu untuk menyesuaikan diri ini membina kembali null nod. Dalam usaha untuk mendapatkan membina nod untuk benar-benar berjaya kembali batal, kita akan mempunyai untuk mengubah suai kod yang, kerana di sini, kita tidak pernah diuji untuk memastikan bahawa malloc kembali penunjuk yang sah. Jadi, jika (n = NULL!), Maka - jika malloc kembali penunjuk yang sah, maka kita akan memulakan ia; sebaliknya, kita hanya akan kembali dan yang akan akhirnya kembali batal untuk kita. Sekarang semua kelihatan agak baik. Mari kita pastikan ini sebenarnya menyusun. Membuat pokok binari, dan oh, kami telah mendapat beberapa perkara yang berlaku di sini. 

Kami telah mendapat pengisytiharan tersirat fungsi membina nod. Sekali lagi, dengan penyusun, kami akan bermula di atas. Apa yang mesti bermakna adalah bahawa saya memanggil membina nod sebelum saya sebenarnya diisytiharkan. Mari kita kembali kepada kod benar-benar cepat. Tatal ke bawah, dan cukup yakin, fungsi memasukkan saya diisytiharkan atas fungsi nod membina, tetapi saya cuba untuk menggunakan membina nod di dalam sisipan. Saya akan pergi dalam salinan dan - dan kemudian paste cara fungsi nod membina sehingga di sini di atas. Cara itu, diharapkan yang akan bekerja. Mari kita memberi ini satu lagi pergi. Kini ia semua menyusun. Semua adalah baik. 

Tetapi pada masa ini, kita tidak sebenarnya dipanggil fungsi memasukkan kami. Kita hanya tahu bahawa ia menyusun, jadi mari kita pergi dalam dan meletakkan beberapa panggilan masuk Mari kita berbuat demikian dalam fungsi utama kami. Di sini, kita mengulas 5, 8, dan 2, dan kemudian kita tidak wayar mereka di sini. Mari kita membuat beberapa panggilan untuk memasukkan, dan mari kita juga menggunakan jenis yang sama barangan yang kita digunakan apabila kita membuat panggilan printf untuk memastikan bahawa segala-galanya tidak dimasukkan dengan betul. Saya akan salin dan tampal, dan bukannya mengandungi kita pergi untuk melakukan memasukkan. Dan bukannya 6, 10, dan 1, kita akan menggunakan 5, 8, dan 2. Ini diharapkan perlu memasukkan 5, 8, dan 2 ke pokok. Mengumpulkannya. Semua adalah baik. Sekarang kita sebenarnya akan menjalankan program kami. 

Segalanya kembali palsu. Jadi, 5, 8, dan 2 tidak pergi, dan ia kelihatan seperti Mengandungi tidak mencari mereka sama ada. Apa yang berlaku? Mari kita mengezum keluar. Masalah pertama ialah memasukkan seolah-olah kembali palsu, dan ia kelihatan seperti itu kerana kita meninggalkan dalam panggilan penyata palsu kami, dan kita tidak pernah benar-benar kembali benar. Kita boleh menetapkan bahawa sehingga. Masalah kedua adalah, kini walaupun kita lakukan - menyelamatkan ini, cukai ini, menjalankan membuat lagi, ia telah menyusun, kemudian berjalan - kita melihat bahawa sesuatu yang lain berlaku di sini. 5, 8, dan 2 masih tidak pernah ditemui di pokok itu. Jadi, apa yang berlaku? 

Mari kita lihat ini dalam kod. Mari kita lihat jika kita boleh memikirkan ini. Kita mulakan dengan ibu bapa tidak menjadi batal. Kami menetapkan penunjuk semasa sama dengan penunjuk akar, dan kita pergi untuk bekerja dengan cara kami ke bawah melalui pokok. Jika nod semasa tidak batal, maka kita tahu bahawa kita boleh bergerak ke bawah sedikit. Kami menetapkan penunjuk induk kami untuk menjadi sama dengan penunjuk semasa, diperiksa nilai - jika nilai adalah sama kita kembali palsu. Jika nilai adalah kurang kita berpindah ke kanan; sebaliknya, kita berpindah ke kiri. Kemudian kita membina nod. Saya akan mengezum masuk sedikit. Dan di sini, kita akan cuba wayar nilai untuk menjadi sama. Apa yang berlaku? Mari kita lihat jika mungkin Valgrind boleh memberi kita petunjuk. 

Saya suka menggunakan Valgrind hanya kerana Valgrind benar-benar cepat berjalan dan memberitahu anda jika terdapat sebarang kesilapan memori. Apabila kita menjalankan Valgrind pada kod, seperti yang anda boleh lihat hit here--Valgrind./binary_tree--and kanan masukkan. Anda melihat bahawa kami tidak mempunyai apa-apa kesilapan memori, jadi ia kelihatan seperti semua okay setakat ini. Kami mempunyai beberapa kebocoran memori, yang kita tahu, kerana kita tidak berada berlaku untuk membebaskan mana-mana nod kami. Mari kita cuba berjalan GDB untuk melihat apa yang sebenarnya berlaku. Kami akan melakukan Pra-Pemasangan / binary_tree. Ia boot sehingga hanya denda. Mari kita menetapkan titik rehat pada insert. Mari kita berjalan. Ia kelihatan seperti kita tidak pernah benar-benar dipanggil insert. Ia kelihatan seperti masalah itu hanya bahawa apabila saya berubah ke sini dalam utama - semua ini panggilan printf dari mengandungi - Saya tidak pernah benar-benar berubah ini untuk memanggil memasukkan. Sekarang mari kita mencubanya. Mari menyusun. Semua kelihatan baik di sana. Sekarang mari kita cuba berjalan ia, lihat apa yang berlaku. Baiklah! Semuanya kelihatan cukup baik di sana. 

Perkara yang terakhir untuk berfikir tentang adalah, adakah terdapat mana-mana kes kelebihan untuk memasukkan ini? Dan ternyata bahawa, baik, kes satu kelebihan yang sentiasa menarik untuk berfikir tentang , apa yang berlaku jika pokok anda adalah kosong dan anda memanggil fungsi ini memasukkan? Ia akan berfungsi? Nah, mari kita mencuba. - Binary_tree c - Cara kita pergi untuk menguji ini, kita akan pergi ke fungsi utama kami, dan bukannya pendawaian nod ini sehingga seperti ini, kita hanya akan mengulas perkara keseluruhan, dan bukannya pendawaian sehingga nodus diri, kita boleh sebenarnya hanya pergi ke hadapan dan memadam semua ini. Kami akan membuat segala-galanya panggilan untuk memasukkan. Jadi, mari kita lakukan - bukannya 5, 8, dan 2, kita akan untuk memasukkan 7, 3, dan 9. Dan kemudian kita juga akan mahu untuk memasukkan 6 serta. Simpan. Berhenti. Buat pokok binari. Ia semua menyusun. Kita hanya boleh jalankan ia sebagai dan lihat apa yang berlaku, tetapi ia juga akan menjadi benar-benar penting untuk memastikan bahawa kita tidak mempunyai apa-apa kesilapan memori, kerana ini adalah salah satu daripada kes kelebihan kita yang kita tahu tentang. 

Mari kita pastikan bahawa ia berfungsi dengan baik di bawah Valgrind, yang kita akan lakukan dengan hanya berjalan Valgrind / binary_tree. Ia kelihatan seperti kita memang mempunyai satu kesilapan dari satu konteks - kita mempunyai kesalahan segmentasi. Apa yang berlaku? Valgrind sebenarnya memberitahu kita di mana ia. Zum keluar sedikit. Ia kelihatan seperti ia berlaku dalam fungsi memasukkan kami, di mana kita mempunyai membaca yang tidak sah daripada 4 saiz pada insert, line 60. Mari kita kembali dan lihat apa yang berlaku di sini. Zum keluar benar-benar cepat. Saya ingin memastikan bahawa ia tidak pergi ke pinggir skrin supaya kita boleh melihat segala-galanya. Tarik bahawa dalam sedikit. Baiklah. Tatal ke bawah, dan masalah yang tepat di sini. Apakah yang akan berlaku jika kita mendapatkan turun dan nod semasa kami sudah batal, nod induk kami adalah batal, jadi jika kita melihat di bahagian paling atas, di sini - jika ini gelung sementara tidak pernah benar-benar melaksanakan kerana nilai semasa kami adalah batal - akar kita adalah batal jadi kini adalah batal - maka ibu bapa kami tidak pernah mendapat bersedia untuk kini atau nilai yang sah, demikian, ibu bapa juga akan menjadi batal. Kita perlu ingat untuk memeriksa masa kita turun di sini, dan kami mula mengakses nilai ibu bapa. Jadi, apa yang berlaku? Nah, jika ibu bapa adalah batal - jika (ibu bapa == NULL) - maka kita tahu bahawa mestilah tidak ada apa-apa di pokok itu. Kita mesti cuba untuk memasukkan ia pada akar. Kita boleh berbuat demikian dengan hanya menetapkan akar yang sama dengan nod baru. Kemudian pada ketika ini, kita tidak benar-benar mahu pergi melalui perkara-perkara lain. Sebaliknya, di sini, kita boleh lakukan sama ada lain-jika-lain, atau kita boleh menggabungkan segala-galanya di sini dalam-galanya, tetapi di sini kita hanya akan menggunakan lain dan melakukannya dengan cara itu. Sekarang, kita akan menguji untuk memastikan bahawa ibu bapa kita tidak batal sebelum itu sebenarnya cuba untuk mengakses bidang. Ini akan membantu kita mengelakkan kesalahan segmentasi. Jadi, kita berhenti, zum keluar, menyusun, jalankan. 

Tiada kesilapan, tetapi kita masih mempunyai sekumpulan kebocoran memori kerana kita tidak membebaskan sebarang nod kami. Tetapi, jika kita pergi di sini dan kita melihat cetakan kami, kita lihat bahawa, baik, kelihatan seperti memasukkan kami semua kembali benar, yang baik. Memasukkan semua adalah benar, dan kemudian Mengandungi sesuai panggilan adalah juga benar. 

Baik kerja! Ia kelihatan seperti kami telah berjaya ditulis memasukkan. Itu semua yang kita ada untuk Spesifikasi Set Masalah minggu ini. Salah satu cabaran yang menyeronokkan untuk berfikir tentang bagaimana anda sebenarnya akan pergi dan bebas semua nod dalam pokok ini. Kita boleh berbuat demikian beberapa cara yang berbeza, tetapi saya akan meninggalkan bahawa terpulang kepada anda untuk mencuba, dan sebagai cabaran yang menyeronokkan, cuba dan pastikan bahawa anda boleh memastikan bahawa laporan ini Valgrind mengembalikan tiada kesilapan dan tiada kebocoran. 

Nasib baik pada set masalah Huffman minggu ini pengekodan, dan kita akan melihat anda minggu depan! [CS50.TV]