[Powered by Google Translate] [ნაწილი 7: უფრო კომფორტული]
[Rob Bowden] [ჰარვარდის უნივერსიტეტის]
[ეს არის CS50] [CS50.TV]
ყველა უფლება. ასე რომ მე განაცხადა ჩემი ელ,
ეს იქნება ორობითი ხე ინტენსიური მონაკვეთზე.
მაგრამ არ არსებობს, რომ ბევრ კითხვას.
ამიტომ, ჩვენ ვაპირებთ შევეცადოთ და შესამუშაევბლად თითოეული კითხვა
და წასვლას მტკივნეული დეტალი ყველა საუკეთესო გზები საქმეს აკეთებენ.
ასე რომ უფლება დასაწყისში, ჩვენ გაიაროს ნიმუში ნახატების ორობითი ხეები და პერსონალი.
ასე რომ აქ ", გახსოვდეთ, რომ ორობითი ხე აქვს კვანძების ანალოგიურია უკავშირდება სია,
გარდა ერთის ნაცვლად მაჩვენებელი არსებობს ორი: ერთი მარცხნივ ბავშვის
და ერთი უფლება 'ბავშვი'. "
ასე რომ ორობითი ხე არის, ისევე, როგორც დაკავშირებული სიაში,
გარდა struct აპირებს აქვს ორი პოინტერები.
არსებობს trinary ხეები, რომლებიც აპირებენ სამი პოინტერები,
არსებობს N-მარტისათვის ხეები, რომელიც უბრალოდ უნდა generic მაჩვენებელი
რომ თქვენ მაშინ უნდა malloc იყოს დიდი საკმარისი აქვს
საკმარისი მითითებას ყველა შესაძლო შვილი.
ასე რომ ორობითი ხე რაღაც ჰქონდეს მუდმივი ხმების ორი.
თუ გსურთ, თქვენ შეგიძლიათ მისცეს დაკავშირებული სიაში როგორც unary ხე,
მაგრამ არა მგონია, ვინმეს მოუწოდებს, რომ.
"დახაზეთ ყუთები და ისრებით დიაგრამის ორობითი ხე კვანძში
შემცველი Nate ფავორიტი ნომერი, 7, სადაც თითოეულ ბავშვს მაჩვენებელი არის null. "
ასე რომ iPad რეჟიმში.
>> ეს იქნება საკმაოდ მარტივია.
ჩვენ უბრალოდ აპირებს კვანძში, მე მიაპყროს, როგორც მოედანზე.
მე კი მიაპყროს ფასეულობების აქ.
ამიტომ ღირებულების წავა აქ,
და შემდეგ ქვევით აქ გვექნება მარცხენა კურსორი მარცხნივ და მარჯვნივ კურსორი მარჯვნივ.
და ეს არის ძალიან ისე კონვენციით ეძახით მარცხენა და მარჯვენა, რომელიც მაჩვენებელმა სახელები.
ორივე ვაპირებთ იყოს null.
ეს ხელს მხოლოდ null, და რომელიც მხოლოდ null.
Okay. ასე რომ თავში აქ.
"ერთად უკავშირდება სია, ჩვენ მხოლოდ შესანახად მაჩვენებელი
პირველი კვანძის სიაში, რათა გვახსოვდეს, რომ მთელი უკავშირდება სიაში, ან მთელი სია.
ანალოგიურად, ხეებით, ჩვენ მხოლოდ უნდა შესანახად მაჩვენებელი
ერთ კვანძში, რათა გვახსოვდეს, რომ მთელი ხე.
ეს კვანძი არის Calle კი "root 'ხე.
ქმნით თქვენს დიაგრამაზე საწყისი დაწყებამდე ან დავხატოთ ახალი
ისეთი, რომ თქვენ გაქვთ ყუთები და ისრებით გამოსახვა ორობითი ხე
ერთად ღირებულება 7, შემდეგ 3 წლის მარცხენა
მაშინ 9 მარჯვენა, შემდეგ კი 6 წლის უფლება 3. "
ვნახოთ, თუ მე მახსოვს ყველა, რომ ჩემი უფროსი.
ასე რომ, ეს იქნება ჩვენი ფესვი აქ.
ჩვენ გვექნება ზოგიერთი მაჩვენებელი სადღაც, რაღაც, რაც ჩვენ მოვუწოდებთ ფესვი,
და ეს მიუთითებს ამ ბიჭს.
ახლა, რათა ახალი კვანძის,
რა გვაქვს, 3 მარცხენა?
ასე რომ ახალი კვანძის ერთად 3, და ეს თავდაპირველად მიუთითებს null.
მე უბრალოდ დააყენა ნ
ახლა ჩვენ გვსურს, რომ გადადით მარცხნივ 7.
ამიტომ, ჩვენ შეცვალოთ ეს მომცეთ არის პასუხისმგებელი ამ ბიჭს.
და ჩვენ იგივე. ჩვენ გვინდა 9 ზე აქ
რომელიც თავდაპირველად მხოლოდ ამბობს null.
ჩვენ ვაპირებთ, რომ შეიცვალოს ეს მაჩვენებელი, წერტილი 9,
და ახლა ჩვენ გვინდა დააყენა 6 მარჯვნივ 3.
ამიტომ აპირებს - მიიღოს 6.
და რომ ბიჭი იქნება აღვნიშნო.
Okay. ასე რომ ყველა ის გვთხოვს უნდა გააკეთოს.
>> ახლა მოდით წავიდეთ მეტი რამდენიმე ტერმინოლოგიას.
ჩვენ უკვე ვისაუბრეთ იმაზე, თუ როგორ root ხე არის ყველაზე საუკეთესო კვანძში, რომელიც ხე.
ერთი შემცველი 7. კვანძების ბოლოში ხე ეწოდება ფოთლები.
ნებისმიერი კვანძის რომელიც მხოლოდ აქვს null როგორც თავისი ბავშვების ფოთოლი.
ასე რომ, შესაძლებელია, თუ ჩვენი ორობითი ხე არის მხოლოდ ერთი კვანძის,
რომ ხე არის ფოთოლი, და ამით ყველაფერი მთავრდება.
"The 'სიმაღლე' ხე არის ხმების hops თქვენ უნდა გააკეთოთ
მიიღოს ზემოდან რომ ფოთოლი. "
ჩვენ შეღწევას, წელს მეორე, განსხვავება
შორის დაბალანსებული და გაუწონასწორებელ ბინარული ხეები,
მაგრამ ახლა, საერთო სიმაღლე ამ ხე
მე ვიტყოდი, არის 3, თუმცა, თუ თქვენ ითვლიან რაოდენობის hops
თქვენ უნდა გააკეთოთ, რათა ხელი 9, მაშინ ეს მართლაც მხოლოდ სიმაღლე 2.
ახლავე ეს გაუწონასწორებელ ორობითი ხე,
მაგრამ ჩვენ ვისაუბრეთ დაბალანსებული, როდესაც იგი იღებს უნდა იყოს შესაბამისი.
ახლა ჩვენ შეგვიძლია ვისაუბროთ კვანძების ხე თვალსაზრისით
შედარებით სხვა კვანძების ხე.
ახლა ჩვენ გვაქვს მშობლები, შვილები, და, ძმა, წინაპრების და შთამომავლების.
ისინი საკმაოდ საღი აზრი, რას გულისხმობენ.
თუ ჩვენ ვთხოვთ - ის მშობლები.
რა არის მშობელი 3?
[სტუდენტთა] 7. >> Yeah. მშობელს მხოლოდ იქნება რა მიუთითებს თქვენ.
მაშინ რა შვილები 7?
[სტუდენტთა] 3 და 9. >> Yeah.
გაითვალისწინეთ, რომ "ბავშვები" სიტყვასიტყვით ნიშნავს შვილი,
ასე რომ, 6 არ ვრცელდება, რადგან მოსწონს შვილიშვილი.
მაგრამ შემდეგ, თუ ჩვენ შთამომავლები, რადგან ყველანი შთამომავლები 7?
[სტუდენტთა] 3, 6 და 9. >> Yeah.
შთამომავლები root node იქნება ყველაფერი ხე,
გარდა იქნებ root node თავად, თუ არ გვინდა, რომ თვლიან, რომ შთამომავალი.
და ბოლოს, წინაპრები, ამიტომ საპირისპირო მიმართულებით.
ასე რომ რა წინაპრები 6?
[სტუდენტთა] 3 და 7. >> Yeah. 9 არ შედის.
უბრალოდ პირდაპირი lineage დაბრუნება root
იქნება თქვენი წინაპრების.
>> "ჩვენ ვამბობთ, რომ ორობითი ხის 'შეუკვეთა' თუ თითოეული კვანძის in ხე,
ყველა მისი შთამომავლები მარცხენა აქვს ნაკლები ღირებულებების
და ყველა, ვინც მარჯვენა აქვს უფრო დიდი ღირებულებები.
მაგალითად, ხე ზემოთ უკვეთავს მაგრამ ეს არ არის მხოლოდ შესაძლებელი უბრძანა მოწყობა. "
სანამ არ მივიღებთ რომ,
უბრძანა ორობითი ხე ასევე ცნობილია როგორც ორობითი ძებნა ხე.
აქ ჩვენ არ უნდა იყოს უწოდა უბრძანა ორობითი ხე,
მაგრამ არასდროს არ მსმენია ეს მოუწოდა უბრძანა ორობითი ხე ადრე,
და ინტელექტუალური ჩვენ ბევრად უფრო დააყენა ორობითი ძებნა ხე.
ისინი ერთი და იგივე,
და მნიშვნელოვანია თქვენ აღიარებს განსხვავება შორის ორობითი ხე და ბინარული ძებნა ხე.
ორობითი ხე მხოლოდ ხე, რომელიც მიუთითებს ორ რამეს.
თითოეული კვანძის მიუთითებს ორ რამეს.
არ არსებობს მიზეზის შესახებ ღირებულებებს, რომ ეს მიუთითებს.
ამიტომ მინდა აქ, რადგან ბინარული ძებნა ხე,
ჩვენ ვიცით, რომ თუ ჩვენ მივდივართ მარცხნივ 7,
მაშინ ყველა ღირებულებებს, რომ ჩვენ შესაძლოა მიაღწიოს
მიერ მიმდინარეობს დარჩა 7 უნდა იყოს არანაკლებ 7.
გაითვალისწინეთ, რომ ყველა ღირებულებების არანაკლებ 7 არიან 3 და 6.
იმ ყველა მარცხნივ 7.
თუ ჩვენ წასვლა უფლება 7, ყველაფერი უნდა იყოს მეტი 7,
ასე 9 არის მარჯვნივ 7, ასე რომ ჩვენ კარგები.
ეს არ არის საქმე ორობითი ხე,
ამისთვის რეგულარული ორობითი ხე შეგვიძლია უბრალოდ 3 ზედა, 7 მარცხნივ,
9 მარცხნივ 7; არ შეკვეთით ფასეულობათა განაწილებაზე.
ახლა ჩვენ რეალურად არ ვაკეთებთ, რადგან ეს რუტინული და არასაჭირო,
მაგრამ "ცდილობენ მიაპყროს როგორც ბევრი უბრძანა ხეები, როგორც თქვენ შეგიძლიათ ვფიქრობ
გამოყენებით ნომრები 7, 3, 9, და 6.
რამდენი განსხვავებული ფორმატი არის იქ? რა არის სიმაღლე ყოველი ერთი? "
>> ჩვენ ყველაფერს გავაკეთებთ წყვილი, მაგრამ მთავარი იდეა ისაა,
ეს არანაირად არ უნიკალური წარმომადგენლობა ორობითი ხე შემცველი ამ ღირებულებებს.
ყველა ჩვენ გვჭირდება გარკვეული ორობითი ხე, რომელიც შეიცავს 7, 3, 6, და 9.
კიდევ ერთი შესაძლო მართებული იქნებოდა root არის 3,
გადადით მარცხნივ და ეს 6, გადადით მარცხნივ და ეს 7,
გადადით მარცხნივ და ეს 9.
სწორედ შესანიშნავად მოქმედებს ორობითი ძებნა ხე.
ეს არ არის ძალიან გამოსადეგი, რადგან ეს ისევე უკავშირდება სია
და ყველა ეს მითითებები მხოლოდ null.
მაგრამ ეს სწორი ხე. ჰო?
[სტუდენტური] ნუ ღირებულებები უნდა იყოს უფრო მეტი მარჯვენა?
ან ეს -? >> ეს ვგულისხმობდი წასვლა სხვა გზით.
არის კიდევ - ჰო, მოდით გადართოთ რომ.
9, 7, 6, 3. კარგი დაჭერა.
ეს ჯერ არ ემორჩილებიან რა ორობითი ხე ძებნა უნდა გავაკეთოთ.
ასე რომ ყველაფერი მარცხნივ უნდა იყოს ნაკლები ნებისმიერ მოცემულ კვანძში.
ჩვენ შეგვეძლო უბრალოდ გადაადგილება, ვთქვათ, ამ 6 და განათავსოთ აქ.
არა, ჩვენ არ შეგვიძლია. რატომაა აკეთეთ, რომ?
მოდით - აქ არის 6, აქ არის 7, 6 ქულა 3.
ეს არის ჯერ კიდევ მოქმედებს ორობითი ძებნა ხე.
რა არის არასწორი თუ - ვნახოთ, თუ შემიძლია ამუშავება მოწყობა.
Yeah, okay. რა არის ცუდი ამ ხეს?
ვფიქრობ მე უკვე მოცემული მინიშნება, რომ არსებობს რაღაც არის.
რატომაა აკეთეთ, რომ?
Okay. ეს გამოიყურება გონივრული.
თუ დავაკვირდებით თითოეული კვანძის, როგორიცაა 7, შემდეგ მარცხნივ 7 არის 3.
ასე რომ, ჩვენ გვაქვს 3, რამ უფლება 3 არის 6.
და თუ თქვენ შეხედეთ 6, რამ უფლება 6 არის 9.
მაშ რატომ არის ეს არ მოქმედებს ორობითი ძებნა ხე?
[სტუდენტთა] 9 მაინც მარცხნივ 7. >> Yeah.
ეს უნდა იყოს ჭეშმარიტი, რომ ყველა მნიშვნელობა თქვენ შესაძლოა მიაღწიოს მიერ აპირებს მარცხნივ 7 ნაკლებია 7.
თუ ჩვენ მივდივართ მარცხნივ 7, მივიღებთ დან 3 და ჩვენ შეგვიძლია მაინც დან 6,
ჩვენ შეგვიძლია მაინც დან 9, არამედ რომელმაც წავიდა არანაკლებ 7,
ჩვენ არ უნდა შეუძლია მიიღოს რიგი რომ აღემატება 7.
ასე რომ ეს არ არის სწორი ორობითი ძებნა ხე.
>> ჩემი ძმა რეალურად ჰქონდა ინტერვიუში კითხვაზე
რომ იყო ძირითადად ეს, უბრალოდ კოდი up რაღაც, რათა შეამოწმოს
თუ არა ხე არის ორობითი ძებნა ხე,
და ა.შ. პირველი რაც მან გააკეთა იყო მხოლოდ შეამოწმეთ
თუ მარცხენა და მარჯვენა სწორია, ხოლო შემდეგ iterate დახვდა.
მაგრამ თქვენ არ შეგიძლიათ უბრალოდ რომ, თქვენ უნდა ტრეკზე
იმისა, რომ ახლა, რომ მე წასული მარცხნივ 7,
ყველაფერი ამ subtree უნდა იყოს არანაკლებ 7.
სწორი ალგორითმი სჭირდება ტრეკზე
საქართველოს ფარგლებს გარეთ, რომ ღირებულებების შესაძლოა ხარობს სისტემაში
ჩვენ არ გავლა ყველა მათგანი.
არსებობს ლამაზი რეციდივის მიზეზი,
თუმცა ჩვენ არ მიღებული იმ, ან ჩვენ ვერ მიიღებენ მათ,
განსაზღვრის რამდენი იქ სინამდვილეში.
ასე რომ 14 მათგანი.
იდეა, როგორ გავაკეთებთ მათემატიკურად ჰგავს,
შეგიძლიათ აირჩიოთ ნებისმიერი ერთი უნდა იყოს root node,
და მაშინ თუ მე აირჩიოთ 7 იყოს root node,
მაშინ არსებობს, ვთქვათ, ზოგიერთი ნომრები, რომ შეიძლება იყოს ჩემი მარცხენა კვანძში,
და არსებობს ციფრები, რომ შეიძლება ჩემი უფლება კვანძში,
მაგრამ თუ მე n სულ ციფრები, მაშინ თანხა, რომელიც შეიძლება წავიდეს მარცხენა
პლუს თანხა, რომელიც შეიძლება წავიდეს უფლება N - 1.
ასე დარჩენილი ციფრები, რომ მათ უნდა მიეცეთ საშუალება წასვლა ან მარცხნივ ან მარჯვნივ.
როგორც ჩანს რთული, რომ თუ მე ზუსტად 3 პირველი მაშინ ყველაფერს აქვს წასვლა მარცხენა
მაგრამ თუ მე ზუსტად 7, მაშინ ზოგი რამ შეიძლება მარცხენა და ზოგი რამ შეიძლება გადადით მარჯვნივ.
და '3 პირველი "მე ყოფილა ყველაფერი შეუძლია უფლება.
მართლაც, თქვენ უბრალოდ უნდა ვიფიქროთ, როგორც,
რამდენი რამ შეიძლება ადამიანმა შემდეგ ეტაპზე ხე.
და საქმე აღმოჩნდება 14; ან თქვენ შეგიძლიათ დახაზოთ ყველა მათგანი,
და შემდეგ თქვენ მიიღებთ 14.
>> უკან აქ,
"წესრიგიანი ბინარული ხეები გრილი რადგან ჩვენ შეგიძლიათ მოძებნოთ მეშვეობით მათ
ძალიან მსგავსი გზა ძებნას მეტი დახარისხებული მასივი.
ამისათვის ჩვენ იწყება root და მუშაობა ჩვენი გზა ქვემოთ ხე
მიმართ ფოთლები, შემოწმების თითოეული კვანძის ღირებულებების წინააღმდეგ ღირებულებები ჩვენ ეძებს.
თუ მიმდინარე კვანძის ს მნიშვნელობა ნაკლებია ღირებულების ჩვენ ვეძებთ,
თქვენ გადასვლა შემდეგ კვანძის უფლება შვილი.
წინააღმდეგ შემთხვევაში თქვენ გადადით კვანძის მარცხენა შვილი.
რაღაც მომენტში, თქვენ ან იპოვოს ღირებულება თქვენ ვეძებთ, ან თქვენ გადაეყარონ null,
მითითებით ღირებულება არ in ხე. "
მე უნდა მეთოდით გადასინჯვის ხე გვქონდა ადრე, რომ ყველაფერს იღებენ მეორე.
მაგრამ ჩვენ გვინდა, რომ ეძებოთ თუ არა 6, 10 და 1 არიან ხე.
ასე რომ, რაც იყო, 7, 9, 3, 6. Okay.
ნომრები გსურთ ეძებოთ, ჩვენ გვინდა გამოიყურებოდეს up 6.
როგორ აკეთებს ამას ალგორითმი მუშაობს?
ასევე, ჩვენ ასევე გვაქვს ძირეული მომცეთ ჩვენი ხე.
და ჩვენ გვინდა წასვლა root და აცხადებენ, ეს ღირებულება ტოლია ღირებულების ჩვენ ეძებს?
ამიტომ, ჩვენ ვეძებთ 6, ამიტომ არ ემთხვევიან.
ამიტომ, ჩვენ ვაპირებთ შენარჩუნება, და ახლა ჩვენ ვამბობთ, okay, ასე 6 ნაკლებია, ვიდრე 7.
ნიშნავს ეს გვინდა წასვლა მარცხენა ან არ გვინდა წასვლა უფლება?
[სტუდენტური] მარცხნივ. >> Yeah.
ეს მნიშვნელოვნად ადვილია, ყველა თქვენ უნდა გააკეთოთ გავამახვილო ერთ შესაძლო კვანძის ხე
და მაშინ don't - ის ნაცვლად ცდილობს ვფიქრობ თქვენს ხელმძღვანელი,
okay, თუ ნაკლები, შემიძლია წასვლა მარცხენა ან მარჯვენა
უბრალოდ ეძებს ამ სურათს, ძალიან ნათელია, რომ მე წასვლა მარცხენა
თუ ამ კვანძის მეტია ღირებულება რომ ვეძებ.
ასე, რომ თქვენ გადადით მარცხნივ, ახლა მე ღამის 3.
მინდა - 3 ნაკლებია, ვიდრე ღირებულება ვეძებ, რომელიც 6.
ამიტომ, ჩვენ გადადით უფლება, და ახლა დასრულდება up at 6,
რაც ღირებულება ვეძებ, ამიტომ იქნება TRUE.
შემდეგი ღირებულება მე ვაპირებ ვეძებოთ არის 10.
Okay. ასე 10, ახლა, აპირებს - შეწყვიტა, რომ - აპირებს დაიცვას root.
ახლა, 10 იქნება მეტი 7, ამიტომ მინდა გამოიყურებოდეს მარჯვნივ.
მე ვაპირებ გადმოდიოდნენ აქ, 10 იქნება მეტი 9,
ამიტომ მე ვაპირებ მინდა თვალი მარჯვნივ.
მე მეტი აქ, მაგრამ აქ ახლა მე ზე null.
რა გავაკეთო, თუ მე მოხვდა null?
[სტუდენტური] დაბრუნება ყალბი? >> Yeah. მე ვერ 10.
1 იქნება თითქმის იდენტურია შემთხვევაში,
გარდა უბრალოდ უნდა flipped; ნაცვლად ეძებს
ქვემოთ მარჯვენა მხარეს, მე ვაპირებ თვალი ქვევით მარცხენა მხარეს.
>> ახლა ვფიქრობ, რეალურად მისაღებად კოდი.
აი აქ - გახსენით CS50 ელექტრო და ნავიგაცია თქვენი გზა არსებობს,
მაგრამ თქვენ შეგიძლიათ უბრალოდ ის სივრცეში.
ალბათ იდეალური ამას სივრცეში,
იმიტომ, რომ ჩვენ შეგვიძლია მუშაობა სივრცეში.
"პირველი, ჩვენ გვჭირდება ახალი ტიპის განმარტება ორობითი ხე კვანძის შემცველი int ღირებულებებს.
გამოყენება boilerplate typedef ქვემოთ
შექმნა ახალი ტიპის განმარტება node in ორობითი ხე.
თუ თქვენ გაქვთ დავრჩებოდით. . . "Blah, blah, blah. Okay.
მოდით დააყენა boilerplate აქ,
typedef struct კვანძის და კვანძის. Yeah, okay.
ასე რომ რა სფეროებში ჩვენ ვაპირებთ გვინდა ჩვენს კვანძის?
[სტუდენტური] Int და შემდეგ ორი პოინტერები?
>> Int ღირებულება, ორი პოინტერები? როგორ შემიძლია წერენ პოინტერები?
[სტუდენტური] Struct. >> მე უნდა zoom შემოსული ჰო, ისე struct კვანძის * დაუტოვებიათ,
და struct კვანძის * უფლება.
და მახსოვს, განხილვის ბოლო დროს,
რომ ეს აზრი არ აქვს, ეს აზრი არ აქვს,
ამ აზრი არა აქვს.
თქვენ უნდა ყველაფერს, რათა განისაზღვროს ამ რეკურსიული struct.
Okay, ასე რომ რა ჩვენი ხე აპირებს გამოიყურებოდეს.
თითქოს ჩვენ აქ trinary ხე, მაშინ კვანძის შეიძლება გამოიყურებოდეს B1, B2, struct კვანძის * B3,
სადაც B არის ფილიალი - ფაქტობრივად, მე მეტი გაიგეს იგი დაუტოვებიათ, შუა, მარჯვენა, მაგრამ რასაც.
ჩვენ მხოლოდ აინტერესებს ორობითი, ამიტომ უფლება, დაუტოვებიათ.
"ახლა განაცხადოს გლობალური კვანძის * ცვლადი ამისთვის ფესვი ხე."
ამიტომ ჩვენ არ ვაპირებთ გავაკეთოთ, რომ.
იმისათვის, რომ რამ ოდნავ უფრო რთული და უფრო განზოგადებული,
არ გვექნება გლობალური კვანძის ცვლადი.
ამის ნაცვლად, მთავარ ჩვენ ვაცხადებთ ჩვენი ყველა კვანძის რამ,
და ეს იმას ნიშნავს რომ ქვემოთ, როდესაც ჩვენ ვიწყებთ გაშვებული
ჩვენი შეიცავს ფუნქცია და ჩვენი ჩანართით ფუნქცია,
ნაცვლად ჩვენი შეიცავს ფუნქციის გამოყენებით ამ გლობალურ კვანძის ცვლადი,
ჩვენ ვაპირებთ აქვს მიიღოს როგორც არგუმენტი ხე რომ ჩვენ გვსურს პროცესში.
მქონე გლობალური ცვლადი უნდა მიიღოს რამ ადვილია.
ჩვენ ვაპირებთ, რათა რამ ჩვენზე მეტი.
ახლა მიიღოს წუთი ან ასე უბრალოდ ასეთი რამ,
აქ შიგნით ძირითადი გსურთ მისი შექმნა ამ ხეს, და რომ ყველა გსურთ.
სცადეთ და მშენებლობა ხე თქვენს მთავარ ფუნქციას.
>> Okay. ასე, რომ თქვენ არც კი უნდა არ აშენდა ხის მთელი გზა არ არის.
მაგრამ არავის აქვს რაღაც შემეძლო დახევის up
რათა ნახოთ, თუ როგორ შეიძლება დავიწყოთ აშენებს ასეთი ხე?
[სტუდენტური] ვინმეს banging, ცდილობდა.
[Bowden] Anyone კომფორტულად იგრძნონ იმ ხის სამშენებლო?
[სტუდენტური] რა თქმა უნდა. ეს არ გაკეთებულა. >> ეს ჯარიმა. ჩვენ შეგვიძლია მხოლოდ დასრულდება -
OH, შეგიძლიათ შეინახოთ? Hooray.
ასე რომ აქ გვაქვს - Oh, მე ოდნავ შეწყვიტა.
ვარ zoomed წელს?
მიუახლოვდით, გადახვევა გარეთ. >> მე მაქვს შეკითხვა. >> Yeah?
[სტუდენტური] როდესაც თქვენ განსაზღვროს struct, რომლებიც რამ, როგორიცაა ინიციალიზაცია არაფრის?
[Bowden] მდებარ >> Okay. ასე, რომ თქვენ უნდა ინიციალიზაცია -
[Bowden] მდებარ როდესაც განსაზღვრავენ, ან როდესაც თქვენ გამოაცხადოს struct,
იგი არ არის ინიციალიზაცია მიერ default; უბრალოდ მინდა თუ განაცხადოს int.
ეს ზუსტად იგივე. ეს იგივეა, თითქოს თითოეულ ინდივიდუალური სფეროები
შეიძლება ჰქონდეს ნაგვის ღირებულების იგი. >> და შეიძლება განისაზღვროს - ან განაცხადოს struct
ისე, რომ ის არ ვრთავ მათ?
[Bowden] დიახ. ასე რომ, მალსახმობი ინიციალიზაციისას სინტაქსი
აპირებს ჰგავს -
არსებობს ორი გზა, ჩვენ შეგვიძლია ამის გაკეთება. მიმაჩნია, რომ უნდა კომპილირება
რომ დავრწმუნდეთ Clang ასევე აკეთებს ამას.
ბრძანებით არგუმენტები, რომ მოდის struct,
თქვენ დააყენა როგორც ბრძანებით არგუმენტები შიგნით ამ Curly braces.
ასე რომ, თუ გსურთ ინიციალიზაცია მას 9 დატოვა იყოს null და შემდეგ სწორი იყოს null,
ეს იქნება 9, null, null.
ალტერნატიული არის, და რედაქტორი არ მოსწონს ეს სინტაქსი,
და ეს ფიქრობს მინდა ახალი ბლოკი,
მაგრამ ალტერნატიული არის რაღაც მსგავსი -
აქ, მე ამას ახალ ხაზზე.
შეგიძლიათ პირდაპირ ვთქვა, მე დაგვავიწყდეს ზუსტი სინტაქსი.
ასე რომ შეგიძლიათ პირდაპირ მიმართოს მათ სახელი და აცხადებენ,
. გ, ან. ღირებულება = 9. მარცხენა = null.
მე გამოცნობა ამ საჭიროებს მძიმეები.
. უფლება = NULL, ამიტომ ამ გზით თქვენ არ
რეალურად უნდა იცოდეთ ბრძანებით struct,
და როდესაც თქვენ კითხულობთ ამ, გაცილებით უფრო ზუსტად რომ ვთქვათ
იმაზე, თუ რა ღირებულების ის მიმდინარეობს ინიციალიზაცია to.
>> ეს ხდება, რომ ერთი რამ, რომ -
ასე რომ, ყველაზე ნაწილი, C + + არის superset of C.
შეგიძლიათ მიიღოს C კოდი, გადატანა მეტი C + +, უნდა შეადგინოს.
ეს არის ერთი რამ, რომ C + + არ უჭერს მხარს, ასე რომ, ადამიანებს ტენდენცია არ უნდა გაეკეთებინათ ეს.
არ ვიცი თუ ეს ერთადერთი მიზეზი ხალხი ტენდენცია არ უნდა გააკეთოს ის,
მაგრამ შემთხვევაში სადაც მე გამოყენება დასჭირდა საჭიროა მუშაობა C + + და ა.შ. მე ვერ გამოიყენოს ეს.
კიდევ ერთი მაგალითი, რომ რაღაც არ მუშაობს ერთად C + + არის
როგორ malloc დააბრუნებს "ბათილად *," ტექნიკურად,
მაგრამ თქვენ შეიძლება უბრალოდ, ვამბობთ char * x = malloc რასაც,
და ეს ავტომატურად იქნება მიცემული რომ char *.
რომ ავტომატური მსახიობი არ ხდება C + +.
რომ არ კომპილირდება, და თქვენ ამას მკაფიოდ უნდა ითქვას,
char *, malloc, რასაც, რომ მიიღო ის, რომ char *.
არ არსებობს ბევრი რამ, რომ C და C + + ვერ შეთანხმებულან,
მაგრამ იმ ორი.
ასე რომ ჩვენ წავიდეთ ერთად ამ სინტაქსს.
მაგრამ მაშინაც კი, თუ ჩვენ არ წავიდეთ ერთად, რომ სინტაქსი,
რა არის - შეიძლება იყოს ცუდი ეს?
[სტუდენტური] მე არ უნდა dereference ეს? >> Yeah.
გახსოვდეთ, რომ arrow აქვს დაფარული dereference,
და ასე, როცა ჩვენ უბრალოდ საქმე struct,
ჩვენ გვინდა გამოვიყენოთ. მიიღოს საათზე სფეროში შიგნით struct.
და მხოლოდ ახლა ვიყენებთ arrow არის, როცა ჩვენ გვსურს რომ -
ასევე, arrow უდრის -
არის ის, რაც მას იმის მანიშნებელი, თუ გამოიყენება arrow.
ყველა arrow საშუალებებზე, dereference ამ, ახლა მე ზე struct, და შემიძლია კიდევ სფეროში.
ან კიდევ სფეროში პირდაპირ ან dereference და მიიღეთ სფეროში -
ვფიქრობ ეს უნდა იყოს მნიშვნელობა.
მაგრამ აქ მე საქმე მხოლოდ struct, არ მომცეთ struct,
და ამიტომ მე ვერ გამოიყენებს arrow.
მაგრამ ამ სახის რამ შეგვიძლია გავაკეთოთ ყველა კვანძების.
Oh ღმერთი ჩემი.
ეს არის 6, 7, და 3.
მაშინ ჩვენ შეგვიძლია შექმნას ფილიალები ჩვენი ხე, რომ შეგვიძლია 7 -
ჩვენ შეგვიძლია არ, მისი მარცხენა უნდა აღვნიშნო, რომ 3.
ასე როგორ უნდა გავაკეთოთ, რომ?
[სტუდენტები, გაუგებარია] >> Yeah. მისამართი node3,
და თუ არ აქვს მისამართი, მაშინ უბრალოდ არ შეადგინოს.
მაგრამ გვახსოვდეს, რომ ეს არის მითითებას შემდეგი კვანძების.
უფლება უნდა აღვნიშნო, რომ 9,
და 3 უნდა აღვნიშნო უფლება 6.
ვფიქრობ, ეს არის სრულ მზადყოფნაში. ნებისმიერი კომენტარი ან კითხვები?
[სტუდენტი გაუგებარია] root იქნება 7.
ჩვენ შეგვიძლია უბრალოდ, ვამბობთ კვანძის * ptr =
ან ფესვი, = & node7.
>> ჩვენი მიზნებისათვის, ჩვენ ვაპირებთ იყოს საქმე ჩანართით,
ამიტომ ჩვენ ვაპირებთ მინდა დაწერა ფუნქციის ჩასასმელად ამ ორობითი ხე
და ჩადეთ არის აუცილებლად ვაპირებ მოვუწოდო malloc შექმნა ახალი კვანძის ამ ხეს.
ასე რამ ვაპირებთ მისაღებად ბინძურ იმ ფაქტით, რომ ზოგიერთი კვანძების
ამჟამად on დასტის
და სხვა კვანძების ვაპირებთ დასრულდება მდე შესახებ ბევრი როდესაც ჩვენ ჩადეთ მათ.
ეს არის შესანიშნავად მოქმედებს, მაგრამ ერთადერთი მიზეზი
ჩვენ ვერ გააკეთებს ამ თემაზე დასტის
არის იმიტომ რომ ასეთი contrived მაგალითია იმისა, რომ ჩვენ ვიცით,
ხე უნდა აშენდეს როგორც 7, 3, 6, 9.
თუ არ გვქონდა, მაშინ ჩვენ არ უნდა malloc პირველ რიგში.
როგორც ვნახავთ, მოგვიანებით, ჩვენ უნდა malloc'ing.
ახლავე ეს შესანიშნავად გონივრული მოათავსოთ დასტის,
მაგრამ მოდით შეცვალოთ ეს უნდა malloc განხორციელება.
ასე რომ თითოეული ეს არის იქნება რაღაც მსგავსი
კვანძის * node9 = malloc (sizeof (კვანძის)).
და ახლა ჩვენ ვაპირებთ უნდა გავაკეთოთ ჩვენი ქვითარი.
თუ (node9 == NULL) - მე არ მინდოდა, რომ -
დააბრუნოს 1, და შემდეგ შეგვიძლია გავაკეთოთ node9-> რადგან ახლა ეს მაჩვენებელი,
ღირებულების = 6, node9-> დაუტოვებიათ = NULL,
node9-> უფლება = NULL,
და ჩვენ ვაპირებთ უნდა გავაკეთოთ, რომ თითოეული იმ კვანძების.
ასე რომ ნაცვლად, მოდით ვთქვათ შიგნით ცალკე ფუნქცია.
მოდით ეძახით კვანძის * build_node,
და ეს გარკვეულწილად მსგავსი APIs ჩვენ უზრუნველყოფს Huffman კოდირებას.
ჩვენ გაძლევთ initializer ფუნქციების ხე
და deconstructor "ფუნქციები" მათთვის, ხეები და იგივე ტყეებში.
>> ასე რომ აქ ჩვენ ვაპირებთ აქვს initializer ფუნქცია
უბრალოდ აშენება კვანძის ჩვენთვის.
და ეს აპირებს გამოიყურებოდეს საკმაოდ ბევრი ზუსტად მოსწონს ეს.
და მე კი იქნება ზარმაცი და არ შეიცვლება სახელით ცვლადი,
მიუხედავად იმისა, რომ node9 აზრი არ აქვს უქმნით.
ოჰ, ვფიქრობ node9 ღირებულების არ უნდა ყოფილიყო 6.
ახლა ჩვენ შეგვიძლია დაბრუნების node9.
და აქ ჩვენ უნდა დაუბრუნდეს null.
ყველამ შეთანხმდნენ, რომ ზრდა-კვანძის ფუნქციას?
ახლა ჩვენ შეგვიძლია უბრალოდ მოვუწოდებთ, რომ ავაშენოთ ნებისმიერი კვანძის ერთად მოცემული მნიშვნელობა და null პოინტერები.
ახლა ჩვენ შეგვიძლია მოვუწოდებთ, რომ ჩვენ შეგვიძლია გავაკეთოთ კვანძი * node9 = build_node (9).
და მოდით. . .
6, 3, 7, 6, 3, 7.
და ახლა ჩვენ გვინდა შეიქმნა იგივე მითითებას,
გარდა ახლა ყველაფერი უკვე თვალსაზრისით პოინტერები
ასე აღარ მისამართი.
Okay. რა არის ბოლო რამ მინდა გავაკეთო?
არსებობს შეცდომის შემოწმება, რომ მე არ აკეთებს.
რას ააშენებს კვანძის დაბრუნების?
[სტუდენტი გაუგებარია] >> Yeah. თუ malloc ვერ მოხერხდა, ის ყველაფერს დაბრუნების null.
ამიტომ მე ვაპირებ lazily დააყენა მისი დანგრევა აქ ნაცვლად აკეთებს მდგომარეობა თითოეული.
თუ (node9 == NULL, ან - კი მარტივი,
ამ უდრის მხოლოდ იმ შემთხვევაში, თუ არ node9.
ასე რომ, თუ არ node9, ან არ node6, ან არ node3, ან არ node7, დაბრუნდნენ 1.
იქნებ ჩვენ უნდა ბეჭდვა malloc ვერ მოხერხდა, ან რაღაც.
[სტუდენტური] სიცრუეა ტოლია null ისევე?
[Bowden] ნებისმიერი ნულოვანი ღირებულება არის ყალბი.
ასე რომ null არის ნულოვანი ღირებულება.
ნულოვანი არის ნულოვანი ღირებულება. ცრუ არის ნულოვანი ღირებულება.
ნებისმიერი - საკმაოდ ბევრი მხოლოდ 2 ნულოვანი ღირებულებები null და ნულის
ყალბი მხოლოდ hash განისაზღვრება, როგორც ნულოვანი.
რომელიც ასევე ვრცელდება თუ ჩვენ ვაცხადებთ გლობალური ცვლადი.
თუ ჩავატარეთ კვანძის * root აქ,
მაშინ - ლამაზი რამ შესახებ გლობალური ცვლადები არის, რომ ისინი ყოველთვის საწყის ღირებულებას.
ეს არ არის ნამდვილი ფუნქციების, როგორ შიგნით აქ,
თუ ჩვენ გვაქვს, ისევე, node * ან კვანძის x.
ჩვენ არ გვაქვს, როგორია x.value, x.whatever,
ან ჩვენ შეგვიძლია ბეჭდვა მათ და ისინი შეიძლება თვითნებური.
ეს არ არის ნამდვილი გლობალური ცვლადები.
ასე რომ კვანძის root ან კვანძის x.
ჩვეულებრივ, ყველაფერი, რაც გლობალურ, თუ პირდაპირ არ ინიციალიზაცია ზოგიერთ ღირებულება,
აქვს ნულოვანი ღირებულება, როგორც მისი ღირებულება.
ასე რომ აქ, node * root, ჩვენ არ არის მკაფიოდ ინიციალიზაცია მას არაფერი,
ამიტომ მისი საწყისი მნიშვნელობა იქნება null, რომელიც ნულოვანი ღირებულება პოინტერები.
ნაგულისხმევი მნიშვნელობა x აპირებს ნიშნავს, რომ x.value არის ნულოვანი,
x.left არის null, და x.right არის null.
, რადგან ეს struct, ყველა სფეროებში struct იქნება ნულოვანი ღირებულებები.
ჩვენ არ უნდა გამოვიყენოთ, რომ აქ, თუმცა.
[სტუდენტური] structs განსხვავებულია, ვიდრე სხვა ცვლადები, და სხვა ცვლადები არის
ნაგვის ფასეულობები; ეს zeros?
[Bowden] სხვა ღირებულებები ძალიან. ასე რომ, x, x იქნება ნულოვანი.
თუ ეს გლობალურ ფარგლებს, მას თავდაპირველი ღირებულება. >> Okay.
[Bowden] ან პირველადი მნიშვნელობა მისცა ან ნულოვანი.
მე ვფიქრობ, რომ ზრუნავს ყველა ამ.
>> Okay. ასე რომ შემდეგი ნაწილი კითხვაზე სთხოვს,
"ახლა ჩვენ გვინდა დავწეროთ ფუნქცია მოუწოდა შეიცავს
ერთად პროტოტიპი bool შეიცავს int ღირებულება. "
ჩვენ არ ვაპირებთ ამის გაკეთებას bool შეიცავს int ღირებულება.
ჩვენი პროტოტიპი აპირებს გამოიყურებოდეს
bool შეიცავს (int ღირებულება.
და მაშინ ჩვენ ასევე ვაპირებთ უნდა გაიაროს ეს ხე
რომ ეს უნდა იყოს შემოწმების დაინახოს, თუ მას, რომ ღირებულება.
ასე რომ კვანძის * ხე). Okay.
და მაშინ ჩვენ შეგვიძლია ეძახით რაღაც მოსწონს,
იქნებ ჩვენ გვინდა printf ან რამე.
შეიცავს 6, ჩვენი ძირეული.
რომ უნდა დაუბრუნდეს ერთი, ან ნამდვილი,
ხოლო შეიცავს 5 root უნდა დაუბრუნდეს ყალბი.
ასე რომ მიიღოს მეორე განხორციელების.
თქვენ შეგიძლიათ ეს გააკეთოთ ან iteratively ან რეკურსიული.
ლამაზი რამ შესახებ გზა ჩვენ მითითებული რამ up არის, რომ
ეს lends თავად ჩვენი რეკურსიული გადაწყვეტა ბევრად უფრო ადვილია
ვიდრე გლობალური-ცვლადი ასე.
რადგან თუ ჩვენ უბრალოდ უნდა შეიცავს int ღირებულება, მაშინ ჩვენ არ გვაქვს გზა recursing ქვემოთ subtrees.
ჩვენ უნდა ჰქონდეს ცალკე დამხმარე ფუნქცია recurses ქვემოთ subtrees ჩვენთვის.
მაგრამ რადგან ჩვენ შეიცვალა მას მიიღოს ხე როგორც არგუმენტი,
რომელიც მას უნდა ყოველთვის პირველ რიგში,
ახლა ჩვენ შეგვიძლია recurse უფრო მარტივად.
ამიტომ iterative ან რეკურსიული, ჩვენ წავიდეთ ორივე,
მაგრამ ჩვენ ვხედავთ, რომ რეკურსიული მთავრდება მყოფი საკმაოდ მარტივია.
Okay. ვინმეს აქვს რაიმე შეგვიძლია ვიმუშაოთ?
>> [სტუდენტური] მაქვს iterative გადაწყვეტა. >> ყველა უფლება, iterative.
Okay, ეს გამოიყურება კარგი.
ასე რომ, მინდა ფეხით ჩვენს მეშვეობით იგი?
[სტუდენტური] რა თქმა უნდა. ასე რომ მითითებული Temp ცვლადის მისაღებად პირველი კვანძის ხე.
და მერე უბრალოდ looped საშუალებით ხოლო temp არ თანაბარი null,
ასე, ხოლო ჯერ კიდევ ხე, ვფიქრობ.
და თუ ღირებულება შეადგენს ღირებულების რომ Temp არის მიუთითებს,
მაშინ ის დააბრუნებს, რომ ღირებულება.
წინააღმდეგ შემთხვევაში, ის ამოწმებს, თუ ის მარჯვენა მხარეს ან მარცხენა მხარეს.
თუ თქვენ ოდესმე კიდევ სიტუაცია, სადაც არ არსებობს უფრო მეტი ხე,
მაშინ ის დააბრუნებს - ის ითიშება მარყუჟის და დააბრუნებს false.
[Bowden] Okay. ასე რომ, როგორც ჩანს კარგი.
ვინმეს აქვს რაიმე კომენტარს არაფერი?
მე არ მაქვს სისწორის კომენტარი ყველა.
ერთი რამ შეგვიძლია გავაკეთოთ არის ამ ბიჭს.
ოჰ, ეს აპირებს პატარა longish.
მე დაფიქსირება, რომ up. Okay.
>> ყველას უნდა ახსოვდეს, როგორ ternary მუშაობს.
არსებობს ნამდვილად იყო ტესტებში წარსულში
რომ გაძლევთ ფუნქციის ternary ოპერატორი,
და ამბობენ, თარგმნა ამ, რაღაც რომ არ გამოიყენებს ternary.
ასე რომ, ეს ძალიან ხშირი შემთხვევაში, როდესაც მე ვფიქრობ გამოიყენოს ternary,
აქ თუ რაღაც მდგომარეობა მითითებული ცვლადი რაიმე,
სხვაგან მითითებული, რომ იგივე ცვლადი რაღაც.
სწორედ ის, რაც ძალიან ხშირად შეიძლება გადაკეთდა ასეთი რამ
სადაც მითითებული, რომ ცვლადი ამ - ან, ასევე, არის ამ ჭეშმარიტი? მაშინ ეს, სხვას ეს.
[სტუდენტური] პირველი ის არის თუ ასეა, არა?
[Bowden] Yeah. გზა მე ყოველთვის წავიკითხავ არის, Temp შეადგენს ღირებულების მეტი temp ღირებულება,
მაშინ ეს, სხვას ეს. ის სვამს კითხვას.
არის თუ არა უფრო დიდი? მაშინ ნუ პირველი რაც. Else გავაკეთოთ მეორე რამ.
მე თითქმის ყოველთვის - მსხვილი ნაწლავის, უბრალოდ - ჩემი უფროსი, წავიკითხე როგორც სხვაგან.
>> ვინმეს აქვს რეკურსიული გამოსავალი?
Okay. ეს ერთი ჩვენ ვაპირებთ - ეს შეიძლება იყოს უკვე დიდი,
მაგრამ ჩვენ ვაპირებთ, რათა ის უფრო უკეთესი.
ეს არის საკმაოდ ბევრი იგივე ზუსტი იდეა.
უბრალოდ, კარგად, გნებავთ ასახსნელად?
[სტუდენტური] რა თქმა უნდა. ამიტომ ჩვენ მიღების დარწმუნებული ვარ, რომ ხე არ არის NULL პირველი,
რადგან თუ ხე null მაშინ ის დაბრუნებას აპირებს ცრუ იმიტომ, რომ ჩვენ არ ი.
და თუ მაინც ხე, ჩვენ წასვლას - ჩვენ პირველი შეამოწმოს თუ ღირებულება მიმდინარე კვანძში.
TRUE თუ ეს და, თუ არ ჩვენ recurse მარცხენა ან მარჯვენა.
Does რომ ხმის შესაბამისი? >> MM-hmm. (შეთანხმება)
ასე რომ ეს არის თითქმის - სტრუქტურულად ძალიან ჰგავს iterative გადაწყვეტა.
უბრალოდ, ნაცვლად recursing, გვქონდა ხოლო loop.
და ბაზის შემთხვევაში აქ, სადაც ხე არ თანაბარი null
იყო მდგომარეობა, რომლის თანახმადაც ჩვენ იფეთქა of ხოლო loop.
ისინი ძალიან გავს. მაგრამ ჩვენ ვაპირებთ ამ ერთი ნაბიჯით შემდგომი.
ახლა, ჩვენ იგივე აქ.
გაითვალისწინეთ ჩვენ დაბრუნების იგივე ორივე ამ ხაზები,
გარდა ერთი არგუმენტი არის სხვადასხვა.
ამიტომ, ჩვენ ვაპირებთ, რათა რომ შევიდა ternary.
მე მოხვდა ვარიანტი რაღაც, და ეს გააკეთა სიმბოლო. Okay.
ამიტომ, ჩვენ ვაპირებთ დაბრუნებას შეიცავს, რომ.
ეს დღითიდღე იყოს მრავალჯერადი ხაზები, ასევე, zoomed მასში არის.
ჩვეულებრივ, როგორც სტილისტური რამ, არა მგონია, ბევრი ადამიანი
დააყენა სივრცეში შემდეგ arrow, მაგრამ ვფიქრობ, თუ თქვენ თანმიმდევრული, ეს ჯარიმა.
თუ მნიშვნელობა ნაკლებია ხის ღირებულება, ჩვენ გვინდა recurse on ხე მარცხენა
სხვაგან გვინდა recurse on ხე უფლება.
ასე რომ იყო ნაბიჯი ერთი მიღების ამ სახეს პატარა.
ნაბიჯი ორ მიღების ამ სახეს პატარა -
ჩვენ შეგვიძლია გამოვყოთ ეს რამდენიმე სტრიქონი.
Okay. ნაბიჯი ორი რაც მას გამოიყურებოდეს პატარა აქ არის,
ასე დაბრუნებული მნიშვნელობა ტოლია ხე ღირებულებით, ან შეიცავს რასაც.
>> ეს არის მთავარი.
მე არ ვარ დარწმუნებული, თუ მისი თქმით, მკაფიოდ კლასში,
მაგრამ ეს ე.წ. მოკლე ჩართვა შეფასება.
იდეა აქ არის ღირებულება == ხე ღირებულებით.
თუ ეს მართალია, მაშინ ეს მართლაც ასეა, და ჩვენ გვინდა "ან" რომ რაც მეტი აქ.
ასე გარეშე კი ფიქრი რაც მეტი აქ,
რა არის მთელი გამოხატულება დაბრუნებას აპირებს?
[სტუდენტური] True? >> Yeah, რადგან სიმართლეა არაფერი,
or'd - ან ნამდვილი or'd ერთად არაფერი აუცილებლად ჭეშმარიტი.
ასე რომ როგორც კი ჩვენ ვხედავთ დაბრუნებული მნიშვნელობა = ხე ღირებულებით,
ჩვენ უბრალოდ დაბრუნებას აპირებს ჭეშმარიტი.
კი არ აპირებს recurse შემდგომი შეიცავს ქვემოთ ხაზი.
ჩვენ შეუძლია მიიღოს ამ ერთი ნაბიჯით შემდგომი.
დაბრუნება ხე არ თანაბარი null და ყველა ამ.
იგი გახადა ერთი ხაზი ფუნქციონირებს.
ეს არის ასევე მაგალითი მოკლე ჩართვა შეფასება.
მაგრამ ახლა ეს იგივე იდეა -
ნაცვლად - ასე რომ, თუ ხე არ თანაბარი null - ან, ისევე,
თუ ხე არ თანაბარი null, რომელიც ცუდი საქმე,
თუ ხე შეადგენს null, მაშინ პირველი მდგომარეობა იქნება ყალბი.
ასე რომ ცრუ anded ერთად არაფერი იქნება რა?
[სტუდენტური] ყალბი. >> Yeah. ეს არის მეორე ნახევარში მოკლე ჩართვა შეფასება,
აქ თუ ხე არ თანაბარი null, მაშინ ჩვენ არ ვაპირებთ თუნდაც წასვლა -
ან თუ ხე არ თანაბარი null, მაშინ ჩვენ არ ვაპირებთ ღირებულება == ხე ღირებულებით.
ჩვენ უბრალოდ აპირებს დაუყოვნებლივ დაბრუნებას ყალბი.
რაც მნიშვნელოვანია, რადგან თუკი მას არ მოკლე ჩართვა შეაფასოს,
მაშინ თუ ხე არ თანაბარი null, ამ მეორე მდგომარეობა აპირებს seg ბრალია,
რადგან ხე-> ღირებულება dereferencing null.
ასე რომ, რომ. შეუძლია ამ - გადაეტანა ერთხელ დასრულდა.
ეს არის ძალიან გავრცელებული რამ ასევე, არ ვდებთ ამ ერთ ხაზს ამისა,
მაგრამ საერთო რამ პირობებში, შესაძლოა, სწორი არ აქ,
მაგრამ თუ (ხე = NULL, და ხე-> ღირებულების == ღირებულების), გააკეთოს რასაც.
ეს არის ძალიან საერთო მდგომარეობა, სადაც ნაცვლად, რომელმაც
მოხსნა ამ ორ IFS, სადაც მინდა, არის ხე null?
Okay, ეს არ null, ამიტომ ახლა არის ხე ღირებულების ტოლია მნიშვნელობა? ამის გაკეთება.
ამის ნაცვლად, ამ მდგომარეობაში, ეს არასდროს არ seg ბრალია
იმიტომ, რომ ეს იქნება შესვენება, თუ ეს მოხდება, რომ იყოს null.
ისე, ვფიქრობ, თუ თქვენი ხე არის სრულიად არასწორი მაჩვენებელი, მას შეუძლია კვლავ seg ბრალია,
მაგრამ მას არ შეუძლია seg ბრალია თუ ხე null.
თუ ეს იყო null, ეს იქნებოდა შესვენება წინაშე ოდესმე dereferenced მაჩვენებელი პირველ რიგში.
[სტუდენტური] არის ამ ე.წ. ზარმაცი შეფასება?
>> [Bowden] Lazy შეფასება ცალკე ამბავია.
Lazy შეფასება უფრო მოსწონს თქვენ ეკითხებით ღირებულება,
თქვენ ჰკითხავთ გამოვთვალოთ ღირებულება, სახის, მაგრამ თქვენ არ სჭირდება დაუყოვნებლივ.
ასე რომ, სანამ თქვენ ნამდვილად სჭირდება, არ არის შეფასებული.
ეს არ არის ზუსტად იგივე, მაგრამ Huffman pset,
იგი ამბობს, რომ ჩვენ "lazily" წერენ.
მიზეზი გავაკეთოთ, რომ ეს იმიტომ რომ ჩვენ რეალურად buffering ჩაწერის -
ჩვენ არ გვინდა, რომ წერენ ინდივიდუალური ბიტი დროს,
ან ინდივიდუალური bytes დროს, ჩვენ ნაცვლად გვინდა ბლოკი bytes.
მაშინ კიდევ გვაქვს ბლოკი ბაიტი, მაშინ ჩვენ დავწეროთ ის.
მიუხედავად იმისა, რომ თქვენ ჰკითხავთ ეს დაწერა - და fwrite და fread იგივე სახის რამ.
ისინი ბუფერში შესანახი თქვენი ნათქვამია და წერს.
მიუხედავად იმისა, რომ თქვენ ჰკითხავთ ეს დაწერა დაუყოვნებლივ, მას ალბათ არ.
და ვერ იქნება დარწმუნებული, რომ ყველაფერი იქნება დაწერილი
სანამ რეკავთ hfclose ან რასაც იგი,
რომელიც შემდეგ ამბობს, okay, მე დახურვის ჩემი ფაილი,
ეს ნიშნავს, რომ მინდა უკეთესი დაწეროს ყველაფერი მე არ წერია ამჟამად.
მას არ აქვს უნდა დაწეროთ ყველაფერს
სანამ არ ვკეტავთ ფაილი, და მაშინ უნდა.
ასე რომ უბრალოდ რა ზარმაცი - ის ელოდება სანამ ის მოხდება.
ეს - მიიღოს 51 და თქვენ წასვლას იგი უფრო დეტალურად,
რადგან OCaml და ყველაფერი 51, ყველაფერი უკან.
არ არსებობს iterative გადაწყვეტილებები, ძირითადად.
ყველაფერი უკან და ზარმაცი შეფასება
იქნება მნიშვნელოვანი ბევრი გარემოებები
სადაც, თუ არ lazily შეაფასოს, რომ ნიშნავს -
მაგალითად არის ნაკადულები, რომლებიც უსასრულოდ გრძელი.
თეორიულად, შეგიძლიათ წარმოიდგინოთ, რომ ბუნებრივი ნომრები ნაკადი 1-2-3-4-5-6-7,
ამიტომ lazily შეაფასეს რამ ჯარიმა.
თუ მე ვიტყვი, მინდა მეათე ნომერი, მერე შეუძლია შეაფასოს მდე მეათე ნომერი.
თუკი მინდა მეასედ ნომერი, მერე შეუძლია შეაფასოს მდე მეასედ ნომერი.
გარეშე ზარმაცი შეფასება, მაშინ იგი აპირებს ცდილობენ შეაფასონ ყველა ნომრები დაუყოვნებლივ.
თქვენ შეფასებისას უსასრულოდ ბევრი ნომრები, და ეს მხოლოდ შეუძლებელია.
ასე რომ ბევრი გარემოებები, სადაც ზარმაცი შეფასება
მხოლოდ არსებითი მიღების რამ მუშაობა.
>> ახლა ჩვენ გვინდა დავწეროთ ჩანართით, სადაც ჩანართით იქნება
ანალოგიურად შეცვლის თავის განმარტება.
ასე რომ ახლა ეს bool ჩანართით (int value).
ჩვენ ვაპირებთ, რომ შეიცვალოს, რომ bool ჩანართით (int ღირებულება, node * ხე).
ჩვენ რეალურად შეიცვლება, რომ კვლავ bit, ვნახავთ, თუ რატომ.
და მოდით გადაადგილება build_node, მხოლოდ heck ეს,
ზემოთ ჩადეთ ასე არ გვაქვს დაწერა ფუნქციის პროტოტიპი.
რაც მინიშნება, რომ თქვენ უნდა გამოყენებით build_node წელს ჩანართით.
Okay. Take წუთი რომ.
ვფიქრობ გადაარჩინა გადასინჯვის თუ გსურთ გაიყვანოს ამისა,
ან, ყოველ შემთხვევაში, მე ახლა.
მინდოდა მცირე შესვენების ფიქრი ლოგიკა ჩანართით,
თუ თქვენ ვერ ვფიქრობ იგი.
ძირითადად, თქვენ მხოლოდ ოდესმე იქნება ჩასმა საათზე ფოთლები.
მსგავსად, თუ ჩადეთ 1, მაშინ მე აუცილებლად იქნება ჩასმა 1 -
მე შეცვლის შავი - I'll იყოს ჩასმა 1 ზე აქ.
ან თუ ჩადეთ 4, მინდა იყოს ჩასმა 4 ზე აქ.
ასე რომ არ აქვს მნიშვნელობა, თუ რას აკეთებთ, თქვენ უნდა ჩასმა საათზე ფოთოლი.
ყველა თქვენ უნდა გააკეთოთ iterate ქვემოთ ხე სანამ თქვენ მიიღებთ კვანძში
რომ უნდა იყოს კვანძის მშობელი, ახალი კვანძის მშობელი,
და შემდეგ შეცვალოს მისი მარცხენა ან მარჯვენა კურსორი, რაც დამოკიდებულია თუ არა
ეს მეტია ან ნაკლებია, ვიდრე მიმდინარე კვანძში.
ცვლილება, რომელიც მაჩვენებელმა აღვნიშნო თქვენს ახალ კვანძში.
ამიტომ iterate ქვემოთ ხე, გახადოს ფოთოლი წერტილი ახალი კვანძში.
ასევე ვფიქრობ, რატომ, რომ კრძალავს ტიპის სიტუაციის წინაშე,
სადაც მე აშენებული ორობითი ხე, სადაც ეს იყო სწორი
თუ თქვენ მხოლოდ შევხედე ერთ კვანძში,
მაგრამ 9 იყო მარცხნივ 7 თუ iterated ქვემოთ ყველა გზა.
ასე რომ შეუძლებელია ამ სცენარით, რადგან -
ვიფიქროთ ჩასმა 9 ან რამე; პირველივე კვანძში,
მე ვაპირებ ვხედავ 7 და მე უბრალოდ აპირებს მისვლას უფლება.
ასე რომ არ აქვს მნიშვნელობა რა გავაკეთო, თუ მე ჩასმა მიერ აპირებს ფოთოლი,
და ფოთოლი გამოყენებით შესაბამისი ალგორითმი,
ეს იქნება შეუძლებელი ჩემთვის ჩასასმელად 9 მარცხნივ 7
რადგან როგორც კი მოხვდა 7 მე ვაპირებ წასვლა უფლება.
ვინმეს აქვს რაიმე იწყება?
[სტუდენტური] გავაკეთო. >> დარწმუნებული.
[სტუდენტი გაუგებარია]
[სხვა სტუდენტი, გაუგებარია]
[Bowden] ეს დასაფასებელია. Okay. მინდა განვმარტო?
>> [სტუდენტური] ვინაიდან ჩვენ ვიცით, რომ ჩვენ ჩასმა
ახალი კვანძების დასასრულს ხე,
მე looped საშუალებით ხე iteratively
სანამ მე მივიღე რომ კვანძის რომ მიუთითა null.
და მერე გადავწყვიტეთ, რომ ეს არც მარჯვენა მხარეს ან მარცხენა მხარეს
გამოყენებით ამ უფლების ცვლადი, ის მითხრა, სად უნდა თქვა.
და მაშინ, არსებითად, მე უბრალოდ, რომ ბოლო -
რომ Temp კვანძის წერტილი ახალი კვანძის რომ იგი შექმნა,
ან მარცხენა მხარეს ან მარჯვენა მხარეს, დამოკიდებულია რა ღირებულების უფლება იყო.
და ბოლოს, მე მითითებული ახალი კვანძის მნიშვნელობა ღირებულება მისი ტესტირება.
[Bowden] Okay, ასე ვხედავ ერთი საკითხი აქ.
ეს არის მსგავსად 95% გზა არსებობს.
ერთი საკითხი, რომელიც მე ვერ ვხედავ, ისევე, ამჯამად ვინმეს ვხედავთ საკითხი?
რა არის გარემოება, რომლის თანახმადაც ისინი დაარღვიოს გარეთ loop?
[სტუდენტური] თუ Temp არის null? >> Yeah. ასე რომ, თუ როგორ შესვენება გარეთ loop არის თუ Temp არის null.
მაგრამ რა გავაკეთოთ უფლება აქ?
მე dereference temp, რომელიც აუცილებლად null.
ასე რომ სხვა რამ რაც თქვენ გჭირდებათ რომ გააკეთოთ, არის არა მხოლოდ ტრეკზე სანამ Temp არის null,
გსურთ ტრეკზე მშობელს ნებისმიერ დროს.
ჩვენ ასევე გვინდა კვანძის * მშობელს, ვფიქრობ ჩვენ შეგვიძლია შევინარჩუნოთ, რომ null თავდაპირველად.
ეს აპირებს აქვს უცნაური ქცევის ფესვი ხეს,
მაგრამ ამას კიდევ რომ.
თუ მნიშვნელობა მეტია რასაც, მაშინ temp = temp უფლება.
მაგრამ სანამ ჩვენ გავაკეთებთ, რომ, მშობელი = temp.
ან მშობლები ყოველთვის აპირებს თანაბარი temp? ის არის, რომ საქმე?
თუ temp არ null, მაშინ მე ვაპირებ ქვევით, არ აქვს მნიშვნელობა, რა,
დან კვანძის რისთვისაც Temp არის მშობელი.
ამიტომ მშობელი იქნება temp, და მერე გადავიდეს temp ქვემოთ.
ახლა არის temp null, მაგრამ მშობელს მიუთითებს მშობელი რაც null.
ასე ქვევით აქ, მე არ მინდა შექმნას უფლება უდრის 1.
ასე რომ გადავიდა უფლება, ასე რომ, თუ უფლება = 1,
და ვფიქრობ, თქვენც გსურთ -
თუ თქვენ გადატანა მარცხნივ, გსურთ უფლება ტოლია 0.
ანდა თუ ოდესმე გადასვლის უფლება.
ასე რომ უფლება = 0. თუ უფლება = 1,
ახლა ჩვენ გვსურს მშობელს უფლება მომცეთ newnode,
სხვაგან ჩვენ გვსურს მშობელი მარცხენა კურსორი newnode.
კითხვები რომ?
Okay. ასე რომ, ეს გზა ჩვენ - კარგად, ფაქტობრივად, ნაცვლად აკეთებს ეს
ჩვენ ნახევარი მოსალოდნელია გამოიყენოთ build_node.
და მაშინ თუ newnode შეადგენს null, დაბრუნდნენ ყალბი.
სწორედ რომ. ახლა, ეს არის ის, რაც ჩვენ მოსალოდნელია თქვენ უნდა გააკეთოს.
>> ეს არის ის, რაც პერსონალის გადაწყვეტილებები გავაკეთოთ.
მე არ ეთანხმებიან ამ როგორც "სწორი" გზა მიდის ამაზე
მაგრამ ეს შესანიშნავად ჯარიმა და ის იმუშავებს.
ერთი რამ, რომ ცოტა უცნაური ახლავე არის
თუ ხე იწყებს off როგორც null, ჩვენ კორიდორი null ხე.
ვფიქრობ ეს დამოკიდებულია, თუ როგორ განსაზღვრავს ქცევის გადადის null ხე.
მინდა ვფიქრობ, რომ თუ თქვენ კორიდორი null ხე,
მაშინ ჩასმა ღირებულება შევიდა null ხე
უნდა უბრალოდ დააბრუნოს ხე სადაც მხოლოდ ღირებულება ის არის, რომ ერთჯერადი კვანძში.
ნუ ხალხს ვეთანხმები, რომ? თქვენ შეიძლება, თუ სურდა,
თუ კორიდორი null ხე
და გსურთ ჩადეთ ღირებულება მივანიჭო, დაბრუნდნენ ყალბი.
ეს თქვენი გადასაწყვეტია, რათა განისაზღვროს, რომ.
იმისათვის რომ პირველი, რაც მე ვთქვი და მერე -
ასევე, თქვენ აპირებს უჭირთ აკეთებს, რადგან
ეს იქნება ადვილი, თუ გვქონდა გლობალური მომცეთ რამ,
მაგრამ ასე არ მოხდა, ასე რომ, თუ ხის არის null, არაფერი შეგვიძლია გავაკეთოთ ამის შესახებ.
ჩვენ შეგვიძლია მხოლოდ დაბრუნების ცრუ.
ამიტომ, მე ვაპირებ, რომ შეიცვალოს ჩანართით.
ჩვენ ტექნიკურად შეეძლო უბრალოდ შეცვალეთ ეს უფლება აქ,
როგორ ის iterating მეტი რამ,
მაგრამ მე ვაპირებ, რომ შეიცვალოს ჩასმა მიიღოს კვანძის ** ხე.
ორმაგი პოინტერები.
რას ნიშნავს ეს?
იმის ნაცვლად, რომ საქმე მითითებას კვანძების,
რამ მე ვაპირებ იყოს მანიპულირებენ ეს მაჩვენებელი.
მე ვაპირებ იყოს მანიპულირებენ ამ მაჩვენებელმა.
მე ვაპირებ იყოს მანიპულირების პოინტერები პირდაპირ.
ეს აზრი, რადგან, ვიფიქროთ Down -
ასევე, ახლავე ამ მიუთითებს null.
რა მინდა გააკეთოთ მანიპულირება ამ მაჩვენებელმა აღვნიშნო, რომ არ null.
მინდა ეს აღვნიშნო, რომ ჩემი ახალი კვანძში.
თუ მე მხოლოდ ტრეკზე მითითებას ჩემი პოინტერები,
მაშინ მე არ უნდა ტრეკზე მშობელი მაჩვენებელი.
მე შემიძლია მხოლოდ ტრეკზე თუ კურსორი არის მიუთითებს null,
და თუ მაჩვენებელი არის მიუთითებს null,
შეცვლის აღვნიშნო, რომ კვანძის მინდა.
და შემიძლია შეცვლის რადგან მე მომცეთ მაჩვენებელი.
ვნახოთ ამ წუთას.
თქვენ შეგიძლიათ რეალურად გავაკეთებთ რეკურსიული საკმაოდ მარტივად.
გვინდა ამის გაკეთება?
დიახ, ჩვენ ვაკეთებთ.
>> ვნახოთ ეს რეკურსიული.
პირველი, რა არის ჩვენი ბაზის შემთხვევაში იქნება?
თითქმის ყოველთვის ჩვენი ბაზის შემთხვევაში, მაგრამ რეალურად, ეს არის სახის სახიფათო.
რაც პირველხარისხოვანია, თუ (ხე == NULL)
ვფიქრობ ჩვენ უბრალოდ დაბრუნებას აპირებს ყალბი.
ეს განსხვავდება თქვენი ხე მყოფი null.
ეს არის მომცეთ თქვენი root მაჩვენებელი მყოფი null
რაც იმას ნიშნავს, რომ თქვენი root მაჩვენებელი არ არსებობს.
ასე ქვევით აქ, თუ
კვანძის * - მოდით უბრალოდ reuse ამ.
Node * root = NULL,
და მაშინ მე ვაპირებ მოვუწოდო ჩასმა ამით რაღაც,
ჩადეთ 4 შევიდა და root.
ამიტომ & root, თუ root არის კვანძის *
მაშინ & root იქნება კვანძის **.
ეს არის სწორი. ამ შემთხვევაში, ხე, აქ,
ხე არ არის null - ან ჩანართით.
აქ. ხე არ არის null; * ხე null, რომელიც სახვითი
რადგან თუ * ხე null, მაშინ მე შემიძლია მის მართვას
აქამდე აღვნიშნო, რომ რაც მე მინდა ის აღვნიშნო, რომ.
მაგრამ თუ ხე null, რაც იმას ნიშნავს, მე უბრალოდ დაინგრა აქ და განაცხადა null.
რომ არ აქვს აზრი. მე ვერაფერს, რომ.
თუ ხე null, დაბრუნდნენ ყალბი.
ამიტომ, მე ძირითადად უკვე განაცხადა რა ჩვენი რეალური ბაზის საქმე.
და რა არის, რომ იქნება?
[სტუდენტი გაუგებარია]
[Bowden] დიახ. ასე რომ, თუ (* ხე == NULL).
ეს ეხება საქმე აქ
აქ თუ ჩემი წითელი მაჩვენებელი არის კურსორი მე ფოკუსირებული,
ასე მოსწონს მე ფოკუსირებული ამ მაჩვენებელმა, ახლა მე ფოკუსირებული ამ მაჩვენებელმა.
ახლა მე ფოკუსირებული ამ მაჩვენებელმა.
ასე რომ, თუ ჩემი წითელი მაჩვენებელი, რომელიც ჩემი კვანძის **,
ოდესმე - თუ *, ჩემი წითელი მაჩვენებელი, ოდესმე null,
რაც იმას ნიშნავს, რომ ვარ შემთხვევაში მე აქცენტი მაჩვენებელი, ქულა -
ეს მაჩვენებელი, ეკუთვნის ფოთოლი.
მინდა შეცვალოთ ეს მაჩვენებელი აღვნიშნო, რომ ჩემი ახალი კვანძში.
დავბრუნდებით მეტი აქ.
ჩემი newnode იქნება მხოლოდ კვანძის * N = build_node (ღირებულება)
მაშინ N, თუ n = NULL, დაბრუნდნენ ყალბი.
Else გვინდა რომ შეიცვალოს რა მაჩვენებელი არის გაკეთებული მიუთითებს
აქამდე აღვნიშნო, რომ ჩვენი ახლად აშენებული კვანძში.
ჩვენ შეგვიძლია რეალურად გავაკეთოთ, რომ აქ.
იმის ნაცვლად, რომ ვამბობ, N, ვამბობთ * ხე = თუ * ხე.
ყველას გვესმის, რომ? რომ საქმე მითითებას პოინტერები,
ჩვენ შეგვიძლია შევცვალოთ null მითითებას აღვნიშნო, რომ რამ გვინდა მათ აღვნიშნო, რომ.
სწორედ ჩვენი ბაზის შემთხვევაში.
>> ახლა ჩვენი რეციდივი, ან ჩვენი უკან,
იქნება ძალიან გავს ყველა სხვა recursions ჩვენ ვაკეთებთ.
ჩვენ ვაპირებთ, რომ გსურთ ჩადეთ ღირებულება,
და ახლა მე ვაპირებ გამოიყენოთ ternary ისევ, მაგრამ რა არის ჩვენი მდგომარეობა იქნება?
რა არის ეს ჩვენ ვეძებთ, რათა მიიღოს გადაწყვეტილება გვინდა წასვლა მარცხენა ან მარჯვენა?
მოდით ეს ცალკე ნაბიჯები.
თუ (value <) რა?
[სტუდენტური] ხე მისი მნიშვნელობა?
[Bowden] ასე მახსოვს, რომ მე გაკეთებული -
[სტუდენტები, გაუგებარია]
[Bowden] ჰო, ისე უფლება აქ, ვთქვათ, რომ ეს მწვანე arrow
არის მაგალითი რა ხე გაკეთებული არის, არის მომცეთ ამ მაჩვენებელმა.
ასე რომ ნიშნავს მე მომცეთ მომცეთ 3.
Dereference ორჯერ გაისმა კარგი.
რა - როგორ გავაკეთო ეს?
[სტუდენტური] Dereference ერთხელ, და შემდეგ გააკეთოს arrow რომ გზა?
[Bowden] ასე (* ხე) არის dereference ერთხელ, -> ღირებულება
აპირებს მომეცი ღირებულება კვანძის რომ მე ირიბად მიუთითებს.
ასე, რომ შეიძლება ასევე დაწერა ** tree.value თუ თქვენ გსურთ, რომ.
ან მუშაობს.
თუ ეს საქმე, მაშინ მინდა მოვუწოდო ჩადეთ ერთად ღირებულება.
და რა არის ჩემი ახლდება კვანძის ** იქნება?
მინდა წასვლა მარცხენა, ასე ** tree.left იქნება ჩემი მარცხენა.
და მინდა მომცეთ რომ რამ
ასე რომ თუ მარცხენა მთავრდება მყოფი null მაჩვენებელი,
შემიძლია ცვლილებები ის აღვნიშნო, რომ ჩემი ახალი კვანძში.
>> და სხვა შემთხვევაში შეიძლება ძალიან მსგავსი.
მოდით რეალურად გააკეთოს, რომ ჩემი ternary ახლავე.
ჩადეთ ღირებულება თუ ფასეულობა <(** ხე). ღირებულება.
მაშინ ჩვენ გვინდა განაახლოს ჩვენი ** მარცხნივ,
სხვაგან გვინდა განაახლოს ჩვენი ** მარჯვნივ.
[სტუდენტური] არა, რომ მიიღოთ მომცეთ მაჩვენებელი?
[Bowden] გახსოვდეთ, რომ - ** tree.right არის კვანძის ვარსკვლავი.
[სტუდენტი გაუგებარია] >> Yeah.
** Tree.right ჰგავს ეს მაჩვენებელი ან რამე.
ასე ხდება მომცეთ, რომ, რომელიც მაძლევს რაც მე მინდა
საქართველოს მომცეთ, რომ ბიჭს.
[სტუდენტური] ვერ ჩვენ კვლავ რატომ ჩვენ გამოყენებით ორი პოინტერები?
[Bowden] Yeah. ასე რომ - არა, თქვენ შეგიძლიათ, და რომ გამოსავალი ადრე
იყო გზა ამის გაკეთება გარეშე აკეთებს ორ მითითებას.
თქვენ უნდა იყოს იგებს გამოყენებით ორი პოინტერები,
და ეს არის სუფთა გადაწყვეტა.
ასევე შეამჩნევთ, რომ, რა მოხდება თუ ჩემი ხე -
რა მოხდება თუ ჩემი root იყო null? რა მოხდება, თუ ამ შემთხვევაში სწორედ აქ?
ასე რომ კვანძის * root = NULL, ჩადეთ 4 შევიდა და root.
რა არის root იქნება ამის შემდეგ?
[სტუდენტი გაუგებარია] >> Yeah.
Root ღირებულება იქნება 4.
Root მარცხენა იქნება null, ძირეული უფლება იქნება null.
იმ შემთხვევაში, სადაც ჩვენ არ გაივლის root მისამართის მიხედვით,
ჩვენ ვერ ცვლილებები root.
იმ შემთხვევაში, ხე - სადაც root იყო null,
ჩვენ უბრალოდ ჰქონდა დაბრუნების ცრუ. არაფერია ჩვენ შეგვიძლია გავაკეთოთ.
ჩვენ ვერ ჩადეთ კვანძის შევიდა ცარიელი ხე.
მაგრამ ახლა ჩვენ შეგვიძლია, ჩვენ მხოლოდ იმის ცარიელი ხე შევიდა ერთი კვანძის ხე.
რაც ჩვეულებრივ მოსალოდნელი გზა, რომ ის უნდა იმუშაოს.
>> გარდა ამისა, ეს არის მნიშვნელოვნად მოკლეა, ვიდრე
ასევე შენახვა ტრეკზე მშობელი, და ასე რომ თქვენ iterate ქვემოთ ყველა გზა.
ახლა მე მაქვს ჩემი მშობელი, და მე უბრალოდ ჩემი მშობელი უფლება მომცეთ რასაც.
სამაგიეროდ, თუ ეს გავაკეთეთ iteratively, ეს მინდა იყოს იგივე იდეა ხოლო loop.
მაგრამ ნაცვლად, რომელმაც უნდა გაუმკლავდეთ ჩემი მშობელი მაჩვენებელი,
ნაცვლად ჩემი ამჟამინდელი მაჩვენებელი იქნებოდა რამ
რომ მე პირდაპირ შეცვლის აღვნიშნო, რომ ჩემი ახალი კვანძში.
მე არ მაქვს გამკლავება თუ არა ეს მიუთითებს მარცხენა.
მე არ მაქვს გამკლავება თუ არა ეს მიუთითებს უფლება.
უბრალოდ რასაც ამ მაჩვენებელმა არის, მე ვაპირებ ვაყენებთ მას აღვნიშნო, რომ ჩემი ახალი კვანძში.
ყველას გვესმის, როგორ მუშაობს?
თუ არ რატომ გვინდა ამის გაკეთება ამ გზით,
მაგრამ მაინც, რომ ეს სამუშაოები როგორც გამოსავალი?
[სტუდენტური] სად ვბრუნდებით მართალია?
[Bowden], რომ ალბათ სწორედ აქ.
თუ ჩვენ სწორად ჩადეთ დისკი, დაუბრუნოს ჭეშმარიტი.
სხვაგან, ქვემოთ აქ ჩვენ ვაპირებთ მინდა დაბრუნდეს რასაც ჩასმა ბრუნდება.
>> და რაც განსაკუთრებულ ამ რეკურსიული ფუნქცია?
ეს კუდი რეკურსიული, ამიტომ სანამ ჩვენ კომპილაციის ზოგიერთი ოპტიმიზაცია,
იგი აღიარებს, რომ და თქვენ არასოდეს მიიღოთ Stack overflow ამ,
მაშინაც კი, თუ ჩვენი ხე აქვს სიმაღლე 10,000 ან 10 მლნ.
[სტუდენტი გაუგებარია]
[Bowden] მე ვფიქრობ, რომ არ ეს Dash - ან რა ოპტიმიზაცია დონეზე
საჭიროა კუდი უკან უნდა იყოს აღიარებული.
მე ვფიქრობ, რომ აღიარებს - gcc და Clang
ასევე აქვს სხვადასხვა მნიშვნელობა მათი ოპტიმიზაციისათვის დონეზე.
მინდა ვთქვა, რომ ეს DashO 2, დარწმუნებული ვარ, რომ ეს აღიარონ კუდი უკან.
მაგრამ ჩვენ - თქვენ შეიძლება ააშენოს მოსწონს Fibonocci მაგალითად ან რამე.
ეს არ არის ადვილი, რათა გამოსცადოს ამისა, რადგან ძნელია მშენებლობა
ორობითი ხე რომ იმდენად დიდი.
მაგრამ ჰო, მე ვფიქრობ, DashO 2, რომ
თუ კომპილაციის ერთად DashO 2, ამას გადახედეთ კუდი უკან
და ოპტიმიზაცია, რომ.
მოდით დავუბრუნდეთ - ჩადეთ არის სიტყვასიტყვით ბოლო რამ სჭირდება.
მოდით დავუბრუნდეთ ჩანართით მეტი აქ
სადაც ჩვენ ვაპირებთ იგივე იდეას.
ეს ისევ აქვს ხარვეზი არა მიმდინარეობს შეუძლია მთლიანად განიმუხტება
როდესაც root თავისთავად null, ან წარსულში შესვლის null,
მაგრამ ნაცვლად საქმე მშობელს მაჩვენებელი,
მოდით ვრცელდება იგივე ლოგიკას შენახვა მითითებას პოინტერები.
თუ აქ ჩვენ შევინარჩუნოთ კვანძის ** მიმდ.,
და ჩვენ არ უნდა ტრეკზე უფლება აღარ,
მაგრამ კვანძის ** მიმდ. = & ხე.
და ახლა ჩვენი ხოლო loop იქნება, ხოლო * მიმდ. არ თანაბარი null.
არ გჭირდებათ ტრეკზე მშობლები უქმნით.
არ გჭირდებათ ტრეკზე მარცხენა და მარჯვენა.
მე კი ეძახით temp, რადგან ჩვენ უკვე იყენებს temp.
Okay. ასე რომ, თუ (value> * temp),
მაშინ & (* Temp) -> უფლება
სხვაგან temp = & (* Temp) -> დაუტოვებიათ.
და ახლა, ამ ეტაპზე, ამის შემდეგ, ხოლო მარყუჟის,
მე მხოლოდ ამას ვაკეთებთ, რადგან შეიძლება უფრო ადვილია ფიქრი iteratively ვიდრე რეკურსიული,
მაგრამ მას შემდეგ, რაც ამ ხოლო მარყუჟის,
* Temp არის კურსორი ჩვენ გვინდა, რომ შეიცვალოს.
>> სანამ ჩვენ გვქონდა მშობელი, და გვინდოდა, რომ შეცვალოს ან მშობელი ან მარცხენა მშობლის უფლება,
მაგრამ თუ ჩვენ გვინდა, რომ შეიცვალოს მშობლის უფლება,
მაშინ * Temp არის მშობელი უფლება, და ჩვენ შეგვიძლია შევცვალოთ იგი პირდაპირ.
ასე ქვევით აქ, შეგვიძლია გავაკეთოთ * temp = newnode, და ამით ყველაფერი მთავრდება.
ასე შეტყობინება, ყველა ჩვენ ამ იყო აიღოს ხაზების კოდი.
იმისათვის, რომ ტრეკზე მშობელი ყველა რომ არის დამატებითი ძალისხმევა.
აქ, თუ ჩვენ მხოლოდ ტრეკზე მომცეთ მაჩვენებელი,
და მაშინაც კი, თუ გვინდოდა დავაღწიოთ ყველა ამ Curly braces ახლა,
რათა ის გამოიყურება მოკლე.
ეს არის არის ზუსტად იგივე გადაწყვეტა,
მაგრამ ნაკლები ხაზების კოდი.
ერთხელ თქვენ დაიწყოს აღიარების ეს სწორი გამოსავალი,
ასევე ადვილია მიზეზი შესახებ, ვიდრე მოსწონს, okay,
რატომაა ეს დროშა int უფლება?
რას ნიშნავს ეს? ოჰ, ეს signifying რომ
ყოველ ჯერზე მე უფლება, მე უნდა ვაყენებთ მას,
სხვას თუ მე დაუტოვებიათ მე უნდა ვაყენებთ მას ნულოვანი.
აქ, მე არ მაქვს მიზეზი რომ, უბრალოდ ადვილია ფიქრი.
კითხვები?
[სტუდენტი გაუგებარია] >> Yeah.
Okay, ასე ბოლო bit -
ვფიქრობ ერთი სწრაფი და მარტივი ფუნქცია შეგვიძლია გავაკეთოთ არის,
let's - ერთად, ვფიქრობ, შეეცდება და დაწეროთ შეიცავს ფუნქცია
, რომელსაც არ ადარდებს თუ არა ორობითი ძებნა ხე.
ეს შეიცავს ფუნქცია იქნება TRUE
თუ სადმე ამ ზოგადი ორობითი ხე არის ღირებულება ჩვენ ვეძებთ.
მოდით პირველ გავაკეთებთ რეკურსიული და შემდეგ ჩვენ გავაკეთებთ iteratively.
ჩვენ შეგვიძლია რეალურად მხოლოდ გავაკეთებთ ერთად, რადგან ეს იქნება მართლაც მოკლე.
>> რა არის ჩემი ბაზა შემთხვევაში იქნება?
[სტუდენტი გაუგებარია]
[Bowden] ასე რომ, თუ (ხე == NULL), მერე რა?
[სტუდენტური] დაბრუნება ყალბი.
[Bowden] სხვაგან, ისე, მე არ გვჭირდება სხვა.
თუ იყო ჩემი სხვა ბაზის შემთხვევაში.
[სტუდენტური] ხე მისი მნიშვნელობა? >> Yeah.
ასე რომ, თუ (ხე-> ღირებულების == ღირებულება.
გაითვალისწინეთ ჩვენ თავში კვანძის *, არ კვანძის ** s?
შეიცავს არასდროს უნდა გამოვიყენოთ კვანძის **,
მას შემდეგ, რაც ჩვენ არ შეცვლის პოინტერები.
ჩვენ უბრალოდ traversing მათ.
თუ ეს მოხდება, მაშინ ჩვენ გვინდა დაბრუნდეს ჭეშმარიტი.
Else გვინდა traverse შვილი.
ამიტომ, ჩვენ ვერ მიზეზი თუ არა ყველაფერი, რათა მარცხენა ნაკლებია
და ყველაფერი მარჯვნივ არის უფრო დიდი.
რა არის ჩვენი მდგომარეობა იქნება აქ - ან, რას აპირებს?
[სტუდენტი გაუგებარია] >> Yeah.
დაბრუნება შეიცავს (ღირებულება, ხის-> მარცხნივ)
ან შეიცავს (ღირებულება, ხის-> მარჯვნივ). და ამით ყველაფერი.
და შენიშნავს, არსებობს გარკვეული მოკლე ჩართვა შეფასება,
აქ თუ ჩვენ მოხდეს მოძიების ღირებულების მარცხენა ხე,
ჩვენ არასოდეს უნდა შევხედოთ უფლება ხე.
სწორედ მთელი ფუნქცია.
ახლა მოდით ეს iteratively,
რაც იქნება ნაკლებად ლამაზი.
ჩვენ მიიღოს ჩვეულებრივი დაწყების კვანძის * მიმდ. = ხე.
მიუხედავად იმისა (მიმდ. = NULL).
სწრაფად აპირებს ვხედავ პრობლემას.
თუ მიმდ. - აქ, თუ ჩვენ ოდესმე შესვენება აქედან,
მაშინ ჩვენ ამოიწურა რამ შევხედოთ, ამიტომ დაბრუნების ცრუ.
თუ (მიმდ.-> ღირებულების == ღირებულების), დაუბრუნოს ჭეშმარიტი.
ახლა, ჩვენ ვიმყოფებით ადგილი -
ჩვენ არ ვიცით თუ არა ჩვენ გვინდა წავიდეთ მარცხნივ ან მარჯვნივ.
ასე თვითნებურად, მოდით უბრალოდ დაუტოვებიათ.
მე აშკარად გადაეყარონ საკითხი, სადაც მე სრულიად მიტოვებული ყველაფერი -
მე მხოლოდ ოდესმე შეამოწმოთ მარცხენა მხარეს ხე.
მე არასდროს შეამოწმოს ყველაფერი, რაც არის სწორი ბავშვი არაფერი.
როგორ შემიძლია დაფიქსირება ამ?
[სტუდენტური] თქვენ უნდა ტრეკზე მარცხენა და მარჯვენა Stack.
[Bowden] Yeah. მოდით იყოს იგი
struct სია, node * n, და შემდეგ კვანძის ** შემდეგი?
მე ვფიქრობ, რომ მუშაობს ჯარიმა.
ჩვენ გვინდა წავიდეთ მეტი მარცხენა, ან let's - აქ.
Struct სია სია =, ეს დავიწყებთ
out ამ struct სიაში.
* სიაში = null. ასე რომ იქნება ჩვენი დაკავშირებული სია
საქართველოს subtrees რომ ჩვენ გამოტოვებენ დასრულდა.
ჩვენ ვაპირებთ, რომ ტრავერსზე დაუტოვებიათ ახლა,
მაგრამ რადგან ჩვენ აუცილებლად უნდა დაუბრუნდეს უფლება,
ჩვენ ვაპირებთ შენარჩუნება მარჯვენა მხარეს შიგნით ჩვენი struct სიაში.
მაშინ გვექნება new_list ან struct,
struct სია *, new_list = malloc (sizeof (სია)).
მე ვაპირებ იგნორირება შეცდომის შემოწმების რომ, მაგრამ თქვენ უნდა შეამოწმეთ, რომ მისი null.
New_list კვანძის ის აპირებს აღვნიშნო, რომ -
OH, ამიტომ მინდოდა ეს აქ. იგი აპირებს აღვნიშნო, რომ მეორე struct სიაში.
ეს მხოლოდ როგორ უკავშირდება სიები მუშაობა.
ეს არის იგივე როგორც int უკავშირდება სია
გარდა ჩვენ უბრალოდ შეცვალა int ერთად კვანძის *.
ეს ზუსტად იგივე.
ამიტომ new_list, ღირებულების ჩვენი new_list კვანძში,
იქნება მიმდ.-> უფლება.
ღირებულება ჩვენი new_list-> შემდეგი იქნება ჩვენი ორიგინალური სიაში,
და მაშინ ჩვენ ვაპირებთ განაახლოს ჩვენი სიიდან აღვნიშნო, რომ new_list.
>> ახლა ჩვენ გვჭირდება გარკვეული გზა უბიძგებენ რამ,
როგორც ჩვენ არ გადიოდა მთელი მარცხენა subtree.
ახლა ჩვენ უნდა გაიყვანოს პერსონალის გარეთ,
მოსწონს მიმდ. არის null, ჩვენ არ გვინდა უბრალოდ დააბრუნოს ყალბი.
ჩვენ გვინდა ახლა გაიყვანოს გარეთ ჩვენი ახალი სია.
მოსახერხებელი გზა კეთების ამ - ისევე, ფაქტობრივად, არსებობს მრავალი გზები აკეთებენ.
ვინმეს აქვს შემოთავაზება?
სადაც მე უნდა გავაკეთოთ ამა თუ როგორ უნდა გავაკეთოთ ეს?
ჩვენ მხოლოდ რამდენიმე წუთის შემდეგ, მაგრამ რაიმე შემოთავაზება?
იმის ნაცვლად, რომ ერთ - ერთი გზა, ნაცვლად ჩვენს პირობებში მყოფი ხოლო,
რა ჩვენ გაკეთებული ეძებს არ არის null,
ნაცვლად ჩვენ გავაგრძელებთ წასვლა სანამ ჩვენს სიაში თავისთავად null.
ასე რომ, თუ ჩვენს სიაში მთავრდება მყოფი null,
მაშინ ჩვენ არ ამოიწურა რამ მოსაძებნად, ძებნის დასრულდა.
მაგრამ ეს იმას ნიშნავს, რომ პირველი, რაც ჩვენს სიაში მხოლოდ იქნება პირველი კვანძი.
ძალიან პირველი რაც იქნება - ჩვენ აღარ უნდა დაინახოს, რომ.
ასე რომ ლენტა-> n იქნება ჩვენი ხე.
სიის-> შემდეგი იქნება null.
და ახლა, ხოლო სიაში არ თანაბარი null.
მიმდ. აპირებს დახევის რაღაც ჩვენი სიიდან.
ამიტომ მიმდ. აპირებს თანაბარი სიაში-> n.
და მაშინ სიაში აპირებს თანაბარი სიაში-> N, ან სიაში-> მომავალი.
ასე რომ, თუ მიმდ. ღირებულება შეადგენს ღირებულების.
ახლა ჩვენ შეგიძლიათ დაამატოთ როგორც ჩვენი უფლება მაჩვენებელი და ჩვენი მარცხენა კურსორი
რადგან ისინი არ null.
Down აქ, ვფიქრობ, უნდა გაკეთდეს, რომ პირველ რიგში.
თუ (მიმდ.-> უფლება! = NULL)
მაშინ ჩვენ ვაპირებთ ჩადეთ რომ კვანძის ჩვენს სიაში.
თუ (მიმდ.-> მარცხნივ), ეს ცოტა ზედმეტი მუშაობა, მაგრამ ჯარიმა.
თუ (მიმდ.-> მარცხენა = NULL),
და ჩვენ ვაპირებთ ჩადეთ მარცხენა ჩვენს უკავშირდება სია,
და რომ უნდა იყოს იგი.
ჩვენ iterate - სანამ ჩვენ გვაქვს რაღაც ჩვენი სიიდან,
ჩვენ გვაქვს კიდევ ერთი კვანძის შევხედოთ.
ასე შევხედავთ, რომ კვანძის,
ჩვენ წინასწარ ჩვენს სიაში მომდევნო ერთი.
თუ რომ კვანძის არის ღირებულება ჩვენ ვეძებთ, ჩვენ შეგვიძლია იქნება TRUE.
Else ჩადეთ ორივე ჩვენი მარჯვენა და მარცხენა subtrees,
რადგან ისინი არ null, ჩვენს სიაში
ასე, რომ ჩვენ აუცილებლად წავიდეთ მათზე.
ასე რომ, თუ ისინი არ null,
თუ ჩვენი ძირეული მაჩვენებელი მიუთითებს ორი რამ,
მაშინ პირველ რიგში ჩვენ გამოყვანილია რაიმე ისე ჩვენს სიაში მთავრდება მყოფი null.
და შემდეგ ჩვენ დააყენა ორი რამ უკან, ასე რომ ახლა ჩვენს სიაში არის ზომა 2.
მაშინ ჩვენ ვაპირებთ მარყუჟი back up და ჩვენ უბრალოდ აპირებს გაიყვანოს,
ვთქვათ, მარცხენა კურსორი ჩვენი ძირეული კვანძის.
და რომ ყველაფერს მხოლოდ შენარჩუნება ხდება, ჩვენ დასრულდება მდე looping ზე ყველაფერი.
>> გაითვალისწინეთ, რომ ეს იყო მნიშვნელოვნად უფრო რთული
წელს რეკურსიული გადაწყვეტა.
და მე განაცხადა რამდენჯერმე
რომ რეკურსიული გადაწყვეტა ჩვეულებრივ გაცილებით საერთო iterative გადაწყვეტა.
აქ სწორედ რეკურსიული გადაწყვეტა აკეთებს.
მხოლოდ ცვლილება არის, რომ ნაცვლად მინიშნებით გამოყენებით დასტის, პროგრამის დასტის,
როგორც თქვენი გზა შენახვის ტრეკზე რა კვანძების თქვენ კვლავ უნდა ეწვევა,
ახლა თქვენ უნდა პირდაპირ გამოყენება დაკავშირებული სიაში.
ორივე შემთხვევაში თქვენ შენახვა ტრეკზე რა კვანძის მაინც საჭიროებს ეწვია.
In რეკურსიული შემთხვევაში უბრალოდ ადვილია რადგან დასტის
ხორციელდება, როგორც პროგრამის დასტის.
გაითვალისწინეთ, რომ ეს დაკავშირებულია სიაში, ეს არის დასტის.
რაც ჩვენ უბრალოდ ჩაიცვი დასტის
მაშინვე, რაც ჩვენ ვაპირებთ დახევის off დასტის ეწვევა შემდეგი.
ჩვენ გარეთ, მაგრამ რაიმე კითხვა?
[სტუდენტი გაუგებარია]
[Bowden] Yeah. ასე რომ, თუ ჩვენ გვაქვს დაკავშირებული სიაში,
მიმდინარე აპირებს აღვნიშნო, რომ ამ ბიჭს,
და ახლა ჩვენ უბრალოდ მიიწევს ჩვენი დაკავშირებული სიაში ფოკუსირება ამ ბიჭს.
ჩვენ traversing მეტი უკავშირდება სიაში რომ ხაზი.
და მაშინ ვხვდები, ჩვენ უნდა გავათავისუფლოთ ჩვენი დაკავშირებული სიაში და პერსონალი
ერთხელ სანამ ჭეშმარიტი ან ცრუ, ჩვენ უნდა
iterate მეტი ჩვენი უკავშირდება სიაში და ყოველთვის ქვევით აქ, ვფიქრობ,
თუ ჩვენ მიმდ. უფლება არ არის ტოლი, დაამატოთ, ასე რომ, ახლა ჩვენ გვინდა გასათავისუფლებლად
მიმდ. რადგან, ისევე, არც ჩვენ სრულიად დაივიწყოს სიაში? Yeah.
ასე რომ, რაც ჩვენ გვსურს რომ აქ.
სად არის მაჩვენებელი?
მიმდ. იყო მაშინ - ჩვენ გვინდა struct სია * 10 ტოლია სიის მომდევნო.
უფასო სია, სიაში = temp.
და იმ შემთხვევაში, ჩვენ იქნება TRUE, ჩვენ გვჭირდება iterate
მეტი ნაშთი ჩვენი დაკავშირებული სიაში გამონთავისუფლების რამ.
ლამაზი რამ შესახებ რეკურსიული გამოსავალი გამონთავისუფლების რამ
მხოლოდ იმას ნიშნავს, popping factorings off დასტის რომელიც მოხდება თქვენთვის.
ამიტომ ჩვენ წავიდა რაღაც ასეთი 3 ხაზების ძნელად ვფიქრობ-ს შესახებ კოდი
რაიმე რომ მნიშვნელოვნად მრავალი სხვა ძნელად ვფიქრობ-ს შესახებ ხაზი კოდი.
ნებისმიერი უფრო მეტი შეკითხვა?
ყველა უფლება. ჩვენ კარგი. Bye!
[CS50.TV]