[Powered by Google Translate] [Bagian 7: Lebih Nyaman]
[Rob Bowden] [Harvard University]
[Ini adalah CS50] [CS50.TV]
Baiklah. Jadi seperti saya katakan di email saya,
ini akan menjadi bagian biner-pohon-intensif.
Tapi ada tidak banyak pertanyaan.
Jadi kita akan mencoba dan menarik keluar setiap pertanyaan
dan pergi ke detail menyakitkan semua cara terbaik untuk melakukan sesuatu.
Jadi tepat di awal, kita pergi melalui gambar sampel pohon biner dan barang-barang.
Jadi di sini, "Ingatlah bahwa pohon biner memiliki node sama dengan linked list,
kecuali bukan satu pointer ada dua: satu untuk 'anak' kiri
dan satu untuk 'anak' yang tepat. "
Jadi pohon biner adalah seperti sebuah linked list,
kecuali struct akan memiliki dua pointer.
Ada pohon trinary, yang akan memiliki tiga pointer,
ada N-ary pohon, yang hanya memiliki pointer generik
yang kemudian harus malloc cukup besar untuk memiliki
cukup pointer untuk semua anak-anak yang mungkin.
Jadi pohon biner kebetulan memiliki sejumlah konstan dua.
Jika Anda ingin, Anda dapat memberikan daftar link sebagai pohon unary,
tapi saya tidak berpikir siapa pun menyebutnya itu.
"Gambarkan diagram kotak-dan-panah dari simpul pohon biner
mengandung nomor favorit Nate, 7, di mana setiap anak adalah null pointer. "
Jadi iPad modus.
>> Ini akan menjadi cukup sederhana.
Kami hanya akan memiliki sebuah node, saya akan menggambar sebagai persegi.
Dan aku akan menarik nilai-nilai di sini.
Jadi nilai akan masuk di sini,
dan kemudian turun di sini kita akan memiliki pointer kiri di sebelah kiri dan pointer tepat di sebelah kanan.
Dan itu sangat banyak sehingga konvensi untuk menyebutnya kiri dan kanan, nama pointer.
Kedua hal ini akan menjadi nol.
Itu hanya akan menjadi nol, dan itu hanya akan menjadi nol.
Oke. Jadi kembali ke sini.
"Dengan linked list, kita hanya harus menyimpan pointer
ke node pertama dalam daftar untuk mengingat linked list keseluruhan, atau seluruh daftar.
Demikian juga, dengan pohon-pohon, kita hanya perlu menyimpan pointer
ke node tunggal untuk mengingat seluruh pohon.
Simpul ini calle 'root' dari pohon.
Membangun diagram Anda dari sebelumnya atau menggambar yang baru
sedemikian rupa sehingga Anda memiliki gambaran kotak-dan-panah dari pohon biner
dengan nilai 7, kemudian 3 di sebelah kiri,
kemudian 9 di sebelah kanan, dan kemudian 6 di sebelah kanan dari 3. "
Mari kita lihat apakah saya bisa mengingat semua itu dalam kepalaku.
Jadi ini akan menjadi akar kami di sini.
Kami akan memiliki beberapa pointer di suatu tempat, sesuatu yang kita akan menelepon akar,
dan itu menunjuk ke orang ini.
Sekarang untuk membuat node baru,
apa yang kita miliki, 3 di sebelah kiri?
Jadi node baru dengan 3, dan awalnya poin nol.
Saya hanya akan menempatkan N.
Sekarang kita ingin membuat yang pergi ke kiri 7.
Jadi kita mengubah pointer ini untuk sekarang menunjukkan orang ini.
Dan kami melakukan hal yang sama. Kami ingin 9 di sini
yang awalnya hanya mengatakan nol.
Kita akan mengubah pointer, arahkan ke 9,
dan sekarang kami ingin menempatkan 6 di sebelah kanan 3.
Jadi itu akan - membuat 6.
Dan pria yang akan mengarahkan sana.
Oke. Jadi itu semua itu meminta kita untuk melakukan.
>> Sekarang mari kita membahas beberapa terminologi.
Kami sudah berbicara tentang bagaimana akar pohon adalah simpul paling atas di pohon.
Yang satu berisi 7. Simpul di bagian bawah pohon yang disebut daun.
Setiap simpul yang hanya memiliki null sebagai anak adalah daun.
Jadi, mungkin, jika pohon biner kita hanya node tunggal,
bahwa pohon adalah daun, dan hanya itu.
"The 'tinggi' dari pohon adalah jumlah hop Anda harus membuat
untuk mendapatkan dari atas ke daun. "
Kami akan masuk ke dalam, dalam satu detik, perbedaan
antara pohon-pohon biner seimbang dan tak seimbang,
tapi untuk saat ini, ketinggian keseluruhan pohon ini
Saya akan katakan adalah 3, meskipun jika Anda menghitung jumlah hop
Anda harus membuat untuk mendapatkan sampai 9, maka itu benar-benar hanya ketinggian 2.
Sekarang ini adalah sebuah pohon biner seimbang,
tapi kami akan berbicara tentang seimbang ketika sampai relevan.
Jadi sekarang kita bisa bicara tentang node di pohon dalam hal
relatif terhadap node lain dalam pohon.
Jadi sekarang kita memiliki orang tua, anak, saudara, nenek moyang, dan keturunan.
Mereka adalah akal yang cukup umum, apa yang mereka maksudkan.
Jika kita bertanya - orang tua itu.
Jadi apa adalah orang tua dari 3?
[Siswa] 7. >> Ya. Orangtua hanya akan menjadi apa yang menunjuk ke Anda.
Lalu apa yang anak-anak dari 7?
[Siswa] 3 dan 9. >> Ya.
Perhatikan bahwa "anak-anak" secara harfiah berarti anak-anak,
jadi 6 tidak akan berlaku, karena itu seperti seorang cucu.
Tapi kemudian jika kita pergi keturunan, jadi apa adalah keturunan dari 7?
[Siswa] 3, 6 dan 9. >> Ya.
Keturunan dari simpul akar akan menjadi segala sesuatu di pohon,
kecuali mungkin simpul akar itu sendiri, jika Anda tidak ingin mempertimbangkan bahwa keturunan.
Dan akhirnya, nenek moyang, jadi arah yang berlawanan.
Jadi apa nenek moyang dari 6?
[Siswa] 3 dan 7. >> Ya. 9 tidak termasuk.
Hanya saja kembali keturunan langsung ke akar
akan menjadi nenek moyang Anda.
>> "Kami mengatakan bahwa pohon biner 'memerintahkan' jika untuk setiap node di pohon,
semua keturunannya di sebelah kiri memiliki nilai lebih rendah
dan semua orang-orang di sebelah kanan memiliki nilai yang lebih besar.
Misalnya, pohon di atas memerintahkan tapi itu bukan pengaturan memerintahkan hanya mungkin. "
Sebelum kita menuju ke sana,
sebuah pohon biner memerintahkan juga dikenal sebagai pohon pencarian biner.
Di sini kita kebetulan menyebutnya sebuah pohon biner memerintahkan,
tapi saya belum pernah mendengarnya disebut pohon biner memesan sebelum,
dan pada kuis kita jauh lebih mungkin untuk menempatkan pohon pencarian biner.
Mereka satu dan sama,
dan itu penting Anda mengenali perbedaan antara pohon biner dan pohon pencarian biner.
Sebuah pohon biner hanya pohon yang menunjuk ke dua hal.
Setiap node menunjuk ke dua hal.
Tidak ada alasan tentang nilai-nilai yang menunjuk ke.
Jadi seperti di sini, karena itu adalah pohon pencarian biner,
kita tahu bahwa jika kita pergi meninggalkan dari 7,
maka semua nilai-nilai yang kita mungkin dapat mencapai
dengan pergi kiri 7 harus kurang dari 7.
Perhatikan bahwa semua nilai kurang dari 7 adalah 3 dan 6.
Mereka semua di sebelah kiri 7.
Jika kita pergi ke kanan 7, semuanya harus lebih besar dari 7,
jadi 9 adalah di sebelah kanan 7, jadi kita baik.
Ini tidak terjadi untuk sebuah pohon biner,
untuk pohon biner biasa kita hanya bisa memiliki 3 di bagian atas, 7 ke kiri,
9 di sebelah kiri 7, tidak ada pemesanan nilai apapun.
Sekarang, kita tidak akan benar-benar melakukan ini karena itu membosankan dan tidak perlu,
tapi "mencoba untuk menarik pohon memerintahkan sebanyak yang Anda bisa memikirkan
menggunakan angka 7, 3, 9, dan 6.
Berapa banyak pengaturan yang berbeda yang ada? Apa ketinggian masing-masing? "
>> Kami akan melakukan beberapa, tapi gagasan utama adalah,
ini sama sekali tidak representasi yang unik dari pohon biner yang mengandung nilai-nilai ini.
Yang kita butuhkan adalah beberapa pohon biner yang berisi 7, 3, 6, dan 9.
Satu lagi berlaku mungkin akan akar adalah 3,
pergi ke kiri dan itu 6, pergi ke kiri dan itu 7,
pergi ke kiri dan itu 9.
Itu adalah pohon pencarian biner yang valid sempurna.
Hal ini tidak sangat membantu, karena itu hanya seperti sebuah linked list
dan semua pointer hanya nol.
Tapi itu adalah pohon valid. Ya?
[Mahasiswa] Jangan nilai-nilai harus lebih besar di sebelah kanan?
Atau ini -? >> Ini saya dimaksudkan untuk pergi ke arah lain.
Ada juga - yeah, mari kita beralih itu.
9, 7, 6, 3. Bagus tangkap.
Ini masih harus menuruti apa pencarian pohon biner yang seharusnya dilakukan.
Jadi semuanya ke kiri harus kurang dari setiap node yang diberikan.
Kami hanya bisa bergerak, mengatakan, ini 6 dan taruh di sini.
Tidak, kita tidak bisa. Mengapa saya terus melakukan itu?
Mari kita lakukan - di sini adalah 6, di sini adalah 7, 6 poin ke 3.
Ini masih sebuah pohon biner yang valid pencarian.
Apa yang salah jika saya - mari kita lihat apakah saya bisa datang dengan pengaturan.
Ya, oke. Jadi apa yang salah dengan pohon ini?
Saya kira saya sudah memberi Anda petunjuk bahwa ada sesuatu yang salah dengan itu.
Mengapa saya terus melakukan itu?
Oke. Hal ini terlihat wajar.
Jika kita melihat pada setiap node, seperti 7, kemudian ke kiri 7 adalah 3.
Jadi kita memiliki 3, hal di sebelah kanan adalah 3 6 a.
Dan jika Anda melihat 6, hal di sebelah kanan 6 adalah 9.
Lalu mengapa ini bukan sebuah pohon biner yang valid pencarian?
[Siswa] 9 masih di sebelah kiri 7. >> Ya.
Ini harus benar bahwa semua nilai yang Anda mungkin dapat mencapai dengan pergi ke sebelah kiri 7 kurang dari 7.
Jika kita pergi kiri 7, kita sampai 3 dan kita masih bisa sampai ke 6,
kita masih bisa mendapatkan sampai 9, tetapi dengan telah pergi kurang dari 7,
kita tidak harus bisa mendapatkan nomor yang lebih besar dari 7.
Jadi ini bukan sebuah pohon biner yang valid pencarian.
>> Adikku benar-benar memiliki pertanyaan wawancara
yang pada dasarnya hal ini, hanya kode sesuatu untuk memvalidasi
apakah pohon adalah pohon pencarian biner,
sehingga hal pertama yang ia lakukan adalah hanya memeriksa untuk melihat
jika kiri dan kanan sudah benar, dan kemudian iterate di sana.
Tapi Anda tidak bisa melakukan itu, Anda harus melacak
dari fakta bahwa sekarang aku sudah kiri 7,
segala sesuatu di subtree harus kurang dari 7.
Algoritma yang benar perlu untuk melacak
dari batasan bahwa nilai mungkin bisa jatuh masuk
Kami tidak akan pergi melalui semua dari mereka.
Ada hubungan kekambuhan yang bagus,
meskipun kami belum mendapatkan mereka, atau kita tidak akan sampai ke mereka,
mendefinisikan berapa banyak sebenarnya ada.
Jadi ada 14 dari mereka.
Ide tentang bagaimana Anda akan melakukannya matematis seperti,
Anda dapat memilih salah satu tunggal untuk menjadi node root,
dan kemudian jika saya memilih 7 menjadi simpul akar,
maka ada, katakanlah, beberapa nomor yang bisa menjadi simpul kiri saya,
dan ada beberapa nomor yang bisa menjadi simpul kanan saya,
tetapi jika saya memiliki n jumlah total, maka jumlah yang bisa pergi ke kiri
ditambah jumlah yang dapat pergi ke kanan adalah n - 1.
Jadi dari nomor yang tersisa, mereka harus mampu untuk pergi baik ke kiri atau ke kanan.
Tampaknya sulit yang, jika saya menempatkan 3 pertama maka semuanya harus pergi ke kiri,
tetapi jika aku menaruh 7, maka beberapa hal dapat pergi kiri dan beberapa hal dapat pergi ke kanan.
Dan dengan '3 'pertama saya berarti segalanya bisa pergi ke kanan.
Ini benar-benar, Anda hanya perlu berpikir tentang hal ini sebagai,
berapa banyak hal yang bisa pergi pada tingkat berikutnya dari pohon.
Dan itu keluar menjadi 14, atau Anda dapat menarik mereka semua,
dan kemudian Anda akan mendapatkan 14.
>> Akan kembali ke sini,
"Pohon biner Memerintahkan keren karena kita bisa mencari melalui mereka
dalam cara yang sangat mirip dengan mencari lebih dari array diurutkan.
Untuk melakukannya, kita mulai dari akar dan bekerja dengan cara kami menuruni pohon
terhadap daun, memeriksa nilai-nilai setiap node terhadap nilai-nilai yang kita cari.
Jika nilai node saat ini kurang dari nilai yang kita cari,
Anda pergi di samping anak kanan node.
Jika tidak, Anda pergi ke anak kiri node.
Pada titik tertentu, Anda akan menemukan nilai yang Anda cari, atau Anda akan lari ke null,
menunjukkan nilai tidak di pohon. "
Saya harus redraw pohon kita sebelumnya, yang akan mengambil kedua.
Tapi kami ingin mencari apakah 6, 10, dan 1 berada di pohon.
Jadi apa itu, 7, 9, 3, 6. Oke.
Angka yang Anda ingin mencari, kami ingin mencari 6.
Bagaimana ini bekerja algoritma?
Nah, kami juga memiliki beberapa pointer akar ke pohon kami.
Dan kami akan pergi ke akar dan mengatakan, ini nilai yang sama dengan nilai yang kita cari?
Jadi kita mencari 6, jadi tidak sama.
Jadi kita terus, dan sekarang kita katakan, oke, jadi 6 kurang dari 7.
Apakah itu berarti kita ingin pergi ke kiri, atau kita ingin pergi ke kanan?
[Mahasiswa] Kiri. >> Ya.
Ini secara signifikan lebih mudah, yang harus Anda lakukan adalah menggambar satu node mungkin pohon
dan kemudian Anda jangan - alih-alih mencoba untuk berpikir di kepala Anda,
oke, jika kurang, aku pergi ke kiri atau ke kanan tersebut,
hanya melihat gambar ini, sangat jelas bahwa saya harus pergi ke kiri
jika node ini lebih besar dari nilai yang saya cari.
Jadi Anda pergi ke kiri, sekarang aku di 3.
Saya ingin - 3 adalah kurang dari nilai yang saya cari, yaitu 6.
Jadi kita pergi ke kanan, dan sekarang saya berakhir di 6,
yang merupakan nilai yang saya cari, jadi saya kembali benar.
Nilai berikutnya aku akan dicari adalah 10.
Oke. Jadi 10, sekarang, akan - dipotong bahwa - akan mengikuti akar.
Sekarang, 10 akan menjadi lebih besar dari 7, jadi saya ingin melihat ke kanan.
Aku akan datang ke sini, 10 akan menjadi lebih besar dari 9,
jadi aku akan ingin melihat ke kanan.
Aku datang ke sini, tapi di sini sekarang aku di nol.
Apa yang harus saya lakukan jika aku memukul nol?
[Mahasiswa] Kembali palsu? >> Ya. Saya tidak menemukan 10.
1 akan menjadi kasus hampir sama,
kecuali itu hanya akan membalik, bukannya mencari
di sisi kanan, aku akan melihat ke bawah sisi kiri.
>> Sekarang saya pikir kita benar-benar bisa kode.
Di sinilah - membuka alat CS50 dan menavigasi jalan Anda di sana,
tetapi Anda juga dapat hanya melakukannya di ruang.
Itu mungkin ideal untuk melakukannya dalam ruang,
karena kita dapat bekerja dalam ruang.
"Pertama kita akan membutuhkan definisi tipe baru untuk simpul pohon biner yang mengandung nilai-nilai int.
Menggunakan boilerplate typedef bawah,
membuat definisi tipe baru untuk node dalam pohon biner.
Jika Anda terjebak. . . "Bla, bla, bla. Oke.
Jadi mari kita boilerplate di sini,
struct typedef node, dan node. Ya, oke.
Jadi apa bidang kita akan inginkan dalam simpul kita?
[Mahasiswa] Int dan kemudian dua pointer?
>> Int nilai, dua pointer? Bagaimana cara menulis pointer?
[Mahasiswa] Struct. >> Saya harus tampilannya masuk Yeah, jadi struct simpul * kiri,
dan struct simpul * tepat.
Dan ingat diskusi dari waktu lalu,
bahwa ini tidak masuk akal, ini tidak masuk akal,
ini tidak masuk akal.
Anda perlu segala sesuatu dalam rangka untuk menentukan ini struct rekursif.
Oke, jadi itulah yang kami pohon akan terlihat seperti.
Jika kita melakukan sebuah pohon trinary, maka simpul mungkin terlihat seperti b1, b2, struct simpul * b3,
di mana b adalah cabang - sebenarnya, saya lebih mendengar itu meninggalkan, tengah, kanan, tapi apa pun.
Kami hanya peduli biner, sehingga kanan, kiri.
"Sekarang mendeklarasikan variabel simpul * global untuk akar pohon."
Jadi kita tidak akan melakukan itu.
Dalam rangka untuk membuat hal-hal yang sedikit lebih sulit dan lebih umum,
kita tidak akan memiliki variabel simpul global.
Sebaliknya, di utama kami akan menyatakan semua hal simpul kami,
dan itu berarti bahwa di bawah ini, ketika kita mulai berjalan
kami dikandungnya fungsi dan fungsi insert kami,
bukannya dikandungnya kami hanya menggunakan fungsi ini variabel simpul global,
kita akan memilikinya mengambil sebagai argumen pohon yang kita inginkan untuk memproses.
Memiliki variabel global seharusnya membuat segalanya lebih mudah.
Kita akan membuat hal-hal sulit.
Sekarang mengambil satu menit atau lebih untuk hanya melakukan hal semacam ini,
di mana dalam utama Anda ingin membuat pohon ini, dan itu semua yang ingin Anda lakukan.
Coba dan membangun pohon ini dalam fungsi utama Anda.
>> Oke. Jadi Anda tidak bahkan harus telah dibangun pohon seluruh jalan belum.
Tapi ada yang punya sesuatu yang saya bisa menarik
untuk menunjukkan bagaimana seseorang bisa mulai membangun semacam pohon?
[Mahasiswa] membenturkan Seseorang, mencoba untuk keluar.
[Bowden] Siapapun nyaman dengan konstruksi pohon mereka?
[Mahasiswa] Tentu. Ini tidak dilakukan. >> Tidak apa-apa. Kami hanya bisa menyelesaikan -
oh, bisa Anda menyimpannya? Hore.
Jadi di sini kita memiliki - oh, aku sedikit terpotong.
Apakah saya diperbesar?
Zoom in, gulir keluar. >> Saya punya pertanyaan. >> Ya?
[Siswa] Ketika Anda mendefinisikan struct, hal-hal seperti diinisialisasi apa pun?
[Bowden] No >> Oke. Jadi, Anda harus menginisialisasi -
[Bowden] No Ketika Anda mendefinisikan, atau ketika Anda mendeklarasikan sebuah struct,
tidak diinisialisasi secara default, itu hanya seperti jika Anda mendeklarasikan int.
Ini hal yang persis sama. Ini seperti setiap bidang individu
dapat memiliki nilai sampah di dalamnya. >> Dan apakah mungkin untuk menentukan - atau untuk mendeklarasikan struct
dengan cara yang itu tidak menginisialisasi mereka?
[Bowden] Ya. Jadi, shortcut inisialisasi sintaks
akan terlihat seperti -
Ada dua cara yang dapat kita lakukan ini. Saya pikir kita harus compile
untuk membuat dentang yakin juga melakukan hal ini.
Urutan argumen yang datang dalam struct,
Anda menempatkan sebagai urutan argumen dalam kurung kurawal tersebut.
Jadi jika Anda ingin menginisialisasi ke 9 dan meninggalkan menjadi batal dan kemudian ke kanan menjadi nol,
itu akan menjadi 9, null, null.
Alternatif lain adalah, dan editor tidak menyukai sintaks ini,
dan berpikir saya ingin blok baru,
namun alternatif adalah sesuatu seperti -
di sini, saya akan meletakkannya pada baris baru.
Anda secara eksplisit bisa mengatakan, saya lupa sintaks yang tepat.
Jadi Anda secara eksplisit dapat mengatasinya dengan nama, dan berkata,
C, atau. Nilai. = 9, kiri =. NULL.
Saya menduga ini perlu menjadi koma.
. Kanan = NULL, sehingga cara ini Anda tidak
benar-benar perlu untuk mengetahui urutan struct,
dan ketika Anda membaca ini, itu jauh lebih eksplisit
tentang apa nilai yang sedang diinisialisasi ke.
>> Hal ini terjadi untuk menjadi salah satu hal yang -
jadi, untuk sebagian besar, C + + adalah superset dari C.
Anda dapat mengambil kode C, memindahkannya ke C + +, dan harus mengkompilasi.
Ini adalah salah satu hal yang C + + tidak mendukung, sehingga orang-orang cenderung untuk tidak melakukannya.
Saya tidak tahu apakah itu satu-satunya alasan orang cenderung untuk tidak melakukannya,
namun kasus di mana saya perlu untuk menggunakannya diperlukan untuk bekerja dengan C + + dan jadi saya tidak bisa menggunakan ini.
Contoh lain dari sesuatu yang tidak bekerja dengan C + + adalah
bagaimana malloc mengembalikan "void *," secara teknis,
tetapi Anda hanya bisa mengatakan char * x = malloc apapun,
dan secara otomatis akan dilemparkan ke char *.
Itu cor otomatis tidak terjadi di C + +.
Itu tidak akan mengkompilasi, dan Anda secara eksplisit akan perlu untuk mengatakan
char *, malloc, apa pun, untuk melemparkan ke char *.
Ada tidak banyak hal yang C dan C + + tidak setuju pada,
tetapi mereka adalah dua.
Jadi kita akan pergi dengan sintaks ini.
Tetapi bahkan jika kita tidak pergi dengan sintaks yang,
apa - mungkin salah dengan ini?
[Siswa] saya tidak perlu dereference itu? >> Ya.
Ingat bahwa panah memiliki dereference implisit,
dan jadi ketika kami hanya berurusan dengan struct,
kita ingin menggunakan. untuk mendapatkan di dalam bidang struct.
Dan satu-satunya waktu yang kita gunakan panah adalah ketika kita ingin melakukan -
baik, panah adalah setara dengan -
itulah yang akan berarti jika saya menggunakan panah.
Semua sarana panah, dereference ini, sekarang aku di struct, dan saya bisa mendapatkan lapangan.
Entah mendapatkan lapangan langsung atau dereference dan mendapatkan lapangan -
Saya kira ini harus menjadi nilai.
Tapi di sini aku berurusan hanya dengan struct, bukan pointer ke struct,
dan jadi saya tidak dapat menggunakan panah.
Tapi hal semacam ini bisa kita lakukan untuk semua node.
Oh my God.
Ini adalah 6, 7, dan 3.
Kemudian kita dapat mengatur cabang di pohon kita, kita dapat memiliki 7 -
kita dapat memiliki, kiri harus menunjuk ke 3.
Jadi bagaimana kita melakukannya?
[Mahasiswa, dipahami] >> Ya. Alamat node3,
dan jika Anda tidak memiliki alamat, maka tidak akan mengkompilasi.
Tapi ingat bahwa ini adalah pointer ke node berikutnya.
Hak harus menunjuk ke 9,
dan 3 harus menunjuk pada hak untuk 6.
Saya pikir ini adalah mengatur semua. Ada komentar atau pertanyaan?
[Mahasiswa, dipahami] akar akan menjadi 7.
Kami hanya bisa mengatakan simpul * ptr =
atau akar, = & node7.
>> Untuk tujuan kita, kita akan berurusan dengan insert,
jadi kita akan ingin menulis fungsi untuk memasukkan ke dalam pohon biner
dan insert pasti akan menelepon malloc untuk membuat node baru untuk pohon ini.
Jadi hal-hal yang akan mendapatkan berantakan dengan fakta bahwa beberapa node
saat ini di stack
dan node lain akan berakhir di heap ketika kita memasukkan mereka.
Ini adalah hal yang sah, tapi satu-satunya alasan
kita dapat melakukan hal ini di stack
karena itu seperti contoh buat yang kita tahu
pohon seharusnya dibangun sebagai 7, 3, 6, 9.
Jika kita tidak memiliki ini, maka kita tidak perlu malloc di tempat pertama.
Seperti yang akan kita lihat sedikit kemudian, kita harus malloc'ing.
Sekarang ini sangat masuk akal untuk menempatkan di stack,
tapi mari kita mengubah ini untuk implementasi malloc.
Jadi masing-masing kini akan menjadi sesuatu seperti
simpul * node9 = malloc (sizeof (node)).
Dan sekarang kita akan harus melakukan cek kami.
if (node9 == NULL) - Aku tidak ingin itu -
kembali 1, dan kemudian kita bisa melakukan node9-> karena sekarang ini pointer,
value = 6, node9-> kiri = NULL,
node9-> kanan = NULL,
dan kita akan harus melakukan itu untuk masing-masing node.
Jadi, bukannya, mari kita memasukkannya dalam fungsi yang terpisah.
Mari kita menyebutnya simpul * build_node,
dan ini agak mirip dengan API yang kami sediakan untuk Huffman coding.
Kami memberikan fungsi initializer untuk pohon
dan Deconstructor "fungsi" bagi pohon-pohon dan sama untuk hutan.
>> Jadi di sini kita akan memiliki fungsi initializer
hanya membangun simpul bagi kita.
Dan itu akan terlihat cukup banyak persis seperti ini.
Dan aku bahkan akan menjadi malas dan tidak mengubah nama variabel,
meskipun node9 tidak masuk akal lagi.
Oh, saya kira nilai node9 tak seharusnya 6.
Sekarang kita dapat kembali node9.
Dan di sini kita harus kembali nol.
Semua orang setuju bahwa fungsi build-a-node?
Jadi sekarang kita hanya bisa menelepon bahwa untuk membangun setiap node dengan nilai yang diberikan dan pointer null.
Sekarang kita bisa menyebutnya, yang bisa kita lakukan simpul * node9 = build_node (9).
Dan mari kita lakukan. . .
6, 3, 7, 6, 3, 7.
Dan sekarang kita ingin mengatur pointer yang sama,
kecuali sekarang semuanya sudah dalam hal pointer
sehingga tidak perlu lagi alamat.
Oke. Jadi apa hal terakhir yang ingin saya lakukan?
Ada kesalahan pengecekan bahwa aku tidak melakukan.
Apa membangun kembali simpul?
[Mahasiswa, dipahami] >> Ya. Jika malloc gagal, itu akan mengembalikan null.
Jadi aku akan malas meletakkannya di sini bukannya melakukan suatu kondisi untuk masing-masing.
Jika (node9 == NULL, atau - bahkan lebih sederhana,
ini setara dengan hanya jika tidak node9.
Jadi jika tidak node9, atau tidak node6, atau tidak node3, atau tidak node7, kembali 1.
Mungkin kita harus mencetak malloc gagal, atau sesuatu.
[Mahasiswa] Apakah palsu sama dengan null juga?
[Bowden] Setiap nilai nol adalah palsu.
Jadi nol adalah nilai nol.
Nol adalah nilai nol. False adalah nilai nol.
Setiap - cukup banyak hanya 2 nilai nol adalah nol dan nol,
palsu hanya hash didefinisikan sebagai nol.
Itu juga berlaku jika kita mendeklarasikan variabel global.
Jika kita memiliki akar simpul * di sini,
kemudian - hal yang baik tentang variabel global adalah bahwa mereka selalu memiliki nilai awal.
Itu tidak benar fungsi, seberapa dalam sini,
jika kita memiliki, seperti *, node atau simpul x.
Kami tidak tahu apa x.value, x.whatever,
atau kita bisa mencetak mereka dan mereka bisa sewenang-wenang.
Itu tidak benar dari variabel global.
Jadi simpul akar atau x simpul.
Secara default, segala sesuatu yang global, jika tidak secara eksplisit diinisialisasi untuk beberapa nilai,
memiliki nilai nol sebagai nilainya.
Jadi di sini, akar * simpul, kita tidak secara eksplisit menginisialisasi dengan apapun,
sehingga nilai default akan nol, yang merupakan nilai nol dari pointer.
Nilai default dari x akan berarti bahwa x.value adalah nol,
x.left adalah nol, dan x.right adalah null.
Jadi karena itu adalah sebuah struct, semua bidang struct akan nilai nol.
Kita tidak perlu menggunakan itu di sini, meskipun.
[Mahasiswa] The structs berbeda dibandingkan variabel lainnya, dan variabel lainnya
nilai sampah, ini adalah nol?
[Bowden] lain nilai-nilai juga. Jadi dalam x, x akan menjadi nol.
Jika itu di lingkup global, memiliki nilai awal. Oke >>.
[Bowden] Entah nilai awal yang Anda berikan atau nol.
Saya pikir yang menangani semua ini.
>> Oke. Jadi bagian selanjutnya dari pertanyaan bertanya,
"Sekarang kita ingin menulis sebuah fungsi yang disebut mengandung
dengan prototipe bool mengandung nilai int. "
Kami tidak akan melakukan bool mengandung nilai int.
Prototipe kami akan terlihat seperti
bool mengandung (nilai int.
Dan kemudian kita juga akan lulus pohon
bahwa itu harus memeriksa untuk melihat apakah memiliki nilai itu.
Jadi simpul * pohon). Oke.
Dan kemudian kita bisa menyebutnya dengan sesuatu seperti,
mungkin kita akan ingin printf atau sesuatu.
Berisi 6, akar kami.
Itu harus kembali satu, atau benar,
sedangkan berisi 5 root harus return false.
Jadi mengambil kedua untuk melaksanakan ini.
Anda dapat melakukannya baik iteratif atau rekursif.
Yang menyenangkan tentang cara kita telah mengatur segalanya adalah bahwa
itu cocok untuk solusi rekursif kami jauh lebih mudah
daripada cara-variabel global yang melakukannya.
Karena jika kita hanya memiliki mengandung nilai int, maka kita tidak memiliki cara untuk recursing bawah subpohon.
Kami harus memiliki fungsi pembantu terpisah yang recurses turun subpohon bagi kita.
Tapi karena kita telah berubah itu untuk mengambil pohon sebagai argumen,
yang harus selalu berada di tempat pertama,
sekarang kita bisa recurse lebih mudah.
Jadi iteratif atau rekursif, kita akan pergi ke baik,
tetapi kita akan melihat bahwa ujung rekursif sampai menjadi cukup mudah.
Oke. Apakah ada yang memiliki sesuatu yang kita dapat bekerja dengan?
>> [Mahasiswa] Aku punya solusi iteratif. >> Baiklah, iteratif.
Oke, ini tampak bagus.
Jadi, ingin berjalan kita melalui itu?
[Mahasiswa] Tentu. Jadi saya menetapkan variabel temp untuk mendapatkan simpul pertama dari pohon.
Dan kemudian aku hanya dilingkarkan melalui sementara suhu tidak nol sama,
jadi sementara masih di pohon, saya kira.
Dan jika nilai sama dengan nilai yang suhu menunjuk ke,
maka mengembalikan nilai itu.
Jika tidak, itu akan memeriksa apakah itu di sisi kanan atau sisi kiri.
Jika Anda pernah mendapatkan situasi di mana tidak ada pohon lagi,
maka kembali - itu keluar loop dan kembali palsu.
[Bowden] Oke. Sehingga tampaknya baik.
Ada yang punya komentar pada apa pun?
Saya tidak punya komentar benar sama sekali.
Satu hal yang dapat kita lakukan adalah orang ini.
Oh, itu akan pergi gondrong sedikit.
Saya akan memperbaiki itu. Oke.
>> Setiap orang harus ingat bagaimana terner bekerja.
Ada pasti telah kuis di masa lalu
yang memberikan fungsi dengan operator terner,
dan berkata, menerjemahkan, melakukan sesuatu yang tidak menggunakan terner.
Jadi ini adalah kasus yang sangat umum ketika saya akan berpikir untuk menggunakan terner,
di mana jika beberapa kondisi mengatur variabel untuk sesuatu,
lain mengatur bahwa variabel yang sama untuk sesuatu yang lain.
Itu adalah sesuatu yang sangat sering dapat diubah menjadi hal semacam ini
di mana mengatur variabel yang ini - atau, juga, apakah ini benar? Maka ini, yang lain ini.
[Mahasiswa] Yang pertama adalah jika benar, kan?
[Bowden] Ya. Cara saya selalu membaca itu, suhu sama dengan nilai yang lebih besar dari nilai temp,
maka ini, yang lain ini. Ini mengajukan pertanyaan.
Apakah yang lebih besar? Kemudian lakukan hal pertama. Lain melakukan hal yang kedua.
Saya hampir selalu - usus besar, saya hanya - di kepala saya, saya baca sebagai yang lain.
>> Apakah ada yang punya solusi rekursif?
Oke. Ini yang kita akan - sudah bisa menjadi besar,
tapi kami akan membuatnya lebih baik.
Hal ini cukup banyak ide yang sama persis.
Hanya saja, baik, apakah Anda ingin menjelaskan?
[Mahasiswa] Tentu. Jadi kita memastikan bahwa pohon tersebut tidak nol pertama,
karena jika pohon adalah null maka akan return false karena kita belum menemukannya.
Dan jika masih ada pohon, kita pergi ke - pertama-tama kita memeriksa apakah nilai adalah node saat ini.
Kembali benar jika, dan jika tidak kita recurse di sebelah kiri atau kanan.
Apakah itu terdengar tepat? >> Mm-hmm. (Perjanjian)
Jadi melihat bahwa ini hampir - struktural sangat mirip dengan solusi iteratif.
Hanya saja bahwa alih-alih recursing, kami memiliki loop sementara.
Dan kasus dasar di sini di mana pohon tidak nol sama
adalah kondisi di mana kita pecah keluar dari while loop.
Mereka sangat mirip. Tapi kami akan mengambil satu langkah lebih jauh.
Sekarang, kami melakukan hal yang sama di sini.
Perhatikan kita kembali hal yang sama di kedua jalur,
kecuali untuk satu argumen berbeda.
Jadi kita akan membuat itu menjadi terner.
Aku memukul sesuatu pilihan, dan itu membuat simbol. Oke.
Jadi kita akan kembali mengandung itu.
Hal ini semakin menjadi beberapa baris, dengan baik, diperbesar itu.
Biasanya, sebagai hal gaya, saya tidak berpikir banyak orang
menempatkan spasi setelah panah, tapi saya kira jika Anda konsisten, tidak apa-apa.
Jika nilai kurang dari nilai pohon, kami ingin recurse di sebelah kiri pohon,
lain kita ingin recurse di sebelah kanan pohon.
Jadi itu salah satu langkah untuk membuat tampilan ini lebih kecil.
Langkah dua membuat tampilan ini lebih kecil -
kita dapat memisahkan ini untuk beberapa baris.
Oke. Langkah dua sehingga terlihat lebih kecil di sini,
sehingga nilai kembali sama dengan nilai pohon, atau berisi apapun.
>> Ini merupakan hal yang penting.
Saya tidak yakin jika ia mengatakan itu tandasnya di kelas,
tapi itu disebut hubungan arus pendek evaluasi.
Idenya di sini adalah nilai == nilai pohon.
Jika itu benar, maka ini adalah benar, dan kami ingin 'atau' bahwa dengan apa pun di sini.
Jadi tanpa berpikir tentang apa pun ada di sini,
apa seluruh ekspresi akan kembali?
[Mahasiswa] Benar? >> Ya, karena sesungguhnya apa-apa,
or'd - or'd atau benar dengan apa pun tentu benar.
Jadi segera setelah kami melihat nilai kembali = nilai pohon,
kita hanya akan kembali benar.
Bahkan tidak akan recurse lebih berisi di telepon.
Kita dapat mengambil satu langkah lebih jauh.
Pohon kembali tidak nol sama dan semua ini.
Hal itu membuat fungsi satu-line.
Ini juga merupakan contoh dari hubungan arus pendek evaluasi.
Tapi sekarang itu adalah ide yang sama -
bukannya - jadi jika pohon tidak nol sama - atau, baik,
jika pohon tidak nol sama, yang merupakan kasus yang buruk,
jika pohon sama dengan nol, maka kondisi pertama akan menjadi palsu.
Jadi palsu anded dengan apa pun akan menjadi apa?
[Mahasiswa] False. >> Ya. Ini adalah bagian lain dari sirkuit pendek evaluasi,
di mana jika pohon tidak nol tidak sama, maka kita tidak akan bahkan pergi -
atau jika pohon tidak nol sama, maka kita tidak akan melakukan value == nilai pohon.
Kita hanya akan segera kembali palsu.
Yang penting, karena jika tidak sirkuit pendek mengevaluasi,
maka jika pohon tidak nol sama, ini kondisi kedua akan kesalahan seg,
karena pohon-> nilai dereferencing null.
Jadi itulah yang. Bisa membuat ini - pergeseran sekali atas.
Ini adalah hal yang sangat umum juga, tidak membuat satu baris dengan ini,
tapi itu hal yang umum dalam kondisi, mungkin tidak di sini,
tetapi jika (pohon = NULL,! dan pohon-> value == value), melakukan apapun.
Ini adalah kondisi yang sangat umum, di mana daripada harus
untuk istirahat ini menjadi dua ifs, di mana suka, adalah nol pohon?
Oke, itu tidak nol, jadi sekarang adalah nilai pohon sama dengan nilai? Lakukan ini.
Sebaliknya, kondisi ini, ini tidak akan pernah seg kesalahan
karena akan keluar jika hal ini terjadi menjadi nol.
Nah, saya kira jika pohon Anda adalah pointer sepenuhnya valid, masih bisa seg kesalahan,
tetapi tidak bisa seg kesalahan jika pohon adalah null.
Jika itu adalah nol, itu akan pecah sebelum Anda pernah dereferenced pointer di tempat pertama.
[Mahasiswa] Apakah ini disebut evaluasi malas?
>> [Bowden] evaluasi malas adalah hal yang terpisah.
Evaluasi malas lebih seperti Anda meminta nilai,
Anda meminta untuk menghitung nilai, jenis, tetapi Anda tidak membutuhkannya segera.
Jadi sampai Anda benar-benar membutuhkannya, tidak dievaluasi.
Ini bukan hal yang persis sama, tetapi dalam pset Huffman,
dikatakan bahwa kita "malas" menulis.
Alasan kami melakukan itu adalah karena kita benar-benar penyangga menulis -
kita tidak ingin menulis bit individu pada suatu waktu,
atau byte individu pada suatu waktu, kita malah ingin mendapatkan potongan byte.
Kemudian setelah kita memiliki sepotong byte, maka kita akan menulis itu.
Meskipun Anda meminta untuk menulis - dan fwrite dan fread melakukan hal yang sama.
Mereka penyangga membaca dan menulis.
Meskipun Anda meminta untuk menulis segera, mungkin tidak akan.
Dan Anda tidak bisa yakin bahwa hal-hal yang akan ditulis
sampai Anda menelepon hfclose atau apapun itu,
yang kemudian berkata, oke, aku menutup file saya,
itu berarti lebih baik aku menulis segala sesuatu yang saya belum ditulis belum.
Hal ini tidak perlu menulis semuanya
sampai Anda menutup file, dan kemudian perlu.
Jadi itulah yang malas - itu menunggu sampai harus terjadi.
Ini - mengambil 51 dan Anda akan masuk ke dalamnya secara lebih rinci,
karena OCaml dan segala sesuatu di 51, semuanya rekursi.
Tidak ada solusi iteratif, pada dasarnya.
Semuanya rekursi, dan evaluasi malas
akan menjadi penting bagi banyak situasi
di mana, jika Anda tidak malas mengevaluasi, itu berarti -
Contoh adalah aliran, yang jauh lebih lama.
Secara teori, Anda bisa memikirkan alam nomor sebagai aliran 1-2-3-4-5-6-7,
Jadi hal-hal yang malas dievaluasi baik-baik saja.
Jika saya mengatakan saya ingin nomor sepuluh, maka saya dapat mengevaluasi sampai ke nomor sepuluh.
Jika saya ingin nomor keseratus, maka saya dapat mengevaluasi sampai jumlah keseratus.
Tanpa evaluasi malas, maka itu akan mencoba untuk mengevaluasi semua nomor segera.
Anda mengevaluasi angka tak terhingga banyaknya, dan itu hanya tidak mungkin.
Jadi ada banyak situasi di mana malas evaluasi
hanya penting untuk mendapatkan sesuatu untuk bekerja.
>> Sekarang kita ingin menulis insert mana insert akan menjadi
sama berubah dalam definisi.
Jadi sekarang ini memasukkan bool (nilai int).
Kita akan mengubah itu untuk memasukkan bool (int nilai, simpul * pohon).
Kami benar-benar akan mengubah itu lagi dalam sedikit, kita akan melihat mengapa.
Dan mari kita bergerak build_node, hanya untuk heck itu,
atas masukkan sehingga kita tidak perlu menulis prototipe fungsi.
Yang adalah petunjuk bahwa Anda akan menggunakan build_node di insert.
Oke. Ambil satu menit untuk itu.
Saya pikir saya menyelamatkan revisi jika Anda ingin menarik dari itu,
atau, setidaknya, saya lakukan sekarang.
Saya ingin istirahat sedikit untuk berpikir tentang logika insert,
jika Anda tidak bisa memikirkan itu.
Pada dasarnya, Anda hanya akan pernah memasukkan di daun.
Seperti, jika saya memasukkan 1, maka aku pasti akan memasukkan 1 -
Aku akan berubah menjadi hitam - aku akan bisa memasukkan 1 di sini.
Atau jika saya memasukkan 4, saya ingin memasukkan 4 di sini.
Jadi tidak peduli apa yang Anda lakukan, Anda akan memasukkan pada daun.
Semua harus Anda lakukan adalah iterate bawah pohon sampai Anda mendapatkan ke node
yang harus orangtua node, orangtua node baru,
dan kemudian mengubah pointer yang kiri atau kanan, tergantung pada apakah
itu lebih besar dari atau kurang dari node saat ini.
Mengubah pointer yang untuk menunjuk ke simpul baru.
Jadi iterate bawah pohon, membuat titik daun ke node baru.
Juga berpikir tentang mengapa yang melarang jenis situasi sebelumnya,
di mana saya membangun pohon biner di mana itu benar
jika Anda hanya melihat satu node,
tapi 9 adalah di sebelah kiri 7 jika Anda mengulangi turun sepanjang jalan.
Sehingga tidak mungkin dalam skenario ini, karena -
berpikir tentang memasukkan 9 atau sesuatu, pada simpul pertama,
Aku akan melihat 7 dan aku hanya akan pergi ke kanan.
Jadi tidak peduli apa yang saya lakukan, jika saya memasukkan dengan pergi ke daun,
dan daun menggunakan algoritma yang sesuai,
itu akan menjadi mustahil bagi saya untuk memasukkan 9 di sebelah kiri 7
karena begitu aku memukul 7 Aku akan pergi ke kanan.
Apakah ada yang memiliki sesuatu untuk memulai dengan?
[Siswa] saya lakukan. Tentu >>.
[Mahasiswa, dipahami]
[Mahasiswa lainnya, tidak dapat dipahami]
[Bowden] Ini dihargai. Oke. Ingin menjelaskan?
>> [Mahasiswa] Karena kita tahu bahwa kita sedang memasukkan
baru node pada akhir pohon,
Saya dilingkarkan melalui pohon iteratif
sampai aku ke node yang menunjuk ke null.
Dan kemudian saya memutuskan untuk meletakkannya baik di sisi kanan atau sisi kiri
menggunakan variabel yang tepat, itu mengatakan kepada saya di mana untuk meletakkannya.
Dan kemudian, pada dasarnya, saya hanya membuat yang terakhir -
bahwa node suhu menunjuk ke simpul baru yang menciptakan itu,
baik di sisi kiri maupun di sisi kanan, tergantung pada apa nilai tepat adalah.
Akhirnya, saya menetapkan nilai node baru dengan nilai pengujian.
[Bowden] Oke, jadi saya melihat satu masalah di sini.
Ini seperti 95% dari perjalanan ke sana.
Salah satu masalah yang saya lihat, baik, tidak ada orang lain melihat masalah?
Apa keadaan di mana mereka keluar dari loop?
[Mahasiswa] Jika suhu adalah null? >> Ya. Jadi bagaimana Anda keluar dari loop adalah jika suhu adalah null.
Tapi apa yang saya lakukan di sini?
Saya dereference temp, yang pasti nol.
Jadi hal lain yang perlu Anda lakukan adalah tidak hanya melacak sampai temp adalah nol,
Anda ingin melacak orang tua setiap saat.
Kami juga ingin orangtua simpul *, saya kira kita bisa menjaga bahwa pada nol pada awalnya.
Ini akan memiliki perilaku aneh untuk akar pohon,
tapi kita akan mendapatkan itu.
Jika nilai lebih besar dari apa pun, maka temp = temp benar.
Tapi sebelum kita melakukan itu, orangtua temp =.
Atau orang tua selalu akan suhu yang sama? Apakah itu kasus ini?
Jika suhu tidak null, maka aku akan bergerak ke bawah, tidak peduli apa,
ke node yang temp adalah orangtua.
Jadi orang tua akan menjadi temp, dan kemudian aku pindah suhu turun.
Sekarang temp adalah nol, tapi poin orangtua kepada orang tua hal yang null.
Jadi di sini, saya tidak ingin diatur tepat sama dengan 1.
Jadi saya pindah ke kanan, jadi jika benar = 1,
dan saya kira Anda juga ingin melakukan -
jika Anda pindah ke kiri, Anda ingin mengatur hak yang sama untuk 0.
Atau yang lain jika Anda pernah bergerak ke kanan.
Jadi benar = 0. Jika benar = 1,
sekarang kita ingin membuat newNode pointer orangtua yang tepat,
lain kita ingin membuat newNode pointer orangtua kiri.
Pertanyaan itu?
Oke. Jadi ini adalah cara kita - baik, sebenarnya, bukan untuk melakukan hal ini,
Kami setengah berharap Anda untuk menggunakan build_node.
Dan kemudian jika newNode sama dengan nol, kembali palsu.
Itulah itu. Sekarang, ini adalah apa yang kami harapkan Anda lakukan.
>> Inilah solusi staf lakukan.
Saya tidak setuju dengan hal ini sebagai cara yang "benar" akan hal itu
tapi ini baik-baik saja dan itu akan bekerja.
Satu hal itu adalah hak sedikit aneh sekarang adalah
jika pohon dimulai sebagai null, kita lulus dalam pohon nol.
Saya kira itu tergantung pada bagaimana Anda mendefinisikan perilaku lewat di pohon nol.
Saya akan berpikir bahwa jika Anda lulus dalam pohon nol,
kemudian memasukkan nilai ke sebuah pohon nol
hanya harus kembali pohon di mana satu-satunya nilai adalah bahwa node tunggal.
Apakah orang setuju dengan itu? Anda bisa, jika Anda ingin,
jika Anda lulus di pohon nol
dan Anda ingin memasukkan nilai ke dalamnya, kembali palsu.
Terserah Anda untuk menentukan hal itu.
Untuk melakukan hal pertama yang saya katakan dan kemudian -
baik, Anda akan mengalami kesulitan melakukan hal itu, karena
akan lebih mudah jika kita memiliki pointer global untuk hal tersebut,
tapi kami tidak, jadi jika pohon adalah null, tidak ada yang bisa kita lakukan tentang hal itu.
Kami hanya bisa kembali palsu.
Jadi aku akan mengubah insert.
Kami secara teknis hanya bisa mengubah ini di sini,
bagaimana itu iterasi atas hal-hal,
tapi aku akan mengubah insert untuk mengambil simpul pohon **.
Ganda pointer.
Apa artinya ini?
Alih-alih berurusan dengan pointer ke node,
hal yang saya akan memanipulasi adalah pointer ini.
Aku akan memanipulasi pointer ini.
Aku akan memanipulasi pointer secara langsung.
Ini masuk akal karena, pikirkan bawah -
baik, sekarang ini menunjuk ke null.
Apa yang saya ingin lakukan adalah memanipulasi pointer ini untuk menunjuk ke tidak nol.
Saya ingin untuk menunjuk ke simpul baru.
Jika saya hanya melacak pointer ke pointer saya,
maka saya tidak perlu melacak pointer orangtua.
Aku hanya bisa melacak untuk melihat apakah pointer menunjuk ke null,
dan jika pointer menunjuk ke null,
mengubahnya untuk menunjuk ke simpul saya inginkan.
Dan saya bisa mengubahnya karena saya memiliki pointer ke pointer.
Mari kita lihat sekarang ini.
Anda benar-benar dapat melakukannya secara rekursif cukup mudah.
Apakah kita ingin melakukan itu?
Ya, kita lakukan.
>> Mari kita lihat secara rekursif.
Pertama, apa yang kasus dasar kita akan menjadi?
Hampir selalu terjadi basis kami, tetapi sebenarnya, ini agak sulit.
Pertama-tama, jika (pohon == NULL)
Saya kira kita hanya akan kembali palsu.
Hal ini berbeda dari nol pohon Anda menjadi.
Ini adalah pointer ke pointer root anda yang null
yang berarti bahwa pointer root anda tidak ada.
Jadi di sini, jika saya lakukan
* node - mari kita menggunakan kembali hal ini.
Node * root = NULL,
dan kemudian aku akan menelepon insert dengan melakukan sesuatu seperti,
masukkan ke dalam 4 & root.
Jadi & akar, jika akar adalah simpul *
kemudian & root akan menjadi ** simpul.
Ini berlaku. Dalam kasus ini, pohon, di sini,
Pohon tidak null - atau insert.
Disini. Pohon tidak null; * pohon adalah null, yang baik-baik saja
karena jika pohon * adalah null, maka saya bisa memanipulasi
untuk sekarang menunjukkan apa yang saya inginkan untuk menunjuk ke.
Namun jika pohon adalah null, yang berarti saya hanya datang ke sini dan berkata nol.
Itu tidak masuk akal. Saya tidak bisa berbuat apa-apa dengan itu.
Jika pohon adalah null, kembali palsu.
Jadi saya pada dasarnya sudah mengatakan apa kasus dasar nyata kita adalah.
Dan apa yang yang akan menjadi?
[Mahasiswa, dipahami]
[Bowden] Ya. Jadi, jika (* pohon == NULL).
Hal ini berkaitan dengan kasus di sini
di mana jika pointer merah saya adalah pointer saya berfokus pada,
jadi seperti aku fokus pada pointer ini, sekarang aku fokus pada pointer ini.
Sekarang aku fokus pada pointer ini.
Jadi jika pointer merah saya, yang ** simpul saya,
yang pernah - jika *, pointer merah saya, yang pernah nol,
itu berarti bahwa saya di kasus di mana saya sedang berfokus pada pointer yang menunjuk -
ini adalah pointer yang dimiliki daun.
Saya ingin mengubah pointer ini untuk menunjuk ke simpul baru.
Kembalilah ke sini.
NewNode saya hanya akan menjadi simpul * n = build_node (value)
maka n, jika n = NULL, kembali palsu.
Lain kita ingin mengubah apa pointer saat ini sedang menunjuk ke
sekarang menunjuk ke simpul kami baru dibangun.
Kami benar-benar bisa melakukannya di sini.
Alih-alih mengatakan n, kita katakan * tree = jika pohon *.
Semua orang memahami bahwa? Bahwa oleh berurusan dengan pointer ke pointer,
kita dapat mengubah pointer nol untuk menunjuk ke hal yang kita ingin mereka untuk menunjuk ke.
Itulah kasus dasar kami.
>> Sekarang kami kambuh, atau rekursi kami,
akan menjadi sangat mirip dengan semua recursions lain kita sudah melakukan.
Kita akan ingin menyisipkan nilai,
dan sekarang aku akan menggunakan terner lagi, tapi apa yang kondisi kita akan menjadi?
Apa itu yang kita cari untuk memutuskan apakah kita ingin pergi kiri atau kanan?
Mari kita lakukan dalam langkah-langkah terpisah.
If (nilai <) apa?
[Mahasiswa] Nilai Pohon itu?
[Bowden] Jadi ingat bahwa aku saat ini -
[Mahasiswa, dipahami]
[Bowden] Ya, jadi di sini, mari kita mengatakan bahwa ini panah hijau
adalah contoh dari apa pohon saat ini, adalah pointer ke pointer ini.
Jadi itu berarti saya pointer ke pointer ke 3.
Dereference dua kali terdengar baik.
Apa yang harus saya - bagaimana saya melakukan itu?
[Mahasiswa] dereference sekali, dan kemudian melakukan panah itu?
[Bowden] Jadi (* pohon) adalah dereference sekali, -> value
akan memberikan nilai node bahwa aku tidak langsung menunjuk ke.
Jadi saya juga bisa menulis ** tree.value jika Anda lebih suka itu.
Entah bekerja.
Jika itu terjadi, maka saya ingin menelepon masukkan dengan nilai.
Dan apa yang saya simpul diperbarui ** akan menjadi?
Saya ingin pergi ke kiri, sehingga ** tree.left akan menjadi kiri saya.
Dan saya ingin pointer ke hal yang
sehingga jika kiri berakhir menjadi null pointer,
Saya dapat memodifikasi untuk menunjuk ke simpul baru.
>> Dan kasus lain bisa sangat mirip.
Mari kita benar-benar membuat bahwa terner saya sekarang.
Masukkan nilai jika nilai <(** pohon). Nilai.
Kemudian kita ingin memperbarui ** kami ke kiri,
lain kita ingin memperbarui ** kami ke kanan.
[Mahasiswa] Apakah yang mendapatkan pointer ke pointer?
[Bowden] Ingatlah bahwa - ** tree.right adalah bintang simpul.
[Mahasiswa, dipahami] >> Ya.
** Tree.right seperti ini pointer atau sesuatu.
Jadi dengan mengambil pointer untuk itu, yang memberikan apa yang saya inginkan
dari pointer ke orang itu.
[Mahasiswa] Bisakah kita pergi lagi mengapa kita menggunakan dua pointer?
[Bowden] Ya. Jadi - tidak, Anda bisa, dan solusi yang sebelumnya
adalah cara untuk melakukannya tanpa melakukan dua pointer.
Anda harus mampu memahami menggunakan dua pointer,
dan ini adalah solusi yang bersih.
Juga, perhatikan bahwa, apa yang terjadi jika pohon saya -
apa yang terjadi jika akar saya nol? Apa yang terjadi jika saya melakukan hal ini di sini?
Jadi simpul * root = NULL, masukkan ke dalam 4 & root.
Apa yang akan menjadi akar setelah ini?
[Mahasiswa, dipahami] >> Ya.
Nilai akar akan menjadi 4.
Kiri akar akan menjadi nol, benar akar akan menjadi nol.
Dalam kasus di mana kita tidak lulus akar berdasarkan alamat,
kita tidak bisa memodifikasi akar.
Dalam kasus di mana pohon - di mana akar adalah nol,
kami hanya harus kembali palsu. Tidak ada yang bisa kami lakukan.
Kita tidak dapat menyisipkan sebuah node menjadi pohon yang kosong.
Tapi sekarang kita bisa, kita hanya membuat sebuah pohon kosong ke pohon satu simpul.
Yang biasanya cara yang diharapkan bahwa itu seharusnya bekerja.
>> Selain itu, hal ini secara signifikan lebih pendek dibandingkan
juga melacak orangtua, sehingga Anda iterate turun sepanjang jalan.
Sekarang saya memiliki orang tua saya, dan saya hanya memiliki orangtua kanan saya pointer untuk apa pun.
Sebaliknya, jika kita melakukan ini iteratif, itu akan menjadi ide yang sama dengan while loop.
Tapi bukannya harus berurusan dengan pointer orangtua saya,
bukan pointer saya saat ini akan menjadi hal yang
bahwa aku langsung memodifikasi untuk menunjuk ke simpul baru.
Saya tidak harus berurusan dengan apakah itu menunjuk ke kiri.
Saya tidak harus berurusan dengan apakah itu menunjuk ke kanan.
Hanya saja apa pointer ini, aku akan mengaturnya untuk menunjuk ke simpul baru.
Semua orang mengerti cara kerjanya?
Jika tidak mengapa kita ingin melakukannya dengan cara ini,
tapi setidaknya bahwa ini bekerja sebagai solusi?
[Siswa] mana kita kembali benar?
[Bowden] Itu mungkin di sini.
Jika kita benar masukkan, kembali benar.
Lain, di sini kita akan ingin kembali apapun kembali insert.
>> Dan apa yang khusus tentang fungsi rekursif?
Ini ekor rekursif, sehingga selama kita mengkompilasi dengan beberapa optimasi,
akan menyadari bahwa Anda dan tidak akan pernah mendapatkan stack overflow dari ini,
bahkan jika pohon kami memiliki ketinggian 10.000 atau 10 juta.
[Mahasiswa, dipahami]
[Bowden] saya pikir itu melakukannya di Dash - atau apa tingkat optimasi
diperlukan untuk rekursi ekor untuk diakui.
Saya pikir itu mengakui - GCC dan dentang
juga memiliki arti yang berbeda untuk tingkat optimasi mereka.
Saya ingin mengatakan itu DashO 2, untuk memastikan bahwa hal itu akan mengenali rekursi ekor.
Tapi kami - Anda bisa membangun seperti contoh Fibonocci atau sesuatu.
Ini tidak mudah untuk menguji dengan ini, karena sulit untuk membangun
pohon biner yang begitu besar.
Tapi ya, saya pikir itu DashO 2, yang
jika Anda mengkompilasi dengan DashO 2, maka akan mencari rekursi ekor
dan mengoptimalkan yang keluar.
Mari kita kembali ke - masukkan secara harfiah hal terakhir yang dibutuhkan.
Mari kita kembali ke insert di sini
di mana kita akan melakukan ide yang sama.
Ini masih akan memiliki cacat yang tidak mampu untuk sepenuhnya menangani
ketika akar itu sendiri adalah null, atau masuknya masa lalu adalah null,
tapi bukannya berurusan dengan pointer tua,
mari kita menerapkan logika yang sama dari pointer ke pointer menjaga.
Jika di sini kita tetap simpul kami ** skr,
dan kita tidak perlu untuk melacak yang benar lagi,
tapi simpul ** skr = & pohon.
Dan sekarang loop sementara kita akan menjadi saat skr * tidak nol sama.
Tidak perlu untuk melacak orang tua lagi.
Tidak perlu melacak kiri dan kanan.
Dan aku akan menyebutnya temp, karena kita sudah menggunakan temp.
Oke. Jadi, jika (nilai> * temp),
kemudian & (* temp) -> benar
lain temp = & (* temp) -> kiri.
Dan sekarang, pada saat ini, setelah loop sementara,
Saya hanya melakukan ini karena mungkin akan lebih mudah untuk berpikir tentang iteratively daripada rekursif,
tapi setelah ini loop sementara,
* Suhu adalah pointer kita ingin berubah.
>> Sebelum kita memiliki orang tua, dan kami ingin mengubah baik kiri orang tua atau orang tua yang tepat,
tetapi jika kita ingin mengubah hak orang tua,
maka * suhu yang tepat orangtua, dan kita bisa mengubahnya secara langsung.
Jadi di sini, kita bisa lakukan * temp = newNode, dan hanya itu.
Jadi pemberitahuan, semua yang kita lakukan dalam hal ini adalah mengambil baris kode.
Dalam rangka untuk melacak orang tua dalam semua itu adalah upaya tambahan.
Di sini, jika kita hanya melacak pointer ke pointer,
dan bahkan jika kita ingin menyingkirkan semua kurung kurawal sekarang,
membuatnya terlihat lebih pendek.
Ini sekarang adalah solusi yang persis sama,
namun sedikit baris kode.
Setelah Anda mulai mengakui ini sebagai solusi yang valid,
itu juga lebih mudah untuk alasan tentang daripada seperti, oke,
mengapa saya memiliki bendera ini di kanan int?
Apa artinya? Oh, itu menandakan bahwa
setiap kali aku pergi tepat, saya harus mengaturnya,
lain jika saya pergi meninggalkan saya perlu untuk mengatur ke nol.
Di sini, saya tidak punya alasan tentang itu, hanya saja lebih mudah untuk berpikir tentang.
Pertanyaan?
[Mahasiswa, dipahami] >> Ya.
Oke, jadi dalam bit terakhir -
Saya kira satu fungsi cepat dan mudah dapat kita lakukan adalah,
ayo - bersama-sama, saya kira, mencoba dan menulis mengandung fungsi
yang tidak peduli apakah itu adalah pohon pencarian biner.
Ini berisi fungsi harus kembali benar
jika di mana saja di pohon biner secara umum adalah nilai yang kita cari.
Jadi mari kita pertama melakukannya secara rekursif dan kemudian kita akan melakukannya iteratif.
Kami benar-benar bisa hanya melakukannya bersama-sama, karena ini akan menjadi benar-benar pendek.
>> Apa yang kasus dasar saya akan?
[Mahasiswa, dipahami]
[Bowden] Jadi, jika (pohon == NULL), lalu apa?
[Mahasiswa] Kembali palsu.
[Bowden] Lain, baik, saya tidak perlu lagi tersebut.
Jika itu kasus dasar saya yang lain.
[Mahasiswa] Tree nilai? >> Ya.
Jadi, jika (pohon-> value == nilai.
Perhatikan kita kembali ke * node, bukan simpul ** s?
Berisi tidak akan pernah perlu menggunakan simpul **,
karena kita tidak memodifikasi pointer.
Kami hanya melintasi mereka.
Jika itu terjadi, maka kita ingin kembali benar.
Lain kita ingin melintasi anak-anak.
Jadi kita tidak bisa berpikir tentang apakah semuanya ke kiri kurang
dan segala sesuatu ke kanan lebih besar.
Jadi apa yang kondisi kita akan berada di sini - atau, apa yang akan kita lakukan?
[Mahasiswa, dipahami] >> Ya.
Kembali mengandung (nilai, pohon-> kiri)
atau mengandung (nilai, pohon-> kanan). Dan itu saja.
Dan perhatikan ada beberapa evaluasi sirkuit pendek,
di mana jika kita kebetulan menemukan nilai di pohon kiri,
kita tidak pernah perlu melihat pohon yang tepat.
Itulah seluruh fungsi.
Sekarang mari kita lakukan iteratively,
yang akan menjadi kurang bagus.
Kami akan mengambil start biasa simpul * skr = pohon.
Sementara (skr = NULL!).
Cepat akan melihat masalah.
Jika skr - di sini, jika kita pernah keluar dari ini,
maka kita sudah kehabisan hal untuk melihat, jadi kembali palsu.
Jika (skr-> value == value), kembali benar.
Jadi sekarang, kita berada di tempat -
kita tidak tahu apakah kita ingin pergi kiri atau kanan.
Jadi sewenang-wenang, mari kita pergi ke kiri.
Aku sudah jelas mengalami masalah di mana saya benar-benar meninggalkan segalanya -
Saya hanya akan memeriksa sisi kiri pohon.
Aku tidak pernah akan memeriksa apa-apa yang merupakan anak kanan dari apa pun.
Bagaimana cara mengatasinya?
[Siswa] Anda harus melacak kiri dan kanan dalam tumpukan.
[Bowden] Ya. Jadi mari kita membuatnya
struct daftar, simpul * n, dan kemudian simpul ** selanjutnya?
Saya berpikir bahwa bekerja dengan baik.
Kami ingin pergi ke kiri, atau ayo - di sini.
= Daftar struct daftar, itu akan mulai
keluar di daftar ini struct.
* List = NULL. Sehingga akan menjadi linked list kami
dari subpohon yang kita telah terlampaui.
Kami akan melintasi tersisa sekarang,
tapi karena mau tak mau kita harus datang kembali ke kanan,
Kita akan menjaga sisi kanan dalam daftar struct kami.
Kemudian kita akan memiliki new_list atau struct,
struct daftar *, new_list = malloc (sizeof (daftar)).
Aku akan mengabaikan kesalahan-memeriksa bahwa, tetapi Anda harus memeriksa untuk melihat null jika itu.
New_list node itu akan menunjuk ke -
oh, itu sebabnya aku ingin di sini. Ini akan menunjukkan daftar struct kedua.
Itu hanya cara kerja terkait daftar.
Ini adalah sama dengan linked list int
kecuali kami hanya mengganti int dengan * simpul.
Ini persis sama.
Jadi new_list, nilai simpul new_list kami,
akan menjadi skr-> benar.
Nilai kami new_list-> berikutnya akan menjadi daftar asli kami,
dan kemudian kita akan memperbarui daftar kami untuk menunjuk ke new_list.
>> Sekarang kita perlu beberapa macam cara hal-hal menarik,
seperti kita telah melintasi seluruh subtree kiri.
Sekarang kita perlu untuk menarik barang-barang keluar dari itu,
seperti skr adalah null, kami tidak ingin hanya kembali palsu.
Kami ingin sekarang tarik luar di daftar baru kami.
Sebuah cara mudah untuk melakukan hal ini - baik, sebenarnya, ada beberapa cara untuk melakukan hal ini.
Ada yang punya saran?
Dimana saya harus melakukan ini atau bagaimana saya harus melakukan ini?
Kami hanya memiliki beberapa menit, tetapi ada saran?
Alih-alih - salah satu cara, bukan kondisi kita yang sementara,
apa yang kita sedang melihat tidak null,
sebaliknya kita akan terus pergi sampai daftar kami sendiri adalah null.
Jadi jika daftar kami akhirnya menjadi nol,
maka kita telah kehabisan hal untuk mencari, untuk mencari lebih.
Tapi itu berarti bahwa hal pertama dalam daftar kami hanya akan menjadi simpul pertama.
Hal pertama akan - kita tidak perlu lagi untuk melihat bahwa.
Jadi list-> n akan menjadi pohon kami.
Daftar-> selanjutnya akan menjadi nol.
Dan sekarang sementara daftar tidak nol sama.
Cur akan menarik sesuatu dari daftar kami.
Jadi skr akan daftar-> sama n.
Dan kemudian daftar akan daftar-> sama n, atau daftar-> berikutnya.
Jadi jika nilai sama dengan nilai skr.
Sekarang kita dapat menambahkan kedua pointer yang tepat dan pointer kiri kami
asalkan mereka tidak nol.
Di sini, saya kira kita harus melakukan itu di tempat pertama.
Jika (skr-> kanan = NULL!)
maka kita akan menyisipkan simpul yang menjadi daftar kami.
Jika (skr-> kiri), ini adalah sedikit kerja ekstra, tapi tidak apa-apa.
Jika (skr-> kiri = NULL!),
dan kita akan memasukkan kiri ke daftar kami terkait,
dan yang harus itu.
Kami iterate - selama kita memiliki sesuatu dalam daftar kami,
kita memiliki node lain untuk melihat.
Jadi kita melihat simpul tersebut,
kita memajukan daftar kami ke yang berikutnya.
Jika node adalah nilai yang kita cari, kita dapat kembali benar.
Lain memasukkan kedua sub pohon kiri dan kanan kami,
asalkan mereka tidak null, ke dalam daftar
sehingga kita pasti pergi atas mereka.
Jadi, jika mereka tidak null,
jika pointer root menunjuk dua hal,
maka pada awalnya kami mengeluarkan sesuatu sehingga daftar kami berakhir menjadi nol.
Dan kemudian kami menempatkan dua hal kembali, jadi sekarang daftar kami adalah ukuran 2.
Kemudian kita akan loop kembali ke atas dan kami hanya akan menarik,
katakanlah, pointer kiri simpul akar kami.
Dan itu hanya akan terus terjadi, kita akan berakhir perulangan atas segala sesuatu.
>> Perhatikan bahwa ini secara signifikan lebih rumit
dalam solusi rekursif.
Dan saya sudah mengatakan beberapa kali
bahwa solusi rekursif biasanya memiliki banyak kesamaan dengan berulang solusi.
Berikut ini adalah apa solusi rekursif lakukan.
Satu-satunya perubahan adalah bahwa alih-alih implisit menggunakan stack, stack program,
sebagai cara Anda melacak apa yang node Anda masih perlu untuk mengunjungi,
sekarang Anda harus secara eksplisit menggunakan linked list.
Dalam kedua kasus Anda melacak apa yang simpul masih perlu untuk dikunjungi.
Dalam kasus rekursif itu hanya lebih mudah karena stack
diimplementasikan untuk Anda sebagai tumpukan program.
Perhatikan bahwa linked list, itu adalah stack.
Apapun yang kita hanya menempatkan di stack
segera apa yang kita akan menarik dari tumpukan untuk mengunjungi selanjutnya.
Kami kehabisan waktu, tetapi setiap pertanyaan?
[Mahasiswa, dipahami]
[Bowden] Ya. Jadi jika kita memiliki linked list kami,
saat akan menunjuk ke orang ini,
dan sekarang kami hanya memajukan linked list kami untuk fokus pada orang ini.
Kami sedang melintasi atas daftar link di baris itu.
Dan kemudian saya kira kita harus membebaskan linked list kami dan barang-barang
sekali sebelum kembali benar atau salah, kita perlu
iterate atas daftar kami terkait dan selalu di sini, saya kira,
jika kita skr benar tidak sama dengan, menambahkannya, jadi sekarang kita ingin membebaskan
skr karena, well, apakah kita benar-benar melupakan daftar? Ya.
Jadi itulah yang kami ingin lakukan di sini.
Dimana pointer?
Cur kemudian - kami ingin daftar struct * 10 sama dengan daftar berikutnya.
Daftar gratis, daftar = temp.
Dan dalam kasus di mana kita kembali benar, kita perlu iterate
selama sisa linked list kami membebaskan hal.
Yang menyenangkan tentang solusi rekursif membebaskan hal-hal
hanya berarti factorings muncul dari tumpukan yang akan terjadi untuk Anda.
Jadi kita sudah pergi dari sesuatu yang seperti 3 baris sulit berpikir tentang kode-
sesuatu yang secara signifikan lebih banyak sulit berpikir-tentang baris kode.
Ada pertanyaan lain?
Baiklah. Kita baik. Bye!
[CS50.TV]