[Powered by Google Translate] [Bagian 7] [Kurang Nyaman] [Nate Hardison] [Harvard University] [Ini adalah CS50.] [CS50.TV] 

Selamat Datang di Bagian 7. Berkat badai Sandy, bukan memiliki bagian yang normal pekan ini, kami melakukan hal ini berjalan-melalui, melalui bagian dari pertanyaan. Saya akan mengikuti bersama dengan Masalah Set 6 Spesifikasi, dan akan melalui semua pertanyaan dalam Sebuah Bagian bagian Pertanyaan. Jika ada pertanyaan, silahkan posting ini pada CS50 Bahas. 

Alright. Mari kita mulai. Saat ini aku sedang melihat halaman 3 dari Set Keterangan Soal. Kami akan pertama kali mulai berbicara tentang pohon biner karena mereka memiliki banyak relevansi untuk mengatur masalah ini minggu - pengkodean Pohon Huffman. Salah satu struktur data pertama kita bicarakan pada CS50 adalah array. Ingat bahwa array adalah urutan elemen - semua jenis yang sama - disimpan tepat di samping satu sama lain dalam memori. Jika saya memiliki sebuah array integer yang aku bisa menggambar menggunakan gaya kotak-nomor-bilangan bulat - Katakanlah saya memiliki 5 di kotak pertama, saya memiliki 7 di kedua, maka saya memiliki 8, 10, dan 20 di kotak akhir. Ingat, keduanya benar-benar baik hal tentang array ini adalah bahwa kita memiliki akses konstan-waktu untuk setiap elemen tertentu  dalam array jika kita tahu indeks. Sebagai contoh, jika saya ingin ambil elemen ketiga dalam array - pada indeks 2 menggunakan zero-based sistem pengindeksan kami - Aku benar-benar hanya perlu melakukan perhitungan matematika sederhana, hop ke posisi dalam array, mencabut 8 yang disimpan di sana, dan aku baik untuk pergi. 

Salah satu hal buruk tentang array ini - yang kita bicarakan ketika kita membahas daftar link - adalah bahwa jika saya ingin memasukkan elemen ke dalam array ini, Aku akan harus melakukan beberapa pergeseran sekitar. Misalnya, array ini di sini adalah dalam rangka diurutkan - diurutkan dalam urutan - 5, maka 7, kemudian 8, kemudian 10, kemudian 20 - tetapi jika saya ingin memasukkan nomor 9 ke dalam array ini, Aku akan harus mengalihkan beberapa elemen untuk membuat ruang. Kita dapat menarik ini di sini. Aku akan harus memindahkan 5, 7, dan kemudian 8; menciptakan celah di mana saya dapat menempatkan 9, dan kemudian 10 dan 20 dapat pergi ke kanan 9. Ini adalah jenis rasa sakit karena dalam skenario terburuk - ketika kita harus memasukkan baik di awal atau di akhir dari array, tergantung pada bagaimana kita pergeseran - kita mungkin akhirnya harus menggeser semua elemen bahwa kita sedang menyimpan dalam array. 

Jadi, apa cara sekitar ini? Cara sekitar ini adalah untuk pergi ke linked-list metode kami di mana - bukannya menyimpan elemen 5, 7, 8, 10, dan 20 semua sebelah satu sama lain dalam memori - bukan apa yang kita lakukan adalah menyimpannya jenis mana pun kita ingin menyimpannya dalam linked-list node yang aku menggambar di sini, semacam ad hoc. Dan kemudian kita menghubungkan mereka bersama-sama menggunakan pointer berikutnya. Saya dapat memiliki pointer dari 5 ke 7, pointer dari 7 ke 8, pointer dari 8 ke 10, dan akhirnya, sebuah pointer dari 10 ke 20, dan kemudian pointer null pada 20 menunjukkan bahwa tidak ada yang kiri. Trade-off yang kita miliki di sini adalah bahwa sekarang jika kita ingin memasukkan nomor 9 dalam daftar kami diurutkan, yang harus kita lakukan adalah membuat simpul baru dengan 9, kawat itu untuk menunjuk ke tempat yang tepat, dan kemudian kembali-kawat 8 untuk menunjuk ke 9. Itu cukup cepat, dengan asumsi kita tahu persis di mana kita ingin memasukkan 9. Namun trade-off dalam pertukaran untuk ini adalah bahwa sekarang kami telah kehilangan akses konstan-waktu kepada elemen tertentu dalam struktur data kami. Sebagai contoh, jika saya ingin mencari elemen keempat dalam linked list, Aku akan harus mulai dari awal daftar dan bekerja dengan cara saya melalui menghitung simpul-simpul by-sampai aku menemukan yang keempat. 

Dalam rangka untuk mendapatkan kinerja akses lebih baik daripada linked list - tetapi juga mempertahankan beberapa manfaat yang kita miliki dalam hal penyisipan-waktu dari sebuah linked list - pohon biner akan perlu menggunakan memori lebih sedikit. Secara khusus, bukan hanya memiliki satu pointer dalam simpul pohon biner - seperti linked list-node tidak - kita akan menambahkan pointer kedua node pohon biner. Daripada hanya memiliki satu pointer ke elemen berikutnya, kita akan memiliki pointer ke anak kiri dan anak kanan. 

Mari kita menggambar untuk melihat apa yang benar-benar tampak seperti. Sekali lagi, aku akan menggunakan kotak dan panah. Sebuah simpul pohon biner akan mulai dengan hanya kotak sederhana. Ini akan memiliki ruang untuk nilai, dan kemudian itu juga akan memiliki ruang untuk anak kiri dan anak kanan. Aku akan label mereka di sini. Kita akan memiliki anak kiri, dan kemudian kita akan memiliki anak kanan. Ada banyak cara yang berbeda untuk melakukan hal ini. Kadang-kadang untuk ruang dan kenyamanan, Aku benar-benar akan menarik seperti saya lakukan di sini di bagian bawah di mana aku akan memiliki nilai di atas, dan kemudian anak kanan di kanan bawah, dan anak kiri di bagian bawah-kiri. Akan kembali ke diagram atas, kita memiliki nilai di bagian paling atas, maka kita memiliki pointer kiri-anak, dan kemudian kita memiliki pointer kanan anak. 

Dalam Spesifikasi Soal Set, kita berbicara tentang menggambar simpul yang memiliki nilai 7, dan kemudian pointer kiri-anak yang nol, dan pointer kanan anak yang null. Kita dapat menulis NULL modal dalam ruang untuk baik anak kiri dan anak kanan, atau kita dapat menarik garis miring diagonal ini melalui masing-masing kotak untuk menunjukkan bahwa itu nol. Aku akan melakukan itu hanya karena itu sederhana. Apa yang Anda lihat di sini adalah dua cara diagram simpul biner pohon yang sangat sederhana di mana kita memiliki nilai 7 dan pointer anak nol. 

Bagian kedua pembicaraan spesifikasi kami tentang bagaimana dengan daftar link - ingat, kita hanya harus berpegang pada elemen pertama dalam daftar mengingat seluruh daftar - dan juga, dengan pohon biner, kita hanya perlu berpegang pada satu pointer ke pohon dalam rangka untuk mempertahankan kontrol atas struktur seluruh data. Unsur khusus dari pohon disebut node akar pohon. Misalnya, jika satu simpul - simpul ini mengandung nilai 7 dengan pointer kiri dan kanan-anak nol - adalah satu-satunya nilai di pohon kami, maka ini akan menjadi simpul akar kami. Ini adalah awal dari pohon kami. Kita bisa melihat ini sedikit lebih jelas sekali kita mulai menambahkan node lebih untuk pohon kami. Mari saya menarik sebuah halaman baru. 

Sekarang kita akan menggambar pohon yang memiliki 7 pada akar, dan 3 dalam dari anak kiri, dan 9 dalam anak kanan. Sekali lagi, ini cukup sederhana. Kami punya 7, menggambar node untuk 3, sebuah node untuk 9, dan aku akan mengatur pointer kiri-anak 7 untuk menunjuk ke simpul yang mengandung 3, dan pointer kanan anak dari simpul yang mengandung 7 ke node yang mengandung 9. Sekarang, sejak 3 dan 9 tidak memiliki anak, kita akan mengatur semua pointer anak mereka untuk menjadi nol. Di sini, akar pohon kita sesuai dengan simpul yang berisi nomor 7. Anda dapat melihat bahwa jika semua yang kita miliki adalah pointer ke simpul akar, kita kemudian dapat berjalan melalui pohon dan mengakses kedua node anak - baik 3 dan 9. Tidak perlu untuk mempertahankan pointer ke setiap node tunggal pada pohon. Alright. Sekarang kita akan menambahkan node lain untuk diagram ini. Kita akan menambahkan node yang mengandung 6, dan kita akan menambahkan ini sebagai anak kanan dari simpul yang mengandung 3. Untuk melakukan itu, aku akan menghapus bahwa pointer nol dalam 3-node dan kawat itu untuk menunjuk ke simpul yang mengandung 6. Alright. 

Pada titik ini, mari kita membahas sedikit terminologi. Untuk memulai, alasan bahwa ini disebut pohon biner khususnya adalah bahwa ia memiliki dua pointer anak. Ada jenis lain dari pohon yang memiliki pointer anak lagi. Secara khusus, Anda melakukan 'mencoba' di Set Soal 5. Anda akan melihat bahwa dalam mencoba itu, Anda memiliki 27 pointer yang berbeda untuk anak-anak yang berbeda - satu untuk masing-masing dari 26 huruf dalam abjad Inggris, dan kemudian 27 untuk tanda kutip - sehingga, yang mirip dengan jenis pohon. Tapi di sini, karena biner itu, kita hanya memiliki dua pointer anak. 

Selain ini simpul akar yang kita bicarakan, kami juga telah melemparkan sekitar istilah 'anak'. Apa artinya untuk satu node menjadi anak node lain? Secara harfiah berarti bahwa node anak adalah anak dari node lain jika node lain memiliki salah satu pointer anaknya diatur untuk menunjuk ke simpul tersebut. Untuk menempatkan ini ke dalam istilah yang lebih konkret, jika 3 ditunjukkan oleh salah satu pointer anak 7, maka 3 adalah anak 7. Jika kita mencari tahu apa anak-anak dari 7 adalah - baik, kita melihat bahwa 7 memiliki pointer ke 3 dan pointer ke 9, jadi 9 dan 3 adalah anak-anak 7. Sembilan tidak memiliki anak karena anaknya pointer adalah null, dan 3 hanya memiliki satu anak, 6. Enam juga tidak memiliki anak karena kedua pointer nya adalah null, yang kita akan menarik sekarang. 

Selain itu, kita juga berbicara tentang orang tua dari node tertentu, dan ini adalah, seperti yang Anda harapkan, kebalikan dari deskripsi anak. Setiap node hanya memiliki satu orang tua - bukan dua seperti yang Anda harapkan dengan manusia. Misalnya, orang tua dari 3 adalah 7. Orang tua dari 9 juga 7, dan orang tua dari 6 adalah 3. Tidak banyak untuk itu. Kami juga memiliki istilah untuk berbicara tentang kakek-nenek dan cucu, dan lebih umumnya kita berbicara tentang nenek moyang dan keturunan dari node tertentu. Nenek moyang node - atau nenek moyang, lebih tepatnya, dari node - adalah semua node yang terletak di jalan dari akar ke simpul tersebut. Sebagai contoh, jika saya melihat 6 node, maka leluhur akan menjadi baik 3 dan 7. Nenek moyang dari 9, misalnya, - jika saya melihat 9 simpul - maka nenek moyang 9 hanya 7. Dan keturunan yang persis sebaliknya. Jika saya ingin melihat semua keturunan 7, maka saya harus melihat semua node di bawahnya. Jadi, saya memiliki 3, 9, dan 6 semua sebagai keturunan dari 7. 

Istilah terakhir yang kita akan berbicara tentang gagasan menjadi saudara kandung. Saudara - jenis mengikuti dari awal pada istilah-istilah keluarga - adalah node yang berada pada tingkat yang sama di pohon. Jadi, 3 dan 9 adalah saudara kandung karena mereka berada pada tingkat yang sama di pohon. Mereka berdua memiliki induk yang sama, 7. 6 tidak memiliki saudara kandung karena 9 tidak memiliki anak. Dan 7 tidak memiliki saudara kandung karena akar pohon kita, dan ada hanya pernah 1 root. Untuk 7 untuk memiliki saudara di sana harus menjadi simpul di atas 7. Ada akan menjadi orang tua dari 7, dalam hal ini 7 akan tidak lagi menjadi akar pohon. Kemudian orang tua baru 7 juga harus memiliki anak, dan anak yang kemudian akan menjadi saudara dari 7. 

Alright. Pindah. Ketika kita mulai diskusi kita dari pohon biner, kita berbicara tentang bagaimana kami akan menggunakannya untuk memperoleh keuntungan lebih baik array dan linked list. Dan cara kita akan melakukannya adalah dengan memesan properti. Kami mengatakan bahwa sebuah pohon biner yang memerintahkan, sesuai dengan spesifikasi, jika untuk setiap node di pohon kita, semua keturunannya di sebelah kiri - anak kiri dan semua keturunan anak kiri - memiliki nilai yang lebih rendah, dan semua node di sebelah kanan - anak kanan dan semua keturunan anak kanan itu - memiliki node lebih besar dari nilai node saat ini bahwa kita sedang melihat. Hanya untuk kesederhanaan, kita akan berasumsi bahwa tidak ada duplikasi node di pohon kita. Misalnya, di pohon ini kita tidak akan berurusan dengan kasus di mana kita memiliki nilai 7 pada akar  dan kemudian kita juga memiliki nilai 7 tempat lain di pohon. Dalam hal ini, Anda akan melihat bahwa pohon ini memang diperintahkan. Kami memiliki nilai 7 pada akar. Semuanya di sebelah kiri 7 - jika saya membatalkan semua tanda kecil di sini - semuanya ke kiri 7 - 3 dan 6 - nilai-nilai keduanya kurang dari 7, dan semuanya ke kanan - yang hanya 9 ini - lebih besar dari 7. 

Ini bukan satu-satunya pohon memerintahkan mengandung nilai-nilai, tapi mari kita menarik beberapa lagi dari mereka. Sebenarnya ada sejumlah cara yang bisa kita lakukan ini. Aku akan menggunakan singkat hanya untuk menjaga hal-hal sederhana di mana - bukannya menarik keluar seluruh kotak-dan-panah - Aku hanya akan menarik angka dan menambahkan panah menghubungkan mereka. Untuk memulai, kita hanya akan menulis pohon asli kami lagi di mana kami memiliki 7, dan kemudian 3, dan kemudian menunjuk 3 kembali ke kanan ke 6, dan 7 memiliki anak kanan itu 9. Alright. Apa cara lain yang kita bisa menulis pohon ini? Alih-alih memiliki 3 menjadi anak kiri dari 7, kita juga bisa memiliki 6 menjadi anak kiri dari 7, dan kemudian 3 menjadi anak kiri dari 6. Itu akan terlihat seperti pohon ini di sini di mana saya punya 7, kemudian 6, kemudian 3, dan 9 di sebelah kanan. Kami juga tidak harus memiliki 7 sebagai simpul akar kami. Kita juga bisa memiliki 6 sebagai simpul akar kami. Apa yang akan terlihat seperti? Jika kita akan mempertahankan properti memerintahkan, semuanya ke kiri dari 6 harus kurang dari itu. Hanya ada satu kemungkinan, dan itu 3. Tapi kemudian sebagai anak kanan dari 6, kita memiliki dua kemungkinan. Pertama, kita bisa memiliki 7 dan kemudian 9, atau kita bisa menggambar - seperti aku akan lakukan di sini - di mana kita memiliki 9 sebagai anak kanan dari 6, dan kemudian 7 sebagai anak kiri 9. 

Sekarang, 7 dan 6 adalah bukan nilai-nilai hanya mungkin untuk root. Kita juga bisa memiliki 3 berada di akar. Apa yang terjadi jika 3 adalah pada akar? Di sini, hal mendapatkan sedikit menarik. Tiga tidak memiliki nilai-nilai yang kurang dari itu, sehingga sisi kiri seluruh pohon itu hanya akan menjadi nol. Ada tidak akan menjadi apa pun di sana. Ke kanan, kita bisa daftar hal-hal dalam urutan. Kita bisa memiliki 3, kemudian 6, kemudian 7, kemudian 9. Atau, kita bisa melakukan 3, kemudian 6, kemudian 9, kemudian 7. Atau, kita bisa melakukan 3, kemudian 7, kemudian 6, kemudian 9. Atau, 3, 7 - sebenarnya tidak ada, kita tidak bisa melakukan lagi 7. Itulah salah satu hal yang kami di sana. Kita bisa melakukan 9, dan kemudian dari 9 bisa kita lakukan dan kemudian 6 7. Atau, kita bisa melakukan 3, kemudian 9, kemudian 7, dan kemudian 6. 

Satu hal yang menarik perhatian Anda ke sini adalah bahwa pohon-pohon yang sedikit aneh yang tampak. Secara khusus, jika kita melihat pada 4 pohon di sisi kanan - Saya akan mengitarinya, di sini - pohon-pohon ini terlihat hampir persis seperti linked list. Setiap node hanya memiliki satu anak, dan jadi kita tidak memiliki salah satu dari ini struktur pohon seperti yang kita lihat, misalnya,  di pohon satu satunya di sini di sebelah kiri bawah. Pohon-pohon ini sebenarnya disebut merosot pohon biner, dan kita akan berbicara tentang ini lebih di masa depan - terutama jika Anda pergi untuk mengambil kursus ilmu komputer lainnya. Pohon-pohon ini merosot. Mereka tidak sangat berguna karena, memang, struktur ini cocok  untuk pencarian kali mirip dengan linked list. Kami tidak bisa mengambil keuntungan dari memori tambahan - ini pointer ekstra - karena struktur kami yang buruk dengan cara ini. Daripada pergi dan menarik keluar pohon biner yang memiliki 9 pada akar, yang merupakan kasus terakhir yang kita akan memiliki, kita sebaliknya, pada saat ini, akan berbicara sedikit tentang istilah lainnya yang kita gunakan ketika berbicara tentang pohon, yang disebut ketinggian. 

Ketinggian pohon adalah jarak dari akar ke simpul paling-jauh, atau lebih tepatnya jumlah hop yang akan Anda harus membuat dalam rangka mulai dari akar dan kemudian berakhir di node paling jauh di pohon. Jika kita melihat beberapa pohon yang kita telah ditarik di sini, kita dapat melihat bahwa jika kita mengambil pohon ini di sudut kiri atas dan kita mulai pada 3, maka kita harus membuat 1 hop untuk sampai ke 6, sebuah hop kedua untuk sampai ke 7, dan hop ketiga untuk sampai ke 9. Jadi, ketinggian pohon ini adalah 3. Kita bisa melakukan latihan yang sama untuk pohon lain diuraikan dengan hijau ini, dan kita melihat bahwa tinggi dari semua pohon juga memang 3. Itu bagian dari apa yang membuat mereka merosot - bahwa tinggi mereka hanya satu kurang dari jumlah node di seluruh pohon. Jika kita melihat pohon lain yang dikelilingi dengan merah, di sisi lain, kita melihat bahwa yang paling jauh-node daun adalah 6 dan 9 - daun menjadi orang node yang tidak memiliki anak. Jadi, dalam rangka untuk mendapatkan dari node root baik 6 atau 9, kita harus membuat satu hop untuk sampai ke 7 dan kemudian hop kedua untuk sampai ke 9, dan juga, hanya hop kedua dari 7 untuk sampai ke 6. Jadi, ketinggian pohon ini di sini hanya 2. Anda dapat kembali dan melakukan itu untuk semua pohon-pohon lain yang kita bahas sebelumnya dimulai dengan 7 dan 6, dan Anda akan menemukan bahwa tinggi dari semua pohon-pohon juga 2. 

Alasan kami telah berbicara tentang memerintahkan pohon biner dan mengapa mereka keren karena Anda dapat mencari melalui mereka dalam cara yang sangat mirip dengan mencari lebih dari array diurutkan. Di sinilah kita berbicara tentang mendapatkan bahwa waktu pencarian ditingkatkan atas linked list sederhana. Dengan linked list - jika Anda ingin mencari elemen tertentu - Anda terbaik akan melakukan semacam pencarian linear di mana Anda mulai pada awal daftar dan hop satu-per-satu - satu node oleh satu node - melalui seluruh daftar sampai Anda menemukan apa pun yang Anda cari. Sedangkan, jika Anda memiliki sebuah pohon biner yang disimpan dalam format yang bagus, Anda benar-benar bisa mendapatkan lebih dari pencarian biner terjadi di mana Anda membagi dan menaklukkan dan pencarian melalui paruh tepat pohon di setiap langkah. Mari kita lihat bagaimana yang bekerja. 

Jika kita memiliki - lagi, akan kembali ke pohon asli kami - kita mulai pada 7, kami memiliki 3 di sebelah kiri, 9 di sebelah kanan, dan di bawah 3 yang kita miliki 6 tersebut. Jika kita ingin mencari nomor 6 di pohon ini, kita akan mulai dari akar. Kami akan membandingkan nilai yang kita cari, katakanlah 6, dengan nilai yang tersimpan dalam simpul yang kita sedang melihat, 7, menemukan bahwa 6 memang kurang dari 7, jadi kita akan bergerak ke kiri. Jika nilai 6 sudah lebih besar dari 7, kita akan sebaliknya pindah ke kanan. Karena kita tahu bahwa - karena struktur pohon biner memerintahkan kita - semua nilai kurang dari 7 akan disimpan di sebelah kiri 7, ada tidak perlu repot-repot mencari melalui sisi kanan pohon. Setelah kita bergerak ke kiri dan kami sekarang di node mengandung 3, kita bisa melakukan itu perbandingan yang sama lagi di mana kita membandingkan 3 dan 6. Dan kita menemukan bahwa sementara 6 - nilai yang kita cari - lebih besar dari 3, kita bisa pergi ke sisi kanan dari node yang mengandung 3. Tidak ada sisi kiri di sini, jadi kita bisa mengabaikan itu. Tapi kita hanya tahu bahwa karena kita sedang melihat pohon itu sendiri, dan kita dapat melihat bahwa pohon itu tidak memiliki anak. 

Hal ini juga cukup mudah untuk mencari 6 di pohon ini jika kita melakukannya diri sebagai manusia, tapi mari kita ikuti proses ini mekanis seperti komputer akan melakukan untuk benar-benar memahami algoritma. Pada titik ini, kita sekarang melihat sebuah simpul yang berisi 6, dan kami sedang mencari nilai 6, jadi, memang, kami telah menemukan simpul yang tepat. Kami menemukan nilai 6 di pohon kita, dan kita dapat menghentikan pencarian kami. Pada titik ini, tergantung pada apa yang terjadi, kita dapat mengatakan, ya, kami telah menemukan nilai 6, itu ada di pohon kami. Atau, jika kita berencana untuk memasukkan node atau melakukan sesuatu, kita bisa melakukan itu pada saat ini. 

Mari kita melakukan pencarian beberapa lebih hanya untuk melihat bagaimana ini bekerja. Mari kita lihat apa yang terjadi jika kita mencoba dan mencari nilai 10. Jika kita melihat ke atas nilai 10, kita akan mulai dari akar. Kita akan melihat bahwa 10 lebih besar dari 7, jadi kita akan bergerak ke kanan. Kita akan sampai ke 9 dan membandingkan 9 ke 10 dan melihat bahwa 9 memang kurang dari 10. Jadi sekali lagi, kita akan mencoba untuk bergerak ke kanan. Tapi pada titik ini, kita akan melihat bahwa kita berada di node null. Ada apa di sana. Tidak ada di mana 10 seharusnya. Di sinilah kita dapat melaporkan kegagalan - bahwa memang tidak 10 di atas pohon. Dan akhirnya, mari kita pergi melalui kasus di mana kita berusaha untuk mencari 1 di pohon. Hal ini mirip dengan apa yang terjadi jika kita melihat ke atas 10, kecuali bukannya pergi ke kanan, kita akan pergi ke kiri. Kita mulai di 7 dan melihat bahwa 1 adalah kurang dari 7, jadi kita bergerak ke kiri. Kami sampai ke 3 dan melihat bahwa 1 adalah kurang dari 3, sehingga sekali lagi kita mencoba untuk bergerak ke kiri. Pada titik ini kita memiliki node nol, sehingga sekali lagi kita dapat melaporkan kegagalan. 

Jika Anda ingin mempelajari lebih lanjut tentang pohon biner, ada sejumlah besar masalah kecil menyenangkan yang dapat Anda lakukan dengan mereka. Saya sarankan berlatih gambar keluar dari diagram ini satu-per-satu dan mengikuti melalui semua langkah-langkah yang berbeda, karena ini akan datang di super-handy tidak hanya ketika Anda melakukan set Huffman encoding masalah tetapi juga dalam program masa depan - hanya belajar bagaimana untuk menarik keluar struktur data dan berpikir melalui masalah dengan pena dan kertas atau, dalam hal ini, iPad dan stylus. 

Pada titik ini meskipun, kita akan melanjutkan untuk melakukan beberapa latihan coding dan benar-benar bermain dengan pohon-pohon biner dan melihat. Aku akan beralih kembali ke komputer saya. Untuk ini bagian dari bagian, daripada menggunakan CS50 CS50 Run atau Spaces, Aku akan menggunakan alat. 

Setelah bersama dengan spesifikasi Set Soal, Saya melihat bahwa aku harus membuka alat, pergi ke folder Dropbox saya, membuat folder bernama Bagian 7, dan kemudian membuat sebuah file yang bernama binary_tree.c. Di sini kita pergi. Aku punya alat sudah terbuka. Aku akan menarik terminal. Aku akan pergi ke folder Dropbox, membuat direktori bernama section7, dan melihat itu benar-benar kosong. Sekarang aku akan membuka binary_tree.c. Alright. Di sini kita pergi - file kosong. 

Mari kita kembali ke spesifikasi. Spesifikasi meminta untuk membuat definisi tipe baru untuk simpul pohon biner yang mengandung nilai-nilai int - seperti nilai-nilai yang kita menarik dalam diagram kami sebelum. Kita akan menggunakan boilerplate ini typedef yang kita lakukan di sini bahwa Anda harus mengenali dari Set Soal 5 - jika Anda melakukan cara tabel hash dari menaklukkan program ejaan. Anda juga harus mengenalinya dari bagian minggu lalu di mana kita berbicara tentang daftar terhubung. Kami telah mendapat typedef dari node struct, dan kami telah memberikan node ini struct ini nama node struct sebelumnya sehingga kita kemudian dapat merujuk ke sana karena kita akan ingin memiliki pointer struct simpul sebagai bagian dari struct kami, tapi kami sudah dikelilingi kemudian ini - atau lebih tepatnya, terlampir ini - dalam typedef sehingga, kemudian dalam kode, kita bisa merujuk pada struct ini hanya sebagai simpul bukan node struct. 

Ini akan menjadi sangat mirip dengan daftar definisi sendiri-linked yang kita lihat minggu lalu. Untuk melakukan hal ini, mari kita mulai dengan menuliskan boilerplate tersebut. Kita tahu bahwa kita harus memiliki nilai integer, jadi kita akan dimasukkan ke dalam nilai int, dan kemudian bukan hanya memiliki satu pointer ke elemen berikutnya - seperti yang kita lakukan dengan sendiri-linked list - kita akan memiliki pointer anak kiri dan kanan. Itu juga cukup sederhana - struct node anak * kiri; dan struct node anak * benar;. Cool. Yang tampak seperti awal yang cukup bagus. Mari kita kembali ke spesifikasi. 

Sekarang kita perlu mendeklarasikan variabel simpul * global untuk akar pohon. Kita akan membuat ini global yang sama seperti kami membuat pointer pertama dalam daftar kami terkait juga global. Ini adalah sehingga dalam fungsi yang kita tulis kita tidak harus tetap lewat di sekitar akar ini - meskipun kita akan melihat bahwa jika Anda ingin menulis fungsi rekursif, mungkin lebih baik untuk tidak bahkan lulus sekitar sebagai global di tempat pertama dan bukannya menginisialisasi secara lokal dalam fungsi utama Anda. Tapi, kami akan melakukannya secara global untuk memulai. Sekali lagi, kami akan memberikan beberapa ruang, dan aku akan menyatakan akar * simpul. Hanya untuk memastikan bahwa saya tidak meninggalkan uninitialized, aku akan mengatur itu sama dengan nol. Sekarang, dalam fungsi utama - yang kita akan menulis sangat cepat di sini - int main (int argc, const char * argv []) - dan aku akan mulai mendeklarasikan array argv saya sebagai const hanya agar saya tahu bahwa mereka argumen argumen bahwa aku mungkin tidak ingin mengubah. Jika saya ingin memodifikasi mereka aku mungkin harus membuat salinan dari mereka. Anda akan melihat ini banyak dalam kode. Tidak apa-apa baik cara. Tidak apa-apa untuk meninggalkan sebagai - menghilangkan const jika Anda ingin. Saya biasanya memasukkannya ke dalam hanya agar saya mengingatkan diri sendiri  bahwa saya mungkin tidak ingin memodifikasi argumen-argumen. 

Seperti biasa, aku akan kembali untuk memasukkan baris 0 pada akhir utama. Di sini, saya akan menginisialisasi simpul akar saya. Seperti berdiri sekarang, aku punya pointer yang diatur ke nol, sehingga itu menunjuk pada apa-apa. Dalam rangka untuk benar-benar mulai membangun node, Saya pertama kali perlu mengalokasikan memori untuk itu. Aku akan melakukannya dengan membuat memori di heap menggunakan malloc. Aku akan mengatur akar sama dengan hasil dari malloc, dan aku akan menggunakan operator sizeof untuk menghitung ukuran node. Alasan yang saya gunakan simpul sizeof sebagai lawan, mengatakan, melakukan sesuatu seperti ini - malloc (4 + 4 +4) atau malloc 12 - karena saya ingin kode saya untuk menjadi seperti yang kompatibel mungkin. Saya ingin bisa mengambil file ini. C, kompilasi pada alat, dan kemudian kompilasi pada 64-bit Mac - atau pada arsitektur yang sama sekali berbeda - dan saya ingin semua ini untuk bekerja sama. 

Jika saya membuat asumsi tentang ukuran variabel - ukuran int atau ukuran pointer - maka aku juga membuat asumsi tentang jenis arsitektur di mana kode saya berhasil dapat mengkompilasi ketika dijalankan. Selalu gunakan sizeof sebagai lawan manual menjumlahkan bidang struct. Alasan lain adalah bahwa ada juga mungkin bantalan bahwa kompilator menempatkan ke struct. Bahkan hanya menjumlahkan bidang individu bukanlah sesuatu yang Anda biasanya ingin lakukan, ya, hapus baris tersebut. Sekarang, untuk benar-benar menginisialisasi ini node root, Aku akan harus memasukkan nilai untuk masing-masing bidang yang berbeda. Misalnya, untuk nilai aku tahu aku ingin menginisialisasi ke 7, dan untuk saat ini aku akan mengatur anak kiri menjadi nol dan anak kanan juga menjadi nol. Great! Kami telah melakukan itu bagian dari spec. 

Spesifikasi turun di bagian bawah halaman 3 meminta saya untuk membuat tiga node - satu berisi 3, satu berisi 6, dan satu dengan 9 - dan kemudian kawat mereka sehingga terlihat persis seperti diagram pohon kita yang kita bicarakan sebelumnya. Mari kita lakukan itu cukup cepat di sini. Anda akan melihat benar-benar cepat bahwa aku akan mulai menulis sekelompok kode duplikat. Aku akan membuat * node dan aku akan menyebutnya tiga. Aku akan mengaturnya sama dengan malloc (sizeof (node)). Aku akan menetapkan tiga-> value = 3. Tiga -> left_child = NULL; tiga -> tepat _child = NULL; juga. Itu terlihat sangat mirip dengan menginisialisasi akar, dan itulah yang Aku akan lakukan jika saya mulai menginisialisasi 6 dan 9 juga. Saya akan melakukan yang benar-benar cepat di sini - sebenarnya, aku akan melakukan copy dan paste sedikit, dan memastikan bahwa saya - baik-baik saja.  Sekarang, saya sudah mendapatkannya disalin dan aku bisa pergi ke depan dan mengatur ini sama dengan 6. Anda dapat melihat bahwa ini mengambil beberapa waktu dan tidak super-efisien. Dalam hanya sedikit, kita akan menulis fungsi yang akan melakukan hal ini untuk kita. Saya ingin mengganti ini dengan 9, menggantikan dengan 6. 

Sekarang kita punya semua node kami dibuat dan diinisialisasi. Kami punya root ditetapkan sama dengan 7, atau mengandung nilai 7, kami simpul yang mengandung 3, simpul kami mengandung 6, dan simpul kami mengandung 9. Pada titik ini, yang harus kita lakukan adalah kawat semuanya. Alasan saya diinisialisasi semua pointer ke null hanya sehingga saya memastikan bahwa Saya tidak memiliki pointer uninitialized di sana oleh kecelakaan. Dan juga karena, pada saat ini, saya hanya harus benar-benar menghubungkan node satu sama lain - kepada orang-orang yang mereka benar-benar terhubung ke - Saya tidak harus melalui dan membuat Pastikan bahwa semua nulls berada di sana di tempat yang tepat. 

Mulai dari akar, saya tahu bahwa anak kiri akar adalah 3. Saya tahu bahwa anak kanan akar adalah 9. Setelah itu, satu-satunya anak lain yang saya telah meninggalkan khawatir tentang adalah anak kanan 3, yang adalah 6. Pada titik ini, semua terlihat cukup bagus. Kami akan menghapus beberapa baris. Sekarang semuanya terlihat cukup bagus. Mari kita kembali ke spesifikasi kami dan melihat apa yang harus kita lakukan selanjutnya. 

Pada titik ini, kita harus menulis sebuah fungsi yang disebut 'berisi' dengan prototipe dari 'dikandungnya bool (int value)'. Dan ini mengandung fungsi akan kembali benar  jika pohon yang ditunjuk oleh variabel akar global kami  mengandung nilai dilewatkan ke fungsi dan palsu sebaliknya. Mari kita pergi ke depan dan melakukan itu. Ini akan menjadi persis seperti pencarian yang kita lakukan dengan tangan pada iPad hanya sedikit lalu. Mari kita tampilannya kembali dalam sedikit dan gulir ke atas. Kita akan menempatkan fungsi ini tepat di atas fungsi utama kami sehingga kita tidak perlu melakukan apapun prototyping. Jadi, bool mengandung (int value). Di sana kami pergi. Ada deklarasi boilerplate kami. Hanya untuk memastikan bahwa ini akan mengkompilasi, Aku akan pergi ke depan dan hanya mengatur itu sama dengan return false. Saat fungsi ini tidak akan melakukan apa-apa dan selalu melaporkan bahwa nilai yang kita cari tidak ada di dalam pohon. 

Pada titik ini, itu mungkin ide yang baik - karena kita telah menulis sejumlah kode dan kami bahkan belum mencoba mengujinya belum - untuk memastikan bahwa semuanya mengkompilasi. Ada beberapa hal yang harus kita lakukan untuk memastikan bahwa ini benar-benar akan mengkompilasi. Pertama, melihat apakah kita telah menggunakan fungsi-fungsi dalam perpustakaan yang kita belum disertakan. Fungsi kami telah digunakan sejauh ini malloc, dan kemudian kita juga telah menggunakan jenis ini - jenis ini tidak standar yang disebut 'bool' - yang termasuk dalam file header standar bool. Kita pasti ingin memasukkan bool.h standar untuk tipe bool, dan kami juga ingin # include lib.h standar untuk perpustakaan standar yang mencakup malloc, dan bebas, dan semua itu. Jadi, zoom out, kita akan berhenti. Mari kita mencoba dan memastikan bahwa ini benar-benar melakukan kompilasi. Kita melihat bahwa hal itu, jadi kami berada di jalur yang benar. 

Mari kita membuka binary_tree.c lagi. Ini mengkompilasi. Mari kita turun dan memastikan bahwa kami memasukkan beberapa panggilan ke fungsi yang dikandungnya kami - hanya untuk memastikan bahwa itu semua baik dan bagus. Sebagai contoh, ketika kita melakukan beberapa pencarian di pohon kami sebelumnya, kami mencoba untuk mencari nilai-nilai 6, 10, dan 1, dan kita tahu bahwa 6 berada di pohon, 10 tidak di pohon, dan 1 tidak di pohon baik. Mari kita menggunakan panggilan sampel tersebut sebagai cara untuk mengetahui apakah atau tidak dikandungnya fungsi kita bekerja. Untuk melakukan itu, saya akan menggunakan fungsi printf, dan kita akan mencetak hasil dari panggilan untuk mengandung. Aku akan dimasukkan ke dalam string "mengandung (% d) = karena  kita akan pasang di nilai bahwa kita akan mencari, dan =% s \ n "dan menggunakannya sebagai format string kami. Kami hanya akan melihat - secara harfiah mencetak di layar - apa yang tampak seperti pemanggilan fungsi. Hal ini tidak benar-benar fungsi panggil.  Ini hanyalah sebuah string yang dirancang untuk terlihat seperti pemanggilan fungsi. 

Sekarang, kita akan pasang di nilai. Kami akan mencoba mengandung pada 6, dan kemudian apa yang akan kita lakukan di sini adalah menggunakan operator ternary. Mari kita lihat - berisi 6 - jadi, sekarang aku sudah mengandung 6 dan jika mengandung 6 adalah benar, string yang akan kita kirim ke karakter format% s akan menjadi string "true". Mari kita gulir lebih sedikit. Jika tidak, kami ingin mengirim string "palsu" jika mengandung 6 returns false. Ini adalah sedikit konyol-tampak, tapi saya pikir saya mungkin juga menggambarkan apa operator terner tampak seperti karena kita belum melihat itu untuk sementara. Ini akan menjadi cara yang baik, berguna untuk mencari tahu apakah yang dikandungnya fungsi kita bekerja. Aku akan gulir kembali ke kiri, dan aku akan copy dan paste baris ini beberapa kali. Itu mengubah beberapa nilai sekitar, jadi ini akan menjadi 1, dan ini akan menjadi 10. 

Pada titik ini kita punya fungsi yang dikandungnya yang bagus. Kami punya beberapa tes, dan kita akan melihat apakah semua ini bekerja. Pada titik ini kita telah menulis beberapa kode lagi. Waktu untuk berhenti keluar dan memastikan bahwa semuanya masih mengkompilasi. Berhenti keluar, dan sekarang mari kita mencoba membuat pohon biner lagi. Yah, sepertinya kita punya kesalahan, dan kita sudah mendapat ini secara eksplisit menyatakan fungsi perpustakaan printf. Sepertinya kita perlu masuk dan # include standardio.h. Dan dengan itu, segala sesuatu harus mengkompilasi. Kita semua baik. Sekarang mari kita coba jalankan pohon biner dan melihat apa yang terjadi. Di sini kita, / binary_tree., dan kita melihat bahwa, seperti yang kita harapkan - karena kita belum diimplementasikan mengandung belum, atau lebih tepatnya, kita baru saja dimasukkan ke dalam return false - kita melihat bahwa itu hanya kembali palsu untuk mereka semua, jadi itu semua bekerja untuk sebagian besar cukup baik. 

Mari kita kembali dan benar-benar menerapkan mengandung pada saat ini. Aku akan gulir ke bawah, memperbesar, dan - ingat, algoritma yang kita gunakan adalah bahwa kita mulai pada simpul akar dan kemudian pada setiap simpul yang kita hadapi, kita melakukan perbandingan, dan berdasarkan perbandingan yang kita pindahkan ke anak kiri atau ke anak kanan. Ini akan terlihat sangat mirip dengan kode pencarian biner yang kita tulis sebelumnya dalam istilah. Ketika kita memulai, kita tahu bahwa kita ingin berpegang pada node saat ini bahwa kita sedang melihat, dan simpul saat ini akan diinisialisasi ke simpul akar. Dan sekarang, kita akan terus melalui pohon, dan ingat bahwa kondisi kita menghentikan -  ketika kita benar-benar bekerja melalui contoh dengan tangan - adalah ketika kami mengalami simpul null, tidak ketika kita melihat seorang anak nol, tetapi ketika kita benar-benar pindah ke sebuah simpul di pohon dan menemukan bahwa kami berada di node null. Kita akan iterate sampai skr tidak sama dengan nol. Dan apa yang akan kita lakukan? Kita akan menguji apakah (skr -> value == value), maka kita tahu bahwa kita telah benar-benar menemukan node yang kita cari. Jadi di sini, kita bisa kembali benar. Jika tidak, kita ingin melihat apakah atau tidak nilai kurang dari nilai. Jika nilai node saat ini kurang dari nilai yang kita cari, kita akan bergerak ke kanan. Jadi, skr = skr -> right_child, dan sebaliknya, kita akan bergerak ke kiri. skr = skr -> left_child;. Cukup sederhana. 

Anda mungkin mengenali loop yang terlihat sangat mirip dengan ini dari biner pencarian awal istilah, kecuali kemudian kami berurusan dengan rendah, menengah, dan tinggi. Di sini, kita hanya harus melihat nilai saat ini, sehingga sangat bagus dan sederhana. Mari kita pastikan kode ini bekerja. Pertama, pastikan mengkompilasi. Sepertinya tidak. Mari kita coba menjalankannya. Dan memang, ia akan mencetak segala sesuatu yang kami harapkan. Ia menemukan 6 di pohon, tidak menemukan 10 karena 10 tidak di pohon, dan tidak menemukan 1 baik karena 1 juga tidak di pohon. Cool stuff. 

Alright. Mari kita kembali ke spesifikasi kami dan melihat apa yang berikutnya. Sekarang, ia ingin menambahkan node lagi ke pohon kami. Ia ingin menambah 5, 2, dan 8, dan pastikan bahwa kami berisi kode masih bekerja seperti yang diharapkan. Mari kita lakukan itu. Pada titik ini, daripada melakukan hal itu mengganggu copy dan paste lagi, mari kita menulis fungsi untuk benar-benar menciptakan sebuah node. Jika kita scroll ke bawah sampai ke utama, kita melihat bahwa kita sudah melakukan ini sangat mirip kode berulang-ulang setiap kali kita ingin membuat sebuah node. 

Mari kita menulis fungsi yang benar-benar akan membangun simpul bagi kita dan mengembalikannya. Aku akan menyebutnya build_node. Aku akan membangun sebuah node dengan nilai tertentu. Zoom di sini. Hal pertama yang saya akan lakukan adalah benar-benar membuat ruang untuk node di heap. Jadi, simpul * n = malloc (sizeof (node)), n -> value = value; dan kemudian di sini, aku hanya akan menginisialisasi semua bidang untuk menjadi nilai-nilai yang sesuai. Dan di akhir, kami akan kembali simpul kami. Alright. Satu hal yang perlu diperhatikan adalah bahwa fungsi ini di sini akan kembali pointer ke memori yang telah dialokasikan tumpukan-. Apa yang baik tentang ini adalah bahwa node ini sekarang - kita harus mendeklarasikan di heap karena jika kita menyatakan itu di stack kita tidak akan mampu melakukannya dalam fungsi ini seperti ini. Memori yang akan keluar dari ruang lingkup dan akan valid jika kita mencoba untuk mengaksesnya nanti. Karena kita menyatakan tumpukan-dialokasikan memori, kita akan harus mengurus membebaskan nanti untuk program kami untuk tidak bocor memori apapun. Kami sudah punting pada bahwa untuk segala sesuatu yang lain dalam kode hanya untuk mudahnya pada saat itu, tetapi jika Anda pernah menulis fungsi yang terlihat seperti ini di mana Anda punya - beberapa menyebutnya malloc atau realloc dalam - Anda ingin memastikan bahwa Anda menempatkan semacam komentar di sini yang mengatakan, hey, kau tahu, mengembalikan node tumpukan-dialokasikan diinisialisasi dengan nilai berlalu-in. Dan kemudian Anda ingin memastikan bahwa Anda masukkan ke dalam semacam catatan yang mengatakan pemanggil harus membebaskan memori dikembalikan. Dengan begitu, jika seseorang pernah berjalan dan menggunakan fungsi itu, mereka tahu bahwa apa pun yang mereka dapatkan kembali dari fungsi yang di beberapa titik perlu dibebaskan. 

Dengan asumsi bahwa semuanya baik-baik dan baik di sini, kita bisa turun ke dalam kode kita dan menggantikan semua baris di sini dengan panggilan ke fungsi simpul kami membangun. Mari kita lakukan yang benar-benar cepat. Bagian yang kita tidak akan menggantikan adalah bagian ini di sini di bagian bawah di mana kita benar-benar memasang sebuah node untuk menunjuk satu sama lain, karena kita tidak bisa dilakukan di fungsi kita. Tapi, mari kita lakukan root = build_node (7), simpul * = build_node tiga (3); simpul * = build_node enam (6), simpul * sembilan = build_node (9);. Dan sekarang, kami juga ingin menambahkan node untuk - simpul * = build_node lima (5), simpul delapan * = build_node (8); dan apa node lainnya? Mari kita lihat di sini. Kami ingin juga menambahkan 2 - simpul * dua = build_node (2);. Alright. Pada titik ini, kita tahu bahwa kita punya 7, 3, 9, dan 6 semua kabel dengan tepat, tapi bagaimana dengan 5, 8, dan 2? Untuk menjaga semuanya dalam urutan yang tepat, kita tahu bahwa anak kanan ketiga adalah 6. Jadi, jika kita akan menambahkan 5, 5 juga termasuk dalam sisi kanan pohon yang 3 adalah akar, jadi 5 milik sebagai anak kiri 6. Kita bisa melakukan hal ini dengan mengatakan, enam -> left_child = lima; dan kemudian 8 milik sebagai anak kiri dari 9, maka sembilan -> left_child = delapan; dan kemudian 2 adalah anak kiri dari 3, sehingga kita bisa melakukan itu di sini - engkau -> left_child = dua;. Jika Anda tidak cukup mengikuti bersama dengan itu, saya sarankan Anda menariknya keluar sendiri. 

Alright. Mari kita menyimpan. Mari kita pergi keluar dan pastikan mengkompilasi, dan kemudian kita dapat menambahkan panggilan kami yang dikandungnya. Sepertinya semuanya masih mengkompilasi. Mari kita masuk dan menambahkan beberapa berisi panggilan. Sekali lagi, aku akan melakukan sedikit copy dan paste. Sekarang mari kita mencari 5, 8, dan 2. Alright. Mari kita pastikan bahwa ini semua terlihat baik masih. Great! Simpan dan berhenti. Sekarang mari kita membuat, kompilasi, dan sekarang mari kita jalankan. Dari hasil, sepertinya semuanya bekerja hanya bagus dan baik. Great! Jadi sekarang kita punya dikandungnya kami fungsi ditulis. Mari kita lanjutkan dan mulai bekerja pada cara memasukkan node ke pohon karena, seperti yang kita lakukan sekarang juga, hal ini tidak sangat cantik. 

Jika kita kembali ke spesifikasi, itu meminta kita untuk menulis sebuah fungsi yang disebut masukkan - lagi, mengembalikan bool untuk apakah atau tidak kita benar-benar bisa memasukkan node ke pohon - dan kemudian nilai untuk memasukkan ke dalam pohon itu ditetapkan sebagai argumen hanya untuk fungsi insert kami. Kami akan mengembalikan true jika kita memang bisa memasukkan nilai yang mengandung simpul dalam pohon, yang berarti bahwa kita, satu, memiliki memori yang cukup, dan kemudian dua, simpul yang tidak sudah ada di pohon sejak - ingat, kita tidak akan memiliki nilai ganda di pohon, hanya untuk membuat hal-hal sederhana. Alright. Kembali ke kode. Membukanya. Memperbesar sedikit, kemudian gulir ke bawah. Mari kita menempatkan fungsi insert tepat di atas dikandungnya. Sekali lagi, itu akan disebut insert bool (int value). Berikan sedikit lebih banyak ruang, dan kemudian, sebagai default, mari kita dimasukkan ke dalam return false di akhir. Sekarang turun di bawah, mari kita pergi ke depan dan bukannya secara manual membangun node di utama diri kita sendiri dan kabel mereka untuk menunjuk satu sama lain seperti yang kita lakukan, kita akan bergantung pada fungsi insert kami untuk melakukan itu. Kami tidak akan bergantung pada fungsi insert kami untuk membangun seluruh pohon dari awal dulu, melainkan kita akan menyingkirkan garis - kami komentari baris berikut - yang membangun node 5, 8, dan 2. Dan sebagai gantinya, kami akan memasukkan panggilan ke fungsi insert kami untuk memastikan bahwa benar-benar bekerja. Di sini kita pergi. 

Sekarang kita sudah komentar baris ini. Kami hanya memiliki 7, 3, 9, dan 6 di pohon kami pada saat ini. Untuk memastikan bahwa ini semua bekerja, kita bisa memperkecil, membuat pohon biner kita, menjalankannya, dan kita dapat melihat bahwa mengandung sekarang mengatakan kepada kita bahwa kita benar-benar benar - 5, 8, dan 2 tidak lagi di pohon. Kembali ke dalam kode, dan bagaimana kita akan memasukkan? Ingat apa yang kita lakukan ketika kita benar-benar memasukkan 5, 8, dan 2 sebelumnya. Kami bermain bahwa permainan Plinko mana kita mulai pada akar, turun satu pohon oleh satu per satu sampai kami menemukan kesenjangan yang tepat, dan kemudian kita kabel di node di tempat yang tepat. Kita akan melakukan hal yang sama. Hal ini pada dasarnya seperti menulis kode yang kita digunakan dalam mengandung fungsi untuk menemukan tempat di mana node seharusnya, dan kemudian kita hanya akan memasukkan node di sana. Mari kita mulai melakukan hal itu. 

Jadi kita memiliki simpul * skr = root, kita hanya akan mengikuti berisi kode sampai kita menemukan bahwa itu tidak cukup bekerja untuk kita. Kita akan pergi melalui pohon sementara elemen saat ini tidak null, dan jika kita menemukan nilai yang skr adalah sama dengan nilai yang kita mencoba untuk memasukkan - baik, ini adalah salah satu kasus di mana kita tidak bisa benar-benar memasukkan node ke pohon karena ini berarti kita memiliki nilai duplikat. Di sini kita benar-benar akan kembali palsu. Sekarang, lain jika nilai skr adalah kurang dari nilai, sekarang kita tahu bahwa kita bergerak ke kanan  karena nilai termasuk dalam bagian kanan dari pohon skr. Jika tidak, kita akan bergerak ke kiri. Itu pada dasarnya berfungsi dikandungnya kami di sana. 

Pada titik ini, setelah kami telah menyelesaikan ini loop sementara, pointer skr kita akan menunjuk ke null jika fungsi tersebut belum dikembalikan. Oleh karena itu kita memiliki skr di tempat di mana kita ingin menyisipkan simpul baru. Apa yang masih harus dilakukan adalah untuk benar-benar membangun node baru, yang bisa kita lakukan cukup mudah. Kita dapat menggunakan super-praktis kami fungsi simpul membangun, dan sesuatu yang kita tidak lakukan sebelumnya - kita hanya semacam mengambil untuk diberikan, tapi sekarang kita akan melakukan hanya untuk memastikan - kita akan menguji untuk memastikan bahwa nilai yang dikembalikan oleh node baru sebenarnya tidak nol, karena kita tidak ingin mulai mengakses memori yang jika nol. Kita dapat menguji untuk memastikan bahwa node baru tidak sama dengan nol. Atau sebaliknya, kita hanya bisa melihat apakah itu benar-benar nol, dan jika itu adalah nol, maka kita hanya dapat return false awal. 

Pada titik ini, kita harus kawat simpul baru ke dalam tempat yang sesuai dalam pohon. Jika kita melihat kembali utama dan di mana kami benar-benar kabel nilai sebelumnya, kita melihat bahwa cara kita melakukan hal itu ketika kita ingin menempatkan 3 di pohon yang kita diakses anak kiri akar. Ketika kita menempatkan 9 di pohon, kami harus mengakses anak kanan dari akar. Kami harus memiliki pointer ke orang tua dalam rangka untuk menempatkan nilai baru ke dalam pohon. Bergulir kembali untuk memasukkan, itu tidak akan cukup bekerja di sini karena kita tidak memiliki pointer orangtua. Apa yang kita ingin bisa lakukan adalah, pada saat ini, memeriksa nilai orang tua dan melihat - baik, gosh, jika nilai orangtua kurang dari nilai saat ini, maka anak kanan orangtua harus menjadi simpul baru; jika tidak, anak kiri induk harus menjadi simpul baru. Tapi, kita tidak memiliki pointer orangtua belum cukup. 

Untuk mendapatkannya, kita benar-benar akan harus melacak itu seperti yang kita pergi melalui pohon dan menemukan tempat yang sesuai dalam lingkaran di atas kami. Kita bisa melakukannya dengan menggulir kembali ke atas fungsi insert kami dan pelacakan variabel lain disebut pointer orangtua. Kita akan mengaturnya sama dengan null awalnya, dan kemudian setiap kali kita pergi melalui pohon, kita akan mengatur pointer orangtua untuk mencocokkan pointer saat ini. Set orangtua sama dengan skr. Dengan cara ini, setiap kali kita pergi melalui, kita akan memastikan bahwa sebagai pointer saat akan bertambah pointer orangtua mengikutinya - hanya satu tingkat lebih tinggi dari pointer saat ini di pohon. Itu semua terlihat cukup bagus. 

Saya pikir satu hal yang kita akan ingin menyesuaikan ini membangun simpul nol kembali. Dalam rangka untuk mendapatkan membangun simpul untuk benar-benar berhasil mengembalikan null, kita harus memodifikasi kode tersebut, karena di sini, kita tidak pernah diuji untuk memastikan bahwa malloc kembali pointer yang valid. Jadi, jika (n = NULL!), Kemudian - jika malloc kembali pointer yang valid, maka kita akan menginisialisasi itu; jika tidak, kita hanya akan kembali dan itu akan berakhir kembali nol bagi kita. Sekarang semua terlihat cukup bagus. Mari kita pastikan ini benar-benar mengkompilasi. Membuat pohon biner, dan oh, kami punya beberapa hal terjadi di sini. 

Kami punya sebuah deklarasi implisit dari fungsi membangun simpul. Sekali lagi, dengan kompiler, kita akan mulai dari atas. Apa yang harus maksud adalah bahwa aku menelepon membangun simpul sebelum aku benar-benar menyatakan itu. Mari kita kembali ke kode benar-benar cepat. Gulir ke bawah, dan tentu saja, fungsi insert saya dinyatakan atas fungsi simpul membangun, tapi aku mencoba untuk menggunakan membangun simpul dalam insert. Aku akan masuk dan copy - dan kemudian paste cara membangun simpul fungsi di sini di bagian atas. Dengan begitu, mudah-mudahan yang akan bekerja. Mari kita memberikan ini lain pergi. Sekarang semuanya mengkompilasi. Semua baik. 

Tapi pada saat ini, kita belum benar-benar disebut fungsi insert kami. Kita hanya tahu bahwa itu mengkompilasi, jadi mari kita masuk dan menaruh beberapa panggilan masuk Mari kita melakukan itu dalam fungsi utama kami. Di sini, kami komentar 5, 8, dan 2, dan kemudian kita tidak kawat mereka di sini. Mari kita membuat beberapa panggilan untuk memasukkan, dan mari kita juga menggunakan jenis yang sama hal-hal yang kita digunakan ketika kita membuat panggilan ini printf untuk memastikan bahwa segala sesuatu tidak bisa dimasukkan dengan benar. Aku akan copy dan paste, dan bukannya mengandung kita akan melakukan insert. Dan bukannya 6,, 10 dan 1, kita akan menggunakan 5, 8, dan 2. Ini diharapkan harus memasukkan 5, 8, dan 2 ke atas pohon. Kompilasi. Semua baik. Sekarang kita benar-benar akan menjalankan program kami. 

Semuanya kembali palsu. Jadi, 5, 8, dan 2 tidak pergi, dan sepertinya yang dikandungnya tidak menemukan mereka baik. Apa yang terjadi? Mari kita zoom out. Masalah pertama adalah bahwa insert tampaknya kembali palsu, dan tampaknya seperti itu karena kami meninggalkan panggilan return false kami, dan kita tidak pernah benar-benar kembali benar. Kita dapat mengatur bahwa sampai. Masalah kedua adalah, sekarang bahkan jika kita lakukan - menyimpan, keluar ini, menjalankan make lagi, memilikinya mengkompilasi, kemudian jalankan - kita melihat bahwa sesuatu yang lain terjadi di sini. The 5, 8, dan 2 masih tidak pernah ditemukan di pohon. Jadi, apa yang terjadi? 

Mari kita lihat ini dalam kode. Mari kita lihat apakah kita bisa mengetahui ini. Kita mulai dengan orangtua tidak menjadi nol. Kami mengatur pointer saat ini sama dengan pointer akar, dan kita akan bekerja dengan cara kami turun melalui pohon. Jika node saat ini tidak nol, maka kita tahu bahwa kita bisa bergerak ke bawah sedikit. Kami menetapkan pointer induk kami untuk menjadi sama dengan pointer saat ini, memeriksa nilai - jika nilai yang sama kami kembali palsu. Jika nilai kurang kami pindah ke kanan; jika tidak, kami pindah ke kiri. Kemudian kita membangun node. Saya akan memperbesar sedikit. Dan di sini, kita akan mencoba untuk kawat sampai nilai-nilai yang sama. Apa yang terjadi? Mari kita lihat apakah kemungkinan Valgrind dapat memberi kita petunjuk. 

Saya ingin menggunakan Valgrind Valgrind hanya karena benar-benar cepat berjalan dan memberitahu Anda jika ada kesalahan memori. Ketika kita menjalankan Valgrind pada kode, karena Anda dapat melihat hit here--Valgrind./binary_tree--and benar masuk. Anda lihat bahwa kita tidak memiliki kesalahan memori, sehingga terlihat seperti semuanya baik-baik saja sejauh ini. Kami memiliki kebocoran memori tertentu, yang kita tahu, karena kita tidak terjadi untuk membebaskan salah satu node kami. Mari kita coba jalankan GDB untuk melihat apa yang sebenarnya terjadi. Kami akan melakukan gdb / binary_tree.. Ini boot up baik-baik saja. Mari kita menetapkan titik istirahat di masukkan. Mari kita jalankan. Sepertinya kita tidak pernah benar-benar disebut insert. Sepertinya masalahnya hanya itu ketika saya berubah di sini di utama - semua panggilan printf dari mengandung - Aku tidak pernah benar-benar berubah ini untuk memanggil insert. Sekarang mari kita mencobanya. Mari kita kompilasi. Semua tampak baik di sana. Sekarang mari kita coba menjalankannya, melihat apa yang terjadi. Alright! Semuanya terlihat cukup baik di sana. 

Hal terakhir untuk berpikir tentang adalah, apakah ada kasus tepi apapun untuk menyisipkan ini? Dan ternyata, baik, salah satu ujung kasus yang selalu menarik untuk berpikir tentang adalah, apa yang terjadi jika pohon Anda kosong dan Anda memanggil fungsi ini insert? Apakah akan berhasil? Nah, mari kita mencobanya. - Binary_tree c -. Cara kita akan menguji ini, kita akan pergi ke fungsi utama kami, dan bukannya kabel node ini sampai seperti ini, kita hanya akan komentar pada seluruh hal, dan bukannya kabel sampai node diri kita sendiri, kita benar-benar bisa hanya pergi ke depan dan menghapus semua ini. Kita akan membuat segalanya panggilan untuk menyisipkan. Jadi, mari kita lakukan - bukan 5, 8, dan 2, kita akan memasukkan 7, 3, dan 9. Dan kemudian kita juga akan ingin memasukkan 6 juga. Simpan. Keluar. Membuat pohon biner. Semuanya mengkompilasi. Kami hanya bisa menjalankannya seperti dan melihat apa yang terjadi, tapi itu juga akan menjadi sangat penting untuk memastikan bahwa kita tidak memiliki kesalahan memori, karena ini adalah salah satu kasus tepi kita yang kita ketahui. 

Mari kita pastikan bahwa ia bekerja dengan baik di bawah Valgrind, yang akan kita lakukan dengan hanya menjalankan Valgrind / binary_tree.. Sepertinya kita memang memiliki satu kesalahan dari satu konteks - kita memiliki kesalahan segmentasi. Apa yang terjadi? Valgrind sebenarnya memberitahu kita di mana itu. Perkecil sedikit. Sepertinya itu terjadi dalam fungsi insert kami, di mana kita memiliki membaca valid ukuran 4 di insert, baris 60. Mari kita kembali dan melihat apa yang terjadi di sini. Perkecil benar-benar cepat. Saya ingin memastikan bahwa ia tidak pergi ke tepi layar sehingga kita bisa melihat segala sesuatu. Menarik bahwa dalam sedikit. Alright. Gulir ke bawah, dan masalahnya adalah di sini. Apa yang terjadi jika kita turun dan node saat ini kami sudah nol, simpul induk kami adalah null, jadi jika kita melihat ke atas di bagian paling atas, di sini - jika ini while loop tidak pernah benar-benar melaksanakan karena nilai kami saat ini adalah null - root adalah null sehingga skr null - maka orang tua kami tidak pernah akan diatur ke skr atau nilai yang valid, jadi, orang tua juga akan nol. Kita harus ingat untuk memeriksa untuk itu pada saat kita sampai ke sini, dan kami mulai mengakses nilai orangtua. Jadi, apa yang terjadi? Nah, jika orang tua adalah null - if (parent == NULL) - maka kita tahu bahwa tidak boleh ada apa pun di pohon. Kita harus mencoba untuk memasukkannya pada akar. Kita dapat melakukannya dengan hanya menetapkan akar sama dengan node baru. Kemudian pada titik ini, kita tidak benar-benar ingin pergi melalui hal-hal lainnya. Sebaliknya, di sini, kita bisa melakukan keduanya dengan yang lain-jika-lain, atau kita bisa menggabungkan semuanya di sini di lain, tapi di sini kita hanya akan menggunakan lain dan melakukannya dengan cara itu. Sekarang, kita akan menguji untuk memastikan bahwa orang tua kami tidak null sebelum kemudian benar-benar mencoba untuk mengakses bidangnya. Hal ini akan membantu kita menghindari kesalahan segmentasi. Jadi, kita berhenti, zoom out, kompilasi, jalankan. 

Tidak ada kesalahan, tapi kami masih memiliki banyak kebocoran memori karena kita tidak membebaskan salah satu node kami. Tapi, jika kita pergi di sini dan kami melihat cetakan kami, kita melihat bahwa, baik, sepertinya semua sisipan kami kembali benar, yang baik. Menyisipkan semua benar, dan kemudian dikandungnya sesuai panggilan juga benar. 

Good job! Sepertinya kita telah berhasil ditulis insert. Itu semua yang kita miliki untuk Set Keterangan minggu ini Masalah. Salah satu tantangan yang menyenangkan untuk berpikir tentang adalah bagaimana Anda benar-benar akan masuk dan bebas dari semua node dalam pohon ini. Kita bisa melakukannya dengan sejumlah cara yang berbeda, tapi aku akan meninggalkan terserah kepada Anda untuk bereksperimen, dan sebagai tantangan yang menyenangkan, mencoba dan pastikan bahwa Anda dapat memastikan bahwa laporan Valgrind kembali tidak ada kesalahan dan tidak ada kebocoran. 

Good luck pada minggu ini set coding masalah Huffman, dan kita akan melihat Anda minggu depan! [CS50.TV]