[Powered by Google Translate] [ნაწილი 7] [Less კომფორტული] [Nate Hardison] [ჰარვარდის უნივერსიტეტის] [ეს არის CS50.] [CS50.TV] 

კეთილი იყოს ნაწილი 7. მადლობა ქარიშხალი Sandy, ნაცვლად, რომელმაც ჩვეულებრივი მონაკვეთზე ამ კვირაში, ვაკეთებთ ამ მსვლელობა მეშვეობით, გავლით მონაკვეთზე კითხვები. მე ვაპირებ იყოს შემდეგ ერთად პრობლემა უცნობია 6 სპეციფიკაცია, და გადის ყველა კითხვას სექცია კითხვები მონაკვეთზე. თუ არის რამე კითხვა, გთხოვთ დაპოსტოთ ამ თემაზე CS50 განიხილავს. 

კარგად. მოდით დავიწყოთ. მარჯვენა ახლა მე ეძებს გვერდი 3 პრობლემა Set სპეციფიკაცია. ჩვენ ვაპირებთ დავიწყოთ ლაპარაკი ბინარული ხეები რადგან იმ ბევრი შესაბამისობა ამ კვირაში პრობლემა კომპლექტი - Huffman ხე კოდირების. ერთი პირველი მონაცემები სტრუქტურები ჩვენ ვისაუბრეთ on CS50 იყო მასივი. გახსოვდეთ, რომ მასივი არის თანმიმდევრობა ელემენტები - ყველა მსგავსი ტიპის - შენახული უფლება მომდევნო ერთმანეთს მეხსიერებაში. თუ მაქვს მთელი მასივი, რომ მე შემიძლია შევაჩერო გამოყენებისას ყუთები-ნომრები-რიცხვებით სტილი - ვთქვათ მაქვს 5 წლის პირველ ყუთი, მაქვს 7 მეორე, მაშინ მე 8, 10, 20 და საბოლოო ყუთში. გახსოვდეთ, ორი მართლაც კარგი ამ მასივი ვართ, რომ გვაქვს ამ მუდმივ დროში ხელმისაწვდომობის კონკრეტული ელემენტს  მასივში, თუ ჩვენ ვიცით მისი ინდექსი. მაგალითად, თუ მინდა დაიბრუნოს მესამე ელემენტია მასივი - ზე ინდექსი 2 გამოყენებით ჩვენი ნულოვანი დაფუძნებული ინდექსირებას სისტემა - მე სიტყვასიტყვით უბრალოდ უნდა გავაკეთოთ მარტივი მათემატიკური გაანგარიშება, hop ამ თანამდებობაზე მასივში, გაიყვანოს 8 რომ ინახება იქ, და მე კარგი წასვლა. 

ერთი ცუდი რამ ამ მასივი - რომ ჩვენ ვისაუბრეთ როდესაც ჩვენ განვიხილეთ უკავშირდება სიები - ის არის, რომ თუ მინდა ჩადეთ ელემენტს ამ მასივი, მე ვაპირებ უნდა გავაკეთოთ ზოგიერთი თავიანთ გარშემო. მაგალითად, ამ მასივი უფლება აქ არის დახარისხებული მიზნით - დახარისხების აღმავალი შეკვეთა - 5, მაშინ 7, მაშინ 8, შემდეგ 10 და შემდეგ 20 - მაგრამ თუ მინდა ჩადეთ ნომერი 9 ამ მასივი, მე ვაპირებ უნდა გადაეტანა ზოგიერთი ელემენტები, რათა სივრცეში. ჩვენ შეგვიძლია დავხატოთ ამ აქ. მე ვაპირებ უნდა გადავიდეთ 5, 7, და შემდეგ 8; შექმნა უფსკრული სად შემიძლია დააყენა 9, და შემდეგ 10 და 20 შეიძლება წავიდეს უფლება 9. ეს არის სახის ტკივილი, რადგან უარესი სცენარით - როდესაც ჩვენ მქონე ჩასვათ ან დასაწყისში ან ბოლოში საქართველოს მასივი, დამოკიდებულია, როგორ ჩვენ გადავიდა - ჩვენ შეიძლება დასრულდება მდე მქონე გადაეტანა ყველა ელემენტები რომ ჩვენ გაკეთებული შენახვის მასივში. 

ასე რომ, რა იყო პირიქით ამ? პირიქით ეს იყო წასვლა ჩვენი დაკავშირებული სიაში მეთოდით რომელშიც - ნაცვლად შენახვის ელემენტები 5, 7, 8, 10, 20 და ყველა მომდევნო ერთმანეთს მეხსიერება - რაც ჩვენ ნაცვლად გააკეთა, შესანახად მათ სახის სადაც არ გვინდოდა შესანახად მათ ამ დაკავშირებული სიაში კვანძების რომელიც მე ხატვის აქ, სახის დროებითი. და შემდეგ ჩვენ უკავშირდება მათი ერთად გამოყენებით ამ შემდეგი პოინტერები. შემიძლია აქვს მაჩვენებელი 5 დან 7, კურსორი საწყისი 7 დან 8, კურსორი საწყისი 8 დან 10, და ბოლოს, კურსორი საწყისი 10 დან 20, და შემდეგ null კურსორი at 20 მიუთითებს, რომ იქ არაფერი დარჩა. ვაჭრობის საგანი, რომ გვაქვს აქ ის არის, რომ ახლა თუ გვინდა ჩადეთ ნომერი 9 ჩვენს დახარისხებული სია, ყველა ჩვენ უნდა გავაკეთოთ არის შექმნას ახალი კვანძის, 9, WIRE ის აღვნიშნო, რომ შესაბამის ადგილზე, და შემდეგ ხელახლა მავთულის 8 აღვნიშნო ქვემოთ 9. რომ საკმაოდ სწრაფად, თუ ვთქვათ ვიცით ზუსტად სად გვინდა ჩადეთ 9. მაგრამ ვაჭრობის სანაცვლოდ არის ის, რომ ჩვენ ახლა დაკარგა მუდმივი დროში ხელმისაწვდომობის რაიმე ელემენტს ჩვენს მონაცემთა სტრუქტურას. მაგალითად, თუ მინდა, რომ იპოვოთ მეოთხე ელემენტს ამ დაკავშირებული სიაში, მე ვაპირებ უნდა იწყება დასაწყისშივე სია და მუშაობა ჩემი გზას დათვლის node-by-node სანამ მე მეოთხე. 

იმისათვის, რომ უკეთ ხელმისაწვდომობის შესრულება ვიდრე უკავშირდება სია - არამედ შეინარჩუნოს ზოგიერთი სარგებელი, რომ ჩვენ გვქონდა თვალსაზრისით Insertion დროში საწყისი უკავშირდება სია - ორობითი ხე აპირებს უნდა გამოვიყენოთ ცოტა მეტი მეხსიერება. კერძოდ, ნაცვლად მხოლოდ ერთი მქონე მაჩვენებელი წელს ორობითი ხე კვანძში - მოსწონს დაკავშირებული სიაში კვანძის აკეთებს - ჩვენ ვაპირებთ დაამატოთ მეორე მომცეთ ორობითი ხე კვანძში. და არა მხოლოდ ერთი მქონე მომცეთ შემდეგი ელემენტს, ჩვენ ვაპირებთ აქვს მომცეთ მარცხენა ბავშვი და მარჯვნივ შვილი. 

მოდით დავხატოთ სურათი, ნახოთ კიდევ რა, რომ რეალურად გამოიყურება. ისევ და ისევ, მე ვაპირებ გამოიყენოთ ეს ყუთები და ისრებით. ორობითი ხე კვანძის დაიწყება off ერთად უბრალოდ მარტივი ყუთში. ის აპირებს ფართი ღირებულება, და მაშინ ის ასევე აპირებს ფართი მარცხენა ბავშვი და მარჯვნივ შვილი. მე ვაპირებ წარწერა ისინი აქ. ჩვენ ვაპირებთ აქვს მარცხენა ბავშვი, და შემდეგ ჩვენ ვაპირებთ აქვს უფლება ბავშვს. არსებობს ბევრი სხვადასხვა გზა ამით. ზოგჯერ, სივრცე და კომფორტი, მე რეალურად გავამახვილო ეს მოსწონს მე ვაკეთებ აქ ბოლოში სადაც მე ვაპირებ აქვს ღირებულების ზედა, და შემდეგ უფლება ბავშვის ქვედა-უფლებას, და მარცხენა ბავშვის ქვედა მარცხენა. უკან ამ ყველაზე დიაგრამაზე, ჩვენ გვაქვს ღირებულება ძალიან ზევით, მაშინ მარცხენა ბავშვის მაჩვენებელი, ხოლო შემდეგ ჩვენ გვაქვს უფლება და შვილის მაჩვენებელი. 

პრობლემის Set სპეციფიკაცია, ვსაუბრობთ ხატვის კვანძში, რომელსაც აქვს ღირებულება 7, და შემდეგ მარცხენა ბავშვის მაჩვენებელი, არის null, და მარჯვენა ბავშვის მაჩვენებელი, არის null. ჩვენ შეგიძლიათ ან წერენ კაპიტალის NULL წელს ფართი ორივე მარცხენა და ბავშვის უფლება ბავშვის, ან ჩვენ შეგვიძლია დავხატოთ ამ დახრილი ხაზი მეშვეობით თითოეულ ყუთები მიუთითოს, რომ ეს null. მე ვაპირებ ამას მხოლოდ იმიტომ, რომ მარტივი. რა ხედავთ აქ ორი გზა diagramming ძალიან მარტივი ორობითი ხე კვანძში სადაც ჩვენ გვყავს ღირებულება 7 და null ბავშვის პოინტერები. 

მეორე ნაწილი ჩვენი სპეციფიკაცია საუბრობს როგორ დავუკავშირდეთ უკავშირდება სიები - გახსოვდეთ, ჩვენ მხოლოდ ჰქონდა გამართავს შესახებ, რომ ძალიან პირველად ელემენტს სია უნდა გვახსოვდეს სრული სია - ანალოგიურად, ერთად ორობითი ხე, ჩვენ მხოლოდ უნდა გაიმართება ერთ მომცეთ ხე იმისათვის, რომ შევინარჩუნოთ კონტროლს მთელი მონაცემები სტრუქტურა. ეს სპეციალური ელემენტს ხე ეწოდება root node ხე. მაგალითად, თუ ამ ერთი კვანძის - ამ კვანძის შემცველი ღირებულება 7 ერთად null მარცხენა და მარჯვენა ბავშვის პოინტერები - იყო მხოლოდ ღირებულების ჩვენი ხე, მაშინ ეს იქნება ჩვენი ძირეული კვანძის. ეს თავიდანვე ჩვენი ხე. ჩვენ ვხედავთ ამ პატარა უფრო ნათლად ერთხელ ჩვენ ვიწყებთ დასძინა მეტი კვანძების ჩვენი ხე. ნება მომეცით დახევის up ახალი გვერდი. 

ახლა ჩვენ ვაპირებთ მიაპყროს ხე, რომელსაც აქვს 7 ზე root, და 3 შიგნით მარცხენა ბავშვი და 9 შიგნით უფლება შვილი. ისევ და ისევ, ეს საკმაოდ მარტივია. გვაქვს 7, მიაპყროს კვანძის ამისთვის 3, კვანძში, 9, და მე ვაპირებ მითითებული მარცხენა ბავშვის მაჩვენებელი 7 დან აღვნიშნო, რომ კვანძის შემცველი 3, და მარჯვენა ბავშვის მაჩვენებელი of კვანძის შემცველი 7 დან კვანძის შემცველი 9. ახლა, მას შემდეგ, რაც 3 და 9 არ აქვთ ბავშვებს, ჩვენ სხვებისათვის ყველა მათი შვილი მითითებას იყოს null. აქ, root ჩვენი ხე შეესაბამება კვანძის შემცველი ნომერი 7. თქვენ ხედავთ, რომ, თუ ყველა ჩვენ გვაქვს არის მომცეთ, რომ ძირეული კვანძის, ჩვენ შეგვიძლია მაშინ გავლა ჩვენი ხე და დაშვების ორივე შვილი კვანძების - ორივე 3 და 9. არ უნდა შეინარჩუნოს მითითებას თითოეული კვანძის on ხე. კარგად. ახლა ჩვენ ვაპირებთ დაამატოთ კიდევ ერთი კვანძის ამ დიაგრამაზე. ჩვენ ვაპირებთ დაამატოთ კვანძის შემცველი 6, და ჩვენ ვაპირებთ დაამატოთ ეს როგორც უფლება ბავშვი კვანძის შემცველი 3. ამისათვის, მე ვაპირებ, რომ წაშალოს null მაჩვენებელი წელს 3-node და მავთული ის აღვნიშნო, რომ კვანძის შემცველი 6. კარგად. 

ამ ეტაპზე, მოდით წავიდეთ მეტი ცოტა ტერმინოლოგიას. უნდა დაიწყოს, იმ მიზეზით, რომ ამ ეწოდება ორობითი ხე კერძოდ არის ის, რომ მას აქვს ორი შვილი მითითებას. არსებობს სხვა სახის ხეები, რომ უფრო მეტი ბავშვი პოინტერები. კერძოდ, რა გააკეთეთ "შეეცდება" პრობლემების Set 5. თქვენ შეამჩნევთ, რომ რომ ცდილობენ, გქონდათ 27 სხვადასხვა მითითებას სხვადასხვა ბავშვებს - ერთი თითოეული 26 ასო ინგლისურ ანბანში, და შემდეგ 27 ამისთვის აპოსტროფი - ასე, რომ მსგავსი ტიპის ხე. მაგრამ აქ, რადგან ეს ორობითი, ჩვენ მხოლოდ ორი ბავშვი პოინტერები. 

გარდა ამისა root node რომ ჩვენ ვისაუბრეთ, ჩვენ ასევე სროლა გარშემო ეს ტერმინი "ბავშვი. ' რას ნიშნავს ერთი კვანძის იყოს ბავშვის სხვა კვანძის? ეს სიტყვასიტყვით ნიშნავს, რომ ბავშვის კვანძში არის ბავშვის სხვა კვანძის თუ ეს სხვა კვანძის ერთი მისი შვილი პოინტერები მითითებული აღვნიშნო, რომ კვანძის. დააყენოს ამ შევიდა უფრო კონკრეტული ვადები, თუ 3 აღნიშნულია, რომ ერთი ბავშვის პოინტერები 7, მაშინ 3 არის ბავშვი 7. თუ ჩვენ უნდა გაერკვნენ, რა შვილები არიან 7 - ასევე, ჩვენ ვხედავთ, რომ 7 აქვს მომცეთ 3 და მომცეთ 9, ასე 9 და 3 არიან შვილები 7. ცხრა ვიზიტორების ბავშვებს, რადგან მისი შვილი მითითებები null, და 3 აქვს მხოლოდ ერთი შვილი, 6. ექვსი ასევე ვიზიტორების ბავშვებს, რადგან ორივე მისი მითითებები null, რომელიც ჩვენ მიაპყროს ახლავე. 

გარდა ამისა, ჩვენ საუბრობენ მშობლები კერძოდ კვანძში, და ეს არის, როგორც თქვენ მინდა ველით, საპირისპირო ამ ბავშვს აღწერა. თითოეული კვანძის აქვს მხოლოდ ერთი მშობლის - ნაცვლად ორი, როგორც თქვენ შეიძლება ველოდოთ ერთად ადამიანები. მაგალითად, მშობელი 3 არის 7. მშობელი 9 ასევე 7 და მშობელი 6 არის 3. ბევრი მას. ჩვენ ასევე გვაქვს თვალსაზრისით ლაპარაკი grandparents და შვილიშვილები, და ზოგადად ვსაუბრობთ წინაპართა და შთამომავლები კერძოდ კვანძში. წინაპარი კვანძის - ან წინაპრების, არამედ საქართველოს კვანძში - არის ყველა კვანძების, რომ ცრუობენ გზაზე საწყისი root to რომ კვანძის. მაგალითად, თუ მე ვერ კვანძის 6, შემდეგ წინაპრების ვაპირებთ იყოს როგორც 3 და 7. წინაპრები 9, მაგალითად, - თუ მე ეძებს კვანძის 9 - მაშინ წინაპარი 9 არის მხოლოდ 7. და შთამომავლები არიან ზუსტად საპირისპირო. თუკი მინდა შევხედოთ ყველა შთამომავლები 7, მაშინ უნდა შევხედოთ ყველა კვანძების ქვეშ იგი. ასე რომ, მე მაქვს 3, 9, და 6 როგორც შთამომავლები 7. 

საბოლოო ვადა, რომ ჩვენ ვსაუბრობთ არის ამ ცნება მყოფი ძმა. ძმა - სახის შემდეგ გასწვრივ ამ ოჯახის თვალსაზრისით - არიან კვანძების, რომლებიც ამავე დონის ხე. ასე რომ, 3 და 9 არიან ძმა რადგან ისინი ამავე დონის ხე. ორივე ერთი და იგივე მშობელი, 7. 6 ვიზიტორების ძმა რადგან 9 არ აქვს არც შვილი. და 7 არ აქვს ძმა რადგან root ჩვენი ხე, და არსებობს მხოლოდ ოდესმე 1 root. 7 ჰქონდეს ძმა იქ უნდა იყოს კვანძის ზემოთ 7. იქ უნდა იყოს მშობელი 7, რომლის დროსაც 7 აღარ იყოს ფესვი ხე. მაშინ ეს ახალი მშობელი 7 ასევე უნდა ჰქონდეს ბავშვს, და რომ ბავშვი ამის შემდეგ იქნება ძმა, 7. 

კარგად. მოძრავი. როდესაც ჩვენ დავიწყეთ ჩვენი განხილვა ორობითი ხეები, ჩვენ ვისაუბრეთ იმაზე, თუ როგორ ვაპირებდით გამოიყენოს მათ მოიპოვოს უპირატესობა ორივე კოლექტორები და დაკავშირებული სიები. და გზა ჩვენ ვაპირებთ, რომ არის ამ შეკვეთით ქონება. ჩვენ ვამბობთ, რომ ორობითი ხის უბრძანა, შესაბამისად სპეციფიკაცია, თუ თითოეული კვანძის ჩვენს ხე, ყველა მის შთამომავლობის მარცხენა - მარცხენა ბავშვი და ყველა მარცხენა ბავშვის შთამომავლები - აქვს ნაკლებად ღირებულებები, და ყველა კვანძების მარჯვენა - უფლება ბავშვი და ყველა უფლება ბავშვის შთამომავლები - აქვს კვანძების მეტი ღირებულების მიმდინარე კვანძის რომ ჩვენ შევხედავთ. Just სიმარტივის, ჩვენ ვაპირებთ ვივარაუდოთ, რომ არ არსებობს დუბლიკატი კვანძების ჩვენი ხე. მაგალითად, ამ ხის ჩვენ არ ვაპირებთ გამკლავება შემთხვევაში სადაც ჩვენ გვყავს ღირებულება 7 ზე root  და მაშინ ჩვენ ასევე გვაქვს ღირებულება 7 სხვაგან ხე. ამ შემთხვევაში, თქვენ შეამჩნევთ, რომ ეს ხე მართლაც უბრძანა. ჩვენ გვყავს ღირებულება 7 ზე root. ყველაფერი მარცხნივ 7 - თუ გაუქმება ყველა ამ პატარა ნიშნების აქ - ყველაფერი მარცხნივ 7 - 3 და 6 - იმ ღირებულებების ორივე არანაკლებ 7 და ყველაფერი მარჯვნივ - რომელიც მხოლოდ ამ 9 - მეტია 7. 

ეს არ არის მხოლოდ დაავალა ხე შემცველი ამ ღირებულებების, მაგრამ მოდით დავხატოთ რამდენიმე მათგანი. არსებობს ფაქტიურად მთელი bunch of გზები, რომ ჩვენ შეგვიძლია ამის გაკეთება. მე ვაპირებ გამოვიყენო სტენოგრამის მხოლოდ შენარჩუნება რამ მარტივი აქ - ვიდრე ხატვის მთლიანი ყუთები და ისრებით - მე უბრალოდ აპირებს გავამახვილო ნომრები და დაამატოთ ისრებით დამაკავშირებელი მათ. დასაწყებად, ჩვენ უბრალოდ დავწეროთ ჩვენი ორიგინალური ხე, სადაც ჩვენ გვქონდა 7, შემდეგ 3, და შემდეგ 3 აღნიშნა თავში უფლება 6, და 7 ჰქონდა უფლება ბავშვი რომ იყო 9. კარგად. რა არის სხვა გზა, რომ ჩვენ შეეძლო დაეწერა ეს ხე? იმის მაგივრად რომ 3 იყოს მარცხენა ბავშვი 7, ჩვენ შეგვიძლია აგრეთვე აქვს 6 იქნება მარცხენა ბავშვი 7, და მაშინ 3 იქნება მარცხენა ბავშვი 6. რომ გამოიყურება ასე, ხე სწორედ აქ, სადაც მე მოხვდით 7, მაშინ 6, მაშინ 3 და 9 მარჯვენა. ჩვენ ასევე არ აქვს 7 როგორც ჩვენი ძირეული კვანძის. ჩვენ შეგვიძლია აგრეთვე აქვს 6 როგორც ჩვენი ძირეული კვანძის. რა, რომ გამოიყურებოდეს? თუ ჩვენ ვაპირებთ, რომ შევინარჩუნოთ ეს უბრძანა ქონება, ყველაფერი მარცხნივ 6 უნდა იყოს ნაკლები. არსებობს მხოლოდ ერთი საშუალება, და რომ 3. მაგრამ შემდეგ, როგორც უფლება ბავშვი 6, ჩვენ გვაქვს ორი გზა. პირველი, ჩვენ შეგვეძლო 7 და შემდეგ 9, ან ჩვენ შეგვიძლია დავხატოთ მას - როგორც მე უნდა გავაკეთოთ აქ - სადაც ჩვენ გვყავს 9 როგორც უფლება ბავშვი 6, და შემდეგ 7 როგორც მარცხენა ბავშვი 9. 

ახლა, 7 და 6 არ არის ერთადერთი შესაძლო ღირებულებების root. ჩვენ შეგვიძლია აგრეთვე აქვს 3 იყოს root. რა მოხდება თუ 3 არის root? აქ რამ კიდევ ცოტა საინტერესო. სამი არა აქვს ღირებულებები, რომლებიც ნაკლები, ისე, რომ მთელი მარცხენა მხარე ხის უბრალოდ იქნება null. აქ არ იქნება არაფერი არსებობს. მარჯვნივ, ჩვენ შეგვიძლია ჩამოვთვალოთ რამ აღმავალი შეკვეთა. ჩვენ შეგვეძლო 3, მაშინ 6, მაშინ 7, მაშინ 9. ან, შეიძლება გავაკეთოთ 3, მაშინ 6, შემდეგ 9, შემდეგ 7. ან, შეიძლება გავაკეთოთ 3, მაშინ 7, მაშინ 6, შემდეგ 9. ან, 3, 7 - რეალურად არა, ჩვენ ვერ 7 უქმნით. სწორედ ჩვენი ერთი რამ არსებობს. ჩვენ შეგვიძლია გავაკეთოთ 9, და შემდეგ 9 შეგვიძლია 6 და შემდეგ 7. ან, შეგვიძლია გავაკეთოთ 3, შემდეგ 9, შემდეგ 7 და შემდეგ 6. 

ერთი რამ გავამახვილო თქვენი ყურადღება აქ არის რომ ეს ხეები ხართ პატარა უცნაური ორიენტირებული. კერძოდ, თუ დავაკვირდებით 4 ხეები მარჯვენა მხარეს - მე შემოხაზეს მათ, აქ - ამ ხეები გამოიყურებოდეს თითქმის ზუსტად ისევე უკავშირდება სიაში. თითოეული კვანძის აქვს მხოლოდ ერთი შვილი, და ამიტომ ჩვენ არ გვაქვს ამ ხის მსგავსი სტრუქტურა, რომელიც ჩვენ ვხედავთ, მაგალითად,  ამ ერთი მარტოხელა ხე მეტი აქ ქვედა მარცხენა. ეს ხეები ფაქტობრივად მოუწოდა degenerate ბინარული ხეები, და ჩვენ ვსაუბრობთ ამ უფრო მომავალში - განსაკუთრებით თუ კი მიიღოს სხვა კომპიუტერულ მეცნიერებათა კურსებს. ეს ჯიშებია degenerate. ისინი არ ძალიან სასარგებლო, რადგან, მართლაც, ამ სტრუქტურის lends თავად  საძიებელი ჯერ მსგავსი უკავშირდება სიაში. ჩვენ არ მიიღოთ ისარგებლოს დამატებითი მეხსიერება - ეს ზედმეტი მიმთითებელი - რადგან ჩვენი სტრუქტურა მყოფი ცუდი ამ გზით. იმის ნაცვლად, რომ წასულიყვნენ და შესამუშაევბლად ბინარული ხეები, რომ აქვს 9 საათზე ფესვი, რაც საბოლოო შემთხვევაში, რომ ჩვენ გვყავს, ჩვენ ნაცვლად, ამ ეტაპზე, მიმდინარეობს გაიგო ცოტა ამ სხვა ვადა ჩვენ ვიყენებთ, როდესაც საუბარია ხეები, რომელსაც სიმაღლე. 

სიმაღლე ხე არის დაშორება root to ყველაზე შორეულ კვანძში, ან საკმაოდ რაოდენობის hops რომ თქვენ უნდა გააკეთოთ, რათა იწყება root და შემდეგ დასრულდება up ყველაზე შორეულ-node in ხე. დავხედოთ ზოგიერთი ხეები, რომ ჩვენ შედგენილი უფლება აქ, ვხედავთ, რომ თუ ავიღებთ ამ ხის ზედა მარცხენა კუთხეში და ჩვენ იწყება 3, მაშინ ჩვენ უნდა გააკეთოთ 1 hop მისაღებად 6, მეორე hop მისაღებად 7, და მესამე hop მისაღებად 9. ასე რომ, სიმაღლე ამ ხე არის 3. ჩვენ შეგვიძლია იგივე გავაკეთოთ სავარჯიშო სხვა ხეები განსაზღვრავდა ამ მწვანე, და ჩვენ ვხედავთ, რომ სიმაღლე ყველა ამ ხეები ასევე მართლაც 3. სწორედ იმ ნაწილს, რომელსაც ხდის მათ degenerate - რომ მათი სიმაღლე მხოლოდ ერთი ნაკლები რაოდენობის კვანძების მთელი ხე. თუ დავაკვირდებით ამ სხვა ხე რომ ალყაშემორტყმული წითელი, მეორეს მხრივ, ჩვენ ვხედავთ, რომ ყველაზე შორეული-ფოთოლი კვანძების არიან 6 და 9 - წასვლამდე მყოფი იმ კვანძების, რომ არ მყავს ბავშვები. ამიტომ, რათა მიიღონ root node ან 6 ან 9, ჩვენ უნდა გააკეთოთ ერთი hop მისაღებად 7 და შემდეგ მეორე hop მისაღებად 9, ანალოგიურად, მხოლოდ მეორე hop საწყისი 7 მისაღებად 6. ასე რომ, სიმაღლე ამ ხის გამო აქ არის მხოლოდ 2. თქვენ შეგიძლიათ უკან და გავაკეთოთ, რომ ყველა სხვა ხეები, რომ ჩვენ ადრე ისაუბრეს დაწყებული 7 და 6, და თქვენ ნახავთ, რომ სიმაღლე ყველა იმ ხეები ასევე 2. 

მიზეზი ჩვენ ვსაუბრობთ უბრძანა ბინარული ხეები და რატომ ისინი ზემოთ არის, რადგან თქვენ შეგიძლიათ ძებნის საშუალებით მათ ძალიან გავს გზა ძებნას მეტი დახარისხებული მასივი. ეს არის სადაც ვსაუბრობთ მისაღებად რომ გაუმჯობესებული lookup დრო მეტი მარტივი უკავშირდება სიაში. With უკავშირდება სია - თუ გინდათ იპოვოთ განსაკუთრებული ელემენტს - თქვენ საუკეთესო აპირებს გარკვეული ხაზოვანი ძებნა სადაც თქვენ დაიწყოს დასაწყისში სიაში და ჰოპ ერთი მიერ ერთი - ერთი კვანძის ერთი კვანძის - მთელი სია, სანამ თქვენთვის რასაც თქვენ ეძებს. ამასთან, თუ თქვენ გაქვთ ორობითი ხე რომ ინახება ამ ლამაზი ფორმატში, შეგიძლიათ რეალურად მიიღოთ მეტი ორობითი ძებნა გრძელდება სადაც თქვენ გათიშე და დაიპყროთ და ძებნის საშუალებით შესაბამისი ნახევარში ხე თითოეული ნაბიჯი. ვნახოთ, როგორ, რომ სამუშაოები. 

თუ ჩვენ გვაქვს - ისევ, რომ დაუბრუნდეს ჩვენს ორიგინალური ხე - ჩვენ ვიწყებთ დილის 7, ჩვენ გვაქვს 3 მარცხენა, 9 მარჯვენა, და ქვეშ 3 გვაქვს 6. თუ გვინდა, რომ მოძებნოთ ნომერი 6 ამ ხეს, ჩვენ გვინდა იწყება root. ჩვენ გვინდა შევადაროთ ღირებულების ჩვენ ვეძებთ, ამბობენ 6, ღირებულების შენახული კვანძში, რომ ჩვენ გაკეთებული ეძებს, 7, ნახავთ, რომ 6 მართლაც არანაკლებ 7, ასე რომ ჩვენ გვინდა გადავა მარცხნივ. თუ ღირებულება 6 იყო აღემატება 7, გვექნებოდა ნაცვლად გადავიდა უფლება. მას შემდეგ, რაც ჩვენ ვიცით, რომ - გამო სტრუქტურა ჩვენი უბრძანა ორობითი ხე - ყველა ღირებულებების არანაკლებ 7 ვაპირებთ ინახება მარცხნივ 7, არ საჭიროებას კი გადაიტვირთოთ გადახედეთ მარჯვენა მხარეს ხე. ერთხელ ჩვენ გადავა მარცხნივ და ჩვენ ახლა კვანძის შემცველი 3, ჩვენ შეგვიძლია გავაკეთოთ, რომ იგივე შედარებით, სადაც შევადარებთ 3 და 6. და ჩვენ ვხედავთ, რომ სანამ 6 - ღირებულება ჩვენ ვეძებთ - მეტია 3, ჩვენ შეგვიძლია წასვლა მარჯვენა მხარეს კვანძის შემცველი 3. იქ არ არის მარცხენა მხარეს აქ, რათა შევძლოთ და არ უგულებელყო რომ. მაგრამ ჩვენ მხოლოდ ვიცით, რომ რადგან ჩვენ ეძებს ხის თავად, და ვხედავთ, რომ ხე არ აქვს შვილი. 

ასევე საკმაოდ ადვილად გამოიყურებოდეს up 6 ამ ხეს თუ ვაკეთებთ მას საკუთარ თავს, როგორც ადამიანი, მაგრამ მოდით დაიცვას ამ პროცესში მექანიკურად მოსწონს კომპიუტერის ყველაფერს გააკეთებს ნამდვილად მესმის ალგორითმი. ამ ეტაპზე, ჩვენ ახლა ეძებს კვანძში, რომელიც შეიცავს 6, და ჩვენ ვეძებთ ღირებულება 6, ასე რომ, მართლაც, ჩვენ ნაპოვნი შესაბამისი კვანძის. ჩვენ ვნახეთ ღირებულება 6 ჩვენს ხე, და ჩვენ ვერ შეწყვეტენ ჩვენი ძიება. ამ ეტაპზე, დამოკიდებულია რა ხდება, ჩვენ შეგვიძლია ვთქვათ, დიახ, ჩვენ მოვნახეთ ღირებულება 6, ის არსებობს ჩვენს ხე. ან, თუ ჩვენ გეგმავს ჩადეთ კვანძის ან რაღაც, ჩვენ შეგვიძლია გავაკეთოთ, რომ ამ ეტაპზე. 

მოდით რამდენიმე lookups უბრალოდ, თუ რამდენად ამ სამუშაოები. მოდით შევხედოთ რა მოხდება თუ ჩვენ უნდა შევეცადოთ და ეძებოთ ღირებულება 10. თუ ჩვენ უნდა გამოიყურებოდეს up ღირებულება 10, გვინდა იწყება root. მე მინდა ვხედავ, რომ 10 მეტია 7, ასე რომ ჩვენ გვინდა გადავა უფლება. მე მინდა მოხვედრა 9 და შედარების 9 დან 10 და ვხედავ, რომ 9 მართლაც არანაკლებ 10. ასე რომ კიდევ ერთხელ, ჩვენ გვინდა ცდილობენ გადავიდეს უფლება. მაგრამ ამ ეტაპზე, ჩვენ გვინდა რომ ჩვენ დროს null კვანძში. არაფერია იქ. არაფერია აქ 10 უნდა იყოს. ეს არის სადაც შეგვიძლია ანგარიშს მარცხი - რომ არსებობს ნამდვილად არ 10 წლის ხე. და ბოლოს, მოდით გავლა შემთხვევაში ჩვენ ცდილობს გამოიყურებოდეს up 1 in ხე. ეს არის მსგავსი რა მოხდება თუ გადავხედავთ up 10, გარდა ნაცვლად აპირებს უფლება, ჩვენ ვაპირებთ წასვლა მარცხენა. ჩვენ იწყება 7 და ვხედავ, რომ 1 ნაკლებია, ვიდრე 7, ასე რომ ჩვენ გადავა მარცხნივ. ჩვენ მისაღებად 3 და ვხედავ, რომ 1 არის არანაკლებ 3, ასე რომ კიდევ ერთხელ ვცდილობთ გადასვლის მარცხენა. ამ ეტაპზე ჩვენ გვაქვს null კვანძში, ამიტომ კიდევ ერთხელ შეგვიძლია ანგარიშს უკმარისობა. 

თუ გსურთ გაიგოთ უფრო მეტი ბინარული ხეები, არსებობს მთელი bunch of fun პატარა პრობლემები, რომელიც შეგიძლიათ გააკეთოთ მათთან. მე გთავაზობთ პრაქტიკოსი ნახაზი აქედან დიაგრამების ერთი მიერ ერთი და შემდეგ მთელი საქართველოს სხვადასხვა ნაბიჯები, რადგან ეს მოვა სუპერ მოსახერხებელი არა მხოლოდ მაშინ, როდესაც თქვენ აკეთებთ Huffman კოდირების პრობლემა კომპლექტი არამედ მომავალი კურსები - მხოლოდ სასწავლო როგორ შესამუშაევბლად ამ მონაცემების სტრუქტურებისა და ვფიქრობ მეშვეობით პრობლემები ერთად კალამი და ქაღალდი ან, ამ შემთხვევაში, iPad და Stylus. 

ამ ეტაპზე, თუმცა, ჩვენ ვაპირებთ გადაადგილება დაკავდით კოდირების პრაქტიკა და ფაქტობრივად თამაში ამ ბინარული ხეები და ვხედავ. მე ვაპირებ გადართოთ უკან მეტი ჩემს კომპიუტერში. ამ ნაწილში მონაკვეთზე, ნაცვლად გამოყენებით CS50 Run ან CS50 სივრცეები, მე ვაპირებ გამოვიყენო ელექტრო მოწყობილობების. 

შემდეგ ერთად პრობლემა Set სპეციფიკაცია, მე ვხედავ, რომ მე უნდა გაიხსნას ელექტრო მოწყობილობების, გადასვლა ჩემს Dropbox ფოლდერი, შექმენით ფოლდერი მოუწოდა ნაწილი 7, და შემდეგ შევქმნათ ფაილი სახელად binary_tree.c. Here We Go. მაქვს ელექტრო უკვე ღია. მე ვაპირებ დახევის up ტერმინალში. მე ვაპირებ წასვლა Dropbox საქაღალდეში, მიიღოს დირექტორია მოუწოდა section7, და ვხედავ ეს სრულიად ცარიელი. ახლა მე ვაპირებ გახსენით binary_tree.c. კარგად. Here We Go - ცარიელი ფაილი. 

მოდით დავუბრუნდეთ სპეციფიკაცია. სპეციფიკაცია სთხოვს, რათა შეიქმნას ახალი ტიპის განსაზღვრება ამისთვის ორობითი ხე კვანძის შემცველი int ღირებულებებს - ისევე, როგორც ღირებულებების, რომ ჩვენ მიიპყრო გარეთ ჩვენს diagramming ადრე. ჩვენ ვაპირებთ გამოვიყენოთ ეს boilerplate typedef, რომ ჩვენ გავაკეთეთ უფლება აქ რომ თქვენ უნდა აღიაროს საწყისი პრობლემა Set 5 - თუ თქვენ არ hash table გზა დაპყრობის speller პროგრამა. თქვენ ასევე უნდა აღიაროს იგი გასულ კვირას სექციაში სადაც ჩვენ ვისაუბრეთ უკავშირდება სიები. გვაქვს ამ typedef of struct კვანძში, და ჩვენ, ამ struct კვანძში ამ სახელით struct კვანძის წინასწარ ასე, რომ ჩვენ შეგვიძლია შემდეგ უწოდებს, რადგან ჩვენ გვინდა struct კვანძის პოინტერები როგორც ნაწილი ჩვენი struct, მაგრამ ჩვენ მაშინ ალყაში აქცევს ამ - უფრო სწორად, თან ერთვის ამ - ში typedef ასე რომ, მოგვიანებით კოდი, ჩვენ შეგვიძლია ეხება ამ struct როგორც მხოლოდ კვანძის ნაცვლად struct კვანძში. 

ეს იქნება ძალიან ჰგავს საგნით დაკავშირებული სიაში განმარტება, რომ ჩვენ ვნახეთ გასულ კვირას. ამისათვის მოდით დავიწყო წერილობით გარეთ boilerplate. ჩვენ ვიცით, რომ ჩვენ გვყავს მთელ რიცხვს ღირებულება, ამიტომ ჩვენ დასვა int ღირებულება, ხოლო შემდეგ ნაცვლად, რომელმაც მხოლოდ ერთი მომცეთ შემდეგი ელემენტს - როგორც ჩვენ შემოიერთა საგნით დაკავშირებული სიები - ჩვენ ვაპირებთ აქვს მარცხნივ და მარჯვნივ ბავშვის პოინტერები. რომ საკმაოდ მარტივია ძალიან - struct კვანძის * მარცხენა ბავშვი; და struct კვანძის * უფლება ბავშვის. ზემოთ. რომ ჰგავს საკმაოდ კარგი დასაწყისია. მოდით დავუბრუნდეთ სპეციფიკაცია. 

ახლა ჩვენ უნდა განაცხადოს გლობალური კვანძის * ცვლადი ამისთვის ფესვი ხე. ჩვენ ვაპირებთ, რომ ეს გლობალური ისევე ჩვენ მივიღეთ პირველი მაჩვენებელი ჩვენს უკავშირდება სიაში ასევე გლობალური. ეს იმდენად, რომ ფუნქციების, რომ ჩვენ წერენ ჩვენ არ გვაქვს შენარჩუნება გავლით გარშემო ამ root - თუმცა ჩვენ ვხედავთ, რომ თუ გვინდა დავწეროთ ამ ფუნქციების რეკურსიული, ეს შესაძლოა უკეთესი კი არ უნდა გაიაროს ეს გარშემო, როგორც გლობალური პირველ რიგში და ნაცვლად ინიციალიზაცია იგი ადგილობრივად თქვენს მთავარ ფუნქციას. მაგრამ ჩვენ გავაკეთებთ გლობალურად უნდა დაიწყოს. ისევ და ისევ, ჩვენ მივცემ რამდენიმე ფართების, და მე ვაპირებ განაცხადოს კვანძის * root. უბრალოდ, დარწმუნდით, რომ მე არ დატოვებენ ამ uninitialized, მე ვაპირებ ვაყენებთ მას ტოლი null. ახლა კი, მთავარი ფუნქცია - რაც ჩვენ წერენ მართლაც სწრაფად სწორედ აქ - int ძირითადი (int argc, const char * argv []) - და მე ვაპირებ დაიწყება გამოცხადების ჩემი argv მასივს როგორც const მხოლოდ ისე, რომ მე ვიცი რომ ეს არგუმენტებია არგუმენტს, რომელიც მე ალბათ არ მინდა ცვლილებები. თუკი მინდა ცვლილებები მათ მე უნდა სავარაუდოდ მიღების ასლები მათ. თქვენ ნახავთ ამ ბევრს კოდი. ეს ჯარიმა ან გზა. ეს ჯარიმა უნდა დატოვონ, როგორც - გამომრჩეს const თუ გსურთ. მე, როგორც წესი, დააყენოს ის მხოლოდ ისე, რომ მე შეგახსენებთ თავს  რომ მე ალბათ არ მინდა ცვლილებები იმ არგუმენტებს. 

როგორც ყოველთვის, მე ვაპირებ მოიცავს ამ დაბრუნების 0 ხაზის დასასრულს მთავარ. აქ, მე ვრთავ ჩემი root node. როგორც იგი დგას ახლავე, მაქვს კურსორი რომ მითითებული null, ამიტომ მიუთითებს არაფერი. იმისათვის, რომ რეალურად შეიქმენით კვანძში, მე ჯერ უნდა გამოყოს მეხსიერება ამისთვის. მე ვაპირებ ამას მიერ მიღების მეხსიერების შესახებ ბევრი გამოყენებით malloc. მე ვაპირებ მითითებული root ტოლია შედეგად malloc, და მე ვაპირებ გამოვიყენო sizeof ოპერატორის გამოთვლა ზომის კვანძი. მიზეზი იმისა, რომ გამოვიყენო sizeof კვანძის ნაცვლად, ვთქვათ, აკეთებს რაღაც მსგავსი - malloc (4 + 4 +4) ან malloc 12 - ეს იმიტომ მინდა ჩემი კოდი უნდა იყოს, როგორც თავსებადი შეიძლება. მინდა შეძლებს მიიღოს ამ. გ ფაილი, კომპილირება on ელექტრო მოწყობილობების, და შემდეგ კომპილირება ჩემს 64-bit Mac - ან სრულიად განსხვავებული არქიტექტურა - და მინდა ამ ყველა მუშაობას იმავე. 

თუ მე მიღების დაშვებების შესახებ ზომა ცვლადები - ზომა int ან ზომის მიმთითებელი - მაშინ მე ასევე მიღების დაშვებების შესახებ სახის არქიტექტურის რომელზედაც ჩემი კოდი წარმატებით შეგიძლიათ კომპილაციის როდესაც აწარმოებს. ყოველთვის გამოიყენეთ sizeof ნაცვლად ხელით შემაჯამებელი struct სფეროებში. სხვა მიზეზი არის ის, რომ იქ შესაძლოა padding რომ შემდგენელი აყენებს შევიდა struct. მაშინაც კი, მხოლოდ შემაჯამებელი ინდივიდუალური სფეროებში არ არის რაღაც, რომ თქვენ, როგორც წესი, გსურთ, ასე, რომ წაშალოთ ხაზი. ახლა ნამდვილად ინიციალიზაცია ამ ძირეული კვანძის, მე ვაპირებ უნდა შეაერთედ წელს ფასეულობების თითოეული მისი სხვადასხვა სფეროში. მაგალითად, ღირებულება ვიცი მინდა ინიციალიზაცია დან 7, და ახლა მე ვაპირებ მითითებული მარცხენა ბავშვი იყოს null და უფლება ბავშვს ასევე null. მშვენიერია ჩვენ გავაკეთეთ ის ნაწილი სპეც. 

სპეციფიკაცია ქვემოთ ბოლოში გვერდზე 3 მკითხავს, ​​რომ შევქმნათ კიდევ სამი კვანძების - ერთი შემცველი 3, ერთი შემცველი 6, და ერთი 9 - და შემდეგ WIRE მათ ასე გამოიყურება ზუსტად ისევე, ჩვენი ხე დიაგრამაზე რომ ჩვენ ვსაუბრობთ ადრე. მოდით, რომ საკმაოდ სწრაფად აქ. თქვენ ნახავთ მართლაც სწრაფად, რომ მე ვაპირებ წერა bunch of დუბლიკატი კოდი. მე ვაპირებ შექმნას კვანძის * და მე ვაპირებ მოვუწოდო მას სამი. მე ვაპირებ ვაყენებთ მას ტოლი malloc (sizeof (კვანძის)). მე ვაპირებ მითითებული სამი> ღირებულება = 3. სამი -> left_child = NULL; სამი -> მარჯვენა _child = NULL; ისევე. რომ გამოიყურება საკმაოდ მსგავსი ინიციალიზაციისას ფესვი, და სწორედ ის, რაც მე ვაპირებ უნდა გავაკეთოთ, თუ დავიწყო ინიციალიზაციისას 6 და 9 ისევე. მე გავაკეთებ, რომ ნამდვილად სწრაფად აქ - ფაქტობრივად, მე ვაპირებ პატარა ასლი და პასტა, და დარწმუნდით, რომ მე - კარგად.  ახლა მაქვს ეს გადაწერა და შემიძლია წავიდეთ წინ და დაადგინა ამ ტოლია 6. თქვენ ხედავთ, რომ ამ იღებს awhile და არ არის სუპერ ეფექტური. რაღაც ცოტა, ჩვენ წერენ ფუნქცია რომ ამას ჩვენთვის. მინდა ჩანაცვლება ამ 9, შეცვლის, რომ 6. 

ახლა ჩვენ მივიღეთ ყველა ჩვენი კვანძების შექმნა და ინიციალიზაცია. გვაქვს ჩვენი ძირეული მითითებული ტოლია 7, ან შეიცავს ღირებულება 7, ჩვენი კვანძის შემცველი 3, ჩვენი კვანძის შემცველი 6, და ჩვენი კვანძის შემცველი 9. ამ ეტაპზე, ყველა ჩვენ უნდა გავაკეთოთ არის მავთულის ყველაფერი up. მიზეზი მე ინიციალიზაცია ყველა მითითებას null მხოლოდ ისე, რომ მე დარწმუნდით, რომ მე არ მაქვს რაიმე uninitialized პოინტერები იქ შემთხვევით. და ასევე წლიდან, ამ ეტაპზე, მე მხოლოდ უნდა რეალურად დააკავშირებს კვანძების ერთმანეთს - to პირობა, რომ ისინი რეალურად უკავშირდება - მე არ უნდა გაიაროს და მიიღოს დარწმუნებული ვარ, რომ ყველა nulls არიან იქ სათანადო ადგილებში. 

დასაწყისი ფესვი, მე ვიცი, რომ root მარცხენა ბავშვი არის 3. მე ვიცი, რომ ძირეული უფლება ბავშვი 9. ამის შემდეგ, მხოლოდ სხვა ბავშვს რომ მე არ დაუტოვებიათ ფიქრი არის 3 უფლება ბავშვს, რომელიც არის 6. ამ ეტაპზე, ეს ყველაფერი გამოიყურება საკმაოდ კარგი. ჩვენ წაშალოთ ზოგიერთი ხაზები. ახლა ყველაფერი გამოიყურება საკმაოდ კარგი. მოდით დავუბრუნდეთ ჩვენი სპეციფიკაცია და რა უნდა გავაკეთოთ შემდეგი. 

ამ ეტაპზე, ჩვენ უნდა დავწეროთ ფუნქცია ე.წ. "შეიცავს" ერთად პროტოტიპი 'bool შეიცავს (int value). და ამ შეიცავს ფუნქციის დაბრუნებას აპირებს ჭეშმარიტი  თუ ხე მიუთითა ჩვენი გლობალური root ცვლადი  შეიცავს ღირებულება შევიდა ფუნქცია და ცრუ სხვაგვარად. მოდით წავიდეთ წინ და გაგვაჩნია. ეს იქნება ზუსტად ისევე lookup, რომ ჩვენ მიერ ხელით iPad უბრალოდ ცოტა წინ. მოდით zoom უკან ცოტა და გადახვევა up. ჩვენ ვაპირებთ დააყენა ამ ფუნქციის უფლება ზემოთ ჩვენი მთავარი ფუნქცია ისე, რომ ჩვენ არ გვაქვს რაიმე სახის prototyping. ასე რომ, bool შეიცავს (int value). იქ ჩვენ წავიდეთ. იქ ჩვენი boilerplate დეკლარაციას. უბრალოდ დარწმუნდით, რომ ეს ხელს კომპილაციის, მე ვაპირებ წავიდეთ წინ და უბრალოდ დააყენეთ თანაბარი დაბრუნების ცრუ. ახლავე ამ ფუნქციის მხოლოდ ხელს არაფერი და ყოველთვის აცხადებს, რომ ღირებულება, რომ ჩვენ ვეძებთ არ არის ხე. 

ამ ეტაპზე, ეს ალბათ კარგი იდეა - მას შემდეგ, რაც ჩვენ წერილობით მთელი bunch of კოდი და ჩვენ კი არ სცადა ტესტირების ამაზე - რომ დავრწმუნდეთ, რომ ყველა ადგენს. არსებობს რამდენიმე რამ, რომ ჩვენ უნდა გავაკეთოთ, რათა დავრწმუნდეთ, რომ ეს ხელს რეალურად ადგენენ. პირველი, თუ ჩვენ გამოყენებით ნებისმიერი ფუნქციების ნებისმიერ ბიბლიოთეკების, რომ ჩვენ ჯერ არ შედის. ფუნქციების ჩვენ გამოიყენება იმდენად, რამდენადაც არიან malloc, და მაშინ ჩვენ ასევე იყენებს ამ ტიპის - ამ არასტანდარტული ტიპი სახელწოდებით "bool' - რაც შედის სტანდარტულ bool header ფაილი. ჩვენ ნამდვილად გვინდა მოიცავს სტანდარტული bool.h ამისთვის bool ტიპის, და ჩვენ ასევე გვინდა # მოიცავს სტანდარტული lib.h სტანდარტული ბიბლიოთეკები რომელიც მოიცავს malloc და თავისუფალი, და ყველა რომ. ასე რომ, zoom out, ჩვენ ვაპირებთ დატოვა. მოდით ვეცადოთ და დარწმუნდით, რომ ეს რეალურად გააკეთა კომპილირების. ჩვენ ვხედავთ, რომ ეს ასეა, ასე ჩვენ სწორ გზაზე. 

მოდით გახსენით binary_tree.c ერთხელ. იგი ადგენს. მოდით დაცემას და დარწმუნდით, რომ ჩვენ ჩადეთ სერიოზული მოწოდებები ჩვენი შეიცავს ფუნქცია - უბრალოდ, დარწმუნდით, რომ ეს ყველაფერი კარგად და კარგი. მაგალითად, როდესაც ჩვენ გავაკეთეთ რამდენიმე lookups ჩვენს ხე ადრე, ჩვენ შევეცადეთ ეძებოთ ღირებულებების 6, 10 და 1, და ვიცოდით, რომ 6 იყო ხე, 10 არ იყო ხე, და 1 არ იყო ხის ან. მოდით გამოვიყენოთ იმ ნიმუშის მოუწოდებს როგორც გზა გაერკვნენ თუ არა ჩვენი შეიცავს ფუნქცია მუშაობს. იმისათვის, რომ გავაკეთოთ, მე ვაპირებ გამოიყენოთ printf ფუნქცია, და ჩვენ ვაპირებთ ამობეჭდოთ შედეგი ზარი შეიცავს. მე ვაპირებ მა სტრიქონი "შეიცავს (% d) = რადგან  ჩვენ ვაპირებთ plug in ღირებულება, რომ ჩვენ ვაპირებთ ვეძებოთ, და =% s \ n "და გამოიყენოს, რომ როგორც ჩვენი სტრიქონში. ჩვენ უბრალოდ აპირებს ვხედავ - სიტყვასიტყვით ამობეჭდოთ ეკრანზე - რა ჰგავს ფუნქცია ზარი. ეს არ არის რეალურად ფუნქცია ზარი.  ეს არის მხოლოდ string განკუთვნილია ჰგავს ფუნქცია ზარი. 

ახლა ჩვენ ვაპირებთ შეაერთედ წელს ღირებულებებს. ჩვენ ვაპირებთ შევეცადოთ შეიცავს წლის 6, და მერე რა ჩვენ ვაპირებთ აქ არის გამოიყენოს რომ ternary ოპერატორს. ვნახოთ - შეიცავს 6 - ასე, ახლა მე შეიცავდა 6 და თუ შეიცავს 6 მართალია, სიმებიანი რომ ჩვენ ვაპირებთ გააგზავნეთ% s ფორმატი ხასიათი იქნება სტრიქონი "ჭეშმარიტი". მოდით გადახვევა მეტი ცოტა. წინააღმდეგ შემთხვევაში, ჩვენ გვინდა გაგზავნას სტრიქონი "ცრუ" თუ შეიცავს 6 ანაზღაურება ყალბი. ეს არის პატარა Goofy ორიენტირებული, მაგრამ მე გაერკვნენ შეიძლება ასევე ილუსტრაციას რა ternary ოპერატორი ჰგავს რადგან ჩვენ არ გვინახავს მისი awhile. ეს იქნება ლამაზი, მოსახერხებელი გზა გაერკვნენ, თუ ჩვენი შეიცავს ფუნქცია მუშაობს. მე ვაპირებ გადახვევა უკან მეტი მარცხნივ, და მე ვაპირებ და ჩასვით ეს ხაზი რამდენჯერმე. იგი შეიცვალა ზოგიერთი ამ ფასეულობების გარშემო, ასე რომ, ეს იქნება 1 და ეს იქნება 10. 

ამ ეტაპზე გვაქვს ლამაზი შეიცავს ფუნქციას. გვაქვს გარკვეული ტესტები, და ვნახავთ, თუ ეს სამუშაოები. ამ ეტაპზე ჩვენ წერილობითი კიდევ რამდენიმე კოდი. ახლა დაეტოვებინა გარეთ და დარწმუნდით, რომ ყველაფერი ჯერ კიდევ ადგენს. Quit გარეთ, და ახლა მოდით შევეცადოთ მიღების ორობითი ხე ერთხელ. ასევე, ის ჰგავს გვაქვს შეცდომა, და ჩვენ მივიღეთ ეს ცალსახად ვაცხადებთ ბიბლიოთეკის ფუნქცია printf. როგორც ჩანს, ჩვენ უნდა წავიდეს და # მოიცავს standardio.h. და ამ ყველაფერს უნდა შეადგინოს. ჩვენ ყველა კარგი. ახლა მოდით შევეცადოთ გაშვებული ორობითი ხე და ვნახოთ, რა მოხდება. აქ ვართ,. / Binary_tree, და ჩვენ ვხედავთ, რომ, როგორც ველოდით - იმიტომ, რომ ჩვენ არ განხორციელდა შეიცავს გაუკეთებია, უფრო სწორად, ჩვენ უბრალოდ დასვა დაბრუნების ცრუ - ჩვენ ვხედავთ, რომ ეს მხოლოდ დაბრუნების ცრუ ყველა მათგანი, ასე რომ ყველა მუშაობს დიდი ნაწილი საკმაოდ კარგად. 

მოდით დავუბრუნდეთ და რეალურად განახორციელებს შეიცავს ამ ეტაპზე. მე ვაპირებ გადახვევა down, მიუახლოვდით, და - გახსოვდეთ, ალგორითმი, რომ ჩვენ გამოყენებული იყო, რომ ჩვენ დაიწყო ძირეული კვანძის და შემდეგ ყოველ კვანძში, რომ ჩვენ ვაწყდებით, ჩვენ შედარებით, და ეფუძნება, რომ შედარებით ჩვენ არც გადავა მარცხენა ბავშვის ან მარჯვნივ შვილი. ეს აპირებს გამოიყურებოდეს ძალიან ჰგავს ორობითი ძებნა კოდი, რომ ჩვენ წერდა ადრე ვადით. როდესაც ჩვენ ვიწყებთ off, ჩვენ ვიცით, რომ ჩვენ გვინდა გაიმართება მიმდინარე კვანძის რომ ჩვენ შევხედავთ, და მიმდინარე კვანძის აპირებს ინიციალიზდება to root node. და ახლა, ჩვენ ვაპირებთ შენარჩუნება გადის ხე, და გვახსოვდეს, რომ ჩვენი შეჩერების პირობით -  როდესაც ჩვენ რეალურად მუშაობდა მეშვეობით მაგალითად ხელით - იმ დროს, როცა ჩვენ შეექმნა null კვანძში, არა მაშინ, როცა ჩვენ შევხედეთ null ბავშვი, არამედ, როდესაც ჩვენ რეალურად გადავიდა node in ხე და აღმოჩნდა, რომ ჩვენ დროს null კვანძში. ჩვენ ვაპირებთ iterate სანამ მიმდ. არ არის ტოლი null. და რა ჩვენ ვაპირებთ? ჩვენ ვაპირებთ შევამოწმოთ, თუ (მიმდ. -> ღირებულების == ღირებულების), მაშინ ჩვენ ვიცით, რომ ჩვენ რეალურად ნაპოვნია კვანძში, რომ ჩვენ ვეძებთ. ასე რომ, ჩვენ შეიძლება დაბრუნდეს ჭეშმარიტი. წინააღმდეგ შემთხვევაში, ჩვენ გვინდა თუ არა მნიშვნელობა ნაკლებია ღირებულება. თუ მიმდინარე კვანძის ს მნიშვნელობა ნაკლებია ღირებულების ჩვენ ვეძებთ, ჩვენ ვაპირებთ გადასვლის უფლება. ასე რომ, მიმდ. = მიმდ. -> right_child და სხვაგვარად, ჩვენ ვაპირებთ გადაინაცვლებს მარცხენა. მიმდ. = მიმდ. -> left_child;. Pretty მარტივი. 

ალბათ აღიარებს loop, რომელიც გამოიყურება ძალიან გავს ამ საწყისი ორობითი ძებნა ადრე ვადა, გარდა მაშინ საქმე გვქონდა დაბალი, საშუალო და მაღალი. აქ, ჩვენ უბრალოდ უნდა შევხედოთ მიმდინარე ღირებულება, ამიტომ ლამაზი და მარტივი. მოდით დარწმუნდით ეს კოდი მუშაობს. პირველი, დარწმუნდით, რომ იგი ადგენს. როგორც ჩანს, ის ჯერ. მოდით ვეცადოთ გაშვებული იგი. მართლაც, იგი ბეჭდავს out ყველაფერი, რაც ჩვენ გვგონია. იგი აღმოაჩენს 6 წლის ხე, არ იპოვოს 10 რადგან 10 არ in ხე, და არ იპოვოს 1 ან იმიტომ 1 ისიც არ ხე. მაგარი რამეები. 

კარგად. მოდით დავუბრუნდეთ ჩვენი სპეციფიკაცია და ხედავთ რა მომავალი. ახლა მას სურს დაამატოთ კიდევ რამდენიმე კვანძების ჩვენი ხე. მას სურს დაამატოთ 5, 2 და 8, და დარწმუნდით, რომ ჩვენი შეიცავს კოდი დღემდე მუშაობს როგორც მოსალოდნელია. მოდით წავიდეთ გავაკეთოთ, რომ. ამ ეტაპზე, ვიდრე აკეთებს, რომ შემაშფოთებელი და ჩასვით ისევ, მოდით დავწეროთ ფუნქცია რეალურად შექმნა კვანძში. თუ ჩვენ გადახვევა ქვემოთ ყველა გზა ძირითადი, ჩვენ ვხედავთ, რომ ჩვენ ამით ძალიან ჰგავს კოდი უსასრულოდ ყოველ ჯერზე, რომ ჩვენ გვინდა შევქმნათ კვანძში. 

მოდით დავწეროთ ფუნქცია, რომელიც რეალურად ააშენოს კვანძის ჩვენთვის და დაგვიბრუნოთ ის. მე ვაპირებ მოვუწოდო მას build_node. მე ვაპირებ აშენებას კვანძის განსაკუთრებული მნიშვნელობა. მიუახლოვდით აქ. პირველი, რაც მე ვაპირებ ამის გაკეთებას რეალურად შექმნას ფართი კვანძის შესახებ ბევრი. ასე რომ, node * N = malloc (sizeof (კვანძის)); N -> ღირებულება = value; და შემდეგ აქ, მე უბრალოდ აპირებს ინიციალიზაცია ყველა ველი უნდა იყოს შესაბამის მნიშვნელობებზე. და ბოლომდე, ჩვენ დავიბრუნოთ ჩვენი კვანძში. კარგად. ერთი რამ აღვნიშნო, რომ ამ ფუნქციის უფლება აქ დაბრუნებას აპირებს მომცეთ მეხსიერება, რომ უკვე ბევრი-გამოყოფილი. რა არის ლამაზი შესახებ არის ის, რომ ამ კვანძის ახლა - ჩვენ უნდა გამოაცხადოს ის შესახებ ბევრი, რადგან თუ ჩვენ გამოაცხადა on დასტის ჩვენ ვერ შეძლებს ამის გაკეთებას ამ ფუნქციის მოსწონს ეს. რომ მეხსიერების წავიდოდა გარეთ ფარგლებს და იქნება ბათილად, თუ ჩვენ შევეცადეთ ვებგვერდზე მოგვიანებით. მას შემდეგ, რაც ჩვენ ვაცხადებთ ბევრი-გამოყოფილი მეხსიერება, ჩვენ ვაპირებთ უნდა იზრუნოს გამონთავისუფლების იგი მოგვიანებით ჩვენი პროგრამის არ გაჟონვა ნებისმიერი მეხსიერება. ჩვენ ბევრი punting რომ ყველაფერს სხვაგან კოდი უბრალოდ სიმარტივის გულისთვის დროს, მაგრამ თუ ოდესმე წერენ ფუნქცია რომ ასე გამოიყურება სადაც თქვენ მოხვდით - ზოგიერთი ეძახით malloc ან realloc შიგნით - თქვენ გვინდა დავრწმუნდეთ, რომ თქვენ დააყენა გარკვეული კომენტარი აქ რომ ამბობს, Hey, თქვენ იცით, დააბრუნებს ბევრი-გამოყოფილი კვანძის ინიციალიზაცია ერთად გაიარა-ღირებულების. და მაშინ გვინდა დავრწმუნდეთ, რომ თქვენ დააყენა გარკვეული გაითვალისწინოთ, რომ ამბობს Caller უნდა გასათავისუფლებლად დაბრუნდა მეხსიერება. რომ გზა, თუ ვინმეს ოდესმე მიდის და იყენებს, რომ ფუნქცია, მათ იციან, რომ რაც ისინი უკან რომ ფუნქცია რაღაც მომენტში უნდა გათავისუფლდებიან. 

ვთქვათ, რომ ყველა კარგად და კარგი აქ, ჩვენ შეგვიძლია წავიდეთ ქვემოთ შევიდა ჩვენი კოდი და შეცვლის ყველა ამ ხაზების უფლება აქ ერთად მოუწოდებს ჩვენს Build კვანძის ფუნქციას. მოდით, რომ მართლაც სწრაფად. ერთი ნაწილი, რომ ჩვენ არ ვაპირებთ, შევცვალოთ ეს ნაწილი ქვევით აქ ბოლოში, სადაც ჩვენ რეალურად WIRE up კვანძების აღვნიშნო ერთმანეთს, იმიტომ, რომ ჩვენ არ შეგვიძლია გავაკეთოთ ჩვენი ფუნქცია. მაგრამ, მოდით root = build_node (7); კვანძის * სამი = build_node (3); კვანძის * ექვსი = build_node (6); კვანძის * ცხრა = build_node (9);. და ახლა, ჩვენც გვინდა დაამატოთ კვანძების ამისთვის - კვანძის * ხუთი = build_node (5); კვანძის * რვა = build_node (8); და რა იყო სხვა კვანძის? ვნახოთ აქ. გვინდოდა აგრეთვე დაამატოთ 2 - კვანძის * ორი = build_node (2);. კარგად. ამ ეტაპზე, ჩვენ ვიცით, რომ გვაქვს 7, 3, 9, და 6 ყველა სახაზო up სათანადოდ, მაგრამ რაც შეეხება 5, 8 და 2? შენარჩუნება ყველაფერი შესაბამისი ბრძანებით, ჩვენ ვიცით, რომ სამი უფლება ბავშვი 6. ასე რომ, თუ ჩვენ ვაპირებთ დაამატოთ 5, 5 ასევე ეკუთვნის in მარჯვენა მხარეს ხე რომელიც 3 არის root, ასე 5 ეკუთვნის როგორც მარცხენა ბავშვი 6. ჩვენ შეგვიძლია ამის გაკეთება იმით, ექვსი -> left_child = ხუთი; და შემდეგ 8 ეკუთვნის როგორც მარცხენა ბავშვი 9, ასე ცხრა -> left_child = რვა; და შემდეგ 2 არის მარცხენა ბავშვი 3, ასე რომ ჩვენ შეგვიძლია გავაკეთოთ, რომ აქ - შენ -> left_child = ორი;. თუ თქვენ არ საკმაოდ დაიცვას ერთად რომ, მე გთავაზობთ დავხატოთ ის თავს. 

კარგად. გადავარჩინოთ ეს. მოდით გასვლა და დარწმუნდით, რომ იგი ადგენს, და მაშინ ჩვენ შეგიძლიათ დაამატოთ ჩვენი არსებული მოწოდებით. როგორც ჩანს, ყველაფერი მაინც ადგენს. მოდით წავიდეთ და დაამატოთ ზოგიერთი შეიცავს მოუწოდებს. ისევ, მე აპირებს ცოტა ასლი და პასტა. ახლა მოვძებნოთ 5, 8, და 2. კარგად. მოდით დავრწმუნდეთ, რომ ამ ყველა გამოიყურება კარგი მაინც. მშვენიერია შენახვა და გასვლა. ახლა გადავდგათ, კომპილირდება და ახლა მოდით აწარმოებს. მდებარეობა შედეგების, როგორც ჩანს ყველაფერი მუშაობს უბრალოდ ლამაზი და კარგად. მშვენიერია ახლა გვაქვს ჩვენი შეიცავს ფუნქციას წერილობითი. მოდით გადაადგილება და დაიწყოს მუშაობა როგორ ჩადეთ კვანძების შევიდა ხე რადგან, როგორც ვაკეთებთ ეს ახლავე, რამ არ არის ძალიან ლამაზი. 

თუ ჩვენ დავუბრუნდებით სპეციფიკაცია, იგი გვთხოვს დაწერა ფუნქციის მოუწოდა ჩადეთ - ერთხელ, დაბრუნების bool ამისთვის თუ არა ჩვენ შეგვიძლია რეალურად ჩადეთ კვანძის შევიდა ხე - და მაშინ ღირებულება ჩასასმელად შევიდა ხე არის მითითებული, როგორც ერთადერთი არგუმენტი ჩვენი ჩანართით ფუნქცია. ჩვენ TRUE თუ ჩვენ შევძელით მართლაც ჩადეთ კვანძის შემცველი ღირებულება შევიდა ხე, რაც იმას ნიშნავს, რომ ჩვენ, ერთი, ჰქონდა საკმარისი მეხსიერება, და შემდეგ ორი, რომ კვანძის არ უკვე არსებობს ხე წლიდან - გახსოვდეთ, ჩვენ არ ვაპირებთ, რომ გვქონდეს დუბლიკატი ღირებულებების ხე, უბრალოდ, რათა რამ მარტივი. კარგად. თავში კოდი. გახსენით ეს. მიუახლოვდით bit, მაშინ გადახვევა down. მოდით დააყენა ჩასმა ფუნქციის უფლება ზემოთ შეიცავს. ისევ და ისევ, ეს იქნება მოუწოდა bool ჩანართით (int value). Give it ცოტა მეტი სივრცე და შემდეგ, როგორც ჩვეულებრივ, მოდით დააყენა სანაცვლოდ ყალბი დროს ბოლომდე. ახლა ქვემოთ ბოლოში, მოდით წავიდეთ წინ და ნაცვლად ხელით ვაშენებთ კვანძების მთავარ თავი და გაყვანილობა მათ მდე აღვნიშნო, რომ ერთმანეთი ისე ვაკეთებთ, ჩვენ დაეყრდნოს ჩვენი ჩანართით ფუნქცია გაგვაჩნია. ჩვენ არ დაეყრდნონ ჩვენი ჩანართით ფუნქცია აშენება მთელი ხე ნულიდან უბრალოდ არ არის, არამედ ჩვენ დავაღწიოთ ამ ხაზები - we'll კომენტარის აღნიშნული ხაზები - რომ ავაშენოთ კვანძების 5, 8, და 2. და ამის ნაცვლად, ჩვენ ჩადეთ მოუწოდებს ჩვენს ჩანართით ფუნქცია რომ დავრწმუნდეთ, რომ რეალურად მუშაობს. Here We Go. 

ახლა ჩვენ გამოეხმაურა აღნიშნული ხაზები. ჩვენ მხოლოდ 7, 3, 9, და 6 ჩვენს ხე ამ ეტაპზე. რომ დავრწმუნდეთ, რომ ეს ყველაფერი სამუშაო, ჩვენ შეგვიძლია დააშორებს, რათა ჩვენი ორობითი ხე, გაუშვით და ვხედავთ, რომ შეიცავს არის გვეუბნებოდა, რომ ჩვენ მთლიანად უფლება - 5, 8 და 2 არ არიან ხე. უკან დაბრუნება შევიდა კოდი, და როგორ მივდივართ ჩასასმელად? გახსოვთ რა გავაკეთეთ, როდესაც ჩვენ რეალურად ჩასმა 5, 8, და 2 ადრე. ჩვენ ითამაშა რომ Plinko თამაში, სადაც ჩვენ დაიწყო root, ჩამოიწია ხე ერთი ერთი სანამ ჩვენ აღმოვაჩინეთ შესაბამისი უფსკრული, და მაშინ ჩვენ სახაზო წელს კვანძის შესაბამის ადგილზე. ჩვენ ვაპირებთ გავაკეთოთ იგივე. ეს არის ძირითადად, როგორიცაა წერა კოდი, რომ ჩვენ გამოყენებული შეიცავს ფუნქცია მოძიების ადგილზე სადაც კვანძის უნდა იყოს, და მაშინ ჩვენ უბრალოდ აპირებს ჩადეთ კვანძის უფლება არსებობს. დავიწყოთ აკეთებს, რომ. 

ამიტომ კვანძის * მიმდ. = root; ჩვენ უბრალოდ აპირებს დაიცვას შეიცავს კოდი სანამ ჩვენ, რომ არ საკმაოდ ჩვენთვის მუშაობა. ჩვენ ვაპირებთ გავლა ხე ხოლო მიმდინარე ელემენტს არ null, და თუ ჩვენ ვხედავთ, რომ მიმდ. ღირებულების ტოლია ღირებულება, რომ ჩვენ ვცდილობთ ჩასასმელად - ასევე, ეს არის ერთ შემთხვევებში, რომელშიც ჩვენ ვერ რეალურად ჩადეთ კვანძში შევიდა ხე რადგან ეს იმას ნიშნავს, რომ ჩვენ გვაქვს დუბლიკატი ღირებულება. აქ ჩვენ რეალურად დაბრუნებას აპირებს ყალბი. ახლა, სხვას თუ მიმდ. ს მნიშვნელობა ნაკლებია ღირებულება, ახლა ჩვენ ვიცით, რომ ჩვენ გადავა უფლება  რადგან ღირებულების ეკუთვნის სწორი ნახევარში მიმდ. ხე. წინააღმდეგ შემთხვევაში, ჩვენ ვაპირებთ გადაინაცვლებს მარცხენა. სწორედ ძირითადად ჩვენი შეიცავს ფუნქციონირებას უფლება არსებობს. 

ამ ეტაპზე, ერთხელ ჩვენ დასრულდება ამ ხოლო მარყუჟის, ჩვენი მიმდ. მაჩვენებელი იქნება მიუთითებს null თუ ფუნქცია არ უკვე დაბრუნდა. ჩვენ ამიტომ მქონე მიმდ. ადგილზე, სადაც ჩვენ გვინდა, რომ ჩადეთ ახალი კვანძში. რა არის გასაკეთებელი არის რეალურად ააშენოს ახალი კვანძის, რაც ჩვენ შეგვიძლია გავაკეთოთ საკმაოდ მარტივად. ჩვენ შეგვიძლია გამოვიყენოთ ჩვენი სუპერ მოსახერხებელი Build კვანძის ფუნქციას, და ის, რასაც ჩვენ არ ადრე - ჩვენ უბრალოდ სახის აიღო თავისთავად მაგრამ ახლა ჩვენ ყველაფერს გავაკეთებთ, რათა დავრწმუნდეთ, - ჩვენ ვამოწმებთ დავრწმუნდეთ, რომ ღირებულება დაბრუნდა ახალი კვანძში იყო სინამდვილეში არ null, რადგან ჩვენ არ გვინდა, რომ დაიწყოს წვდომის რომ მეხსიერების თუ ეს null. ჩვენ შეგვიძლია შევამოწმოთ რომ დავრწმუნდეთ, რომ ახალი კვანძში არ არის ტოლი null. ან ნაცვლად, ჩვენ შეგვიძლია მხოლოდ თუ ის რეალურად არის null, და თუ ეს null, მაშინ ჩვენ შეგვიძლია მხოლოდ დაბრუნების ცრუ დასაწყისში. 

ამ ეტაპზე, ჩვენ უნდა WIRE ახალი კვანძის მის შესაბამის ადგილზე in ხე. თუ ჩვენ ვიხსენებთ ძირითად და სად ვიყავით რეალურად გაყვანილობა წელს ფასეულობების წინაშე, ჩვენ ვხედავთ, რომ გზა ვაკეთებდით, როცა გვინდოდა დააყენა 3 in ხე იყო ჩვენ შემოწმდა მარცხენა ბავშვის ძირეული. როდესაც ჩვენ დააყენა 9 in ხე, გვქონდა წვდომისათვის უფლება ბავშვი root. ჩვენ უნდა აქვს მომცეთ მშობელს, რათა დააყენოს ახალი მნიშვნელობის შევიდა ხე. სენსორული უკან მდე ჩადეთ, რომ არ აპირებს საკმაოდ მუშაობა აქ იმიტომ, რომ ჩვენ არ გვაქვს მშობელი მაჩვენებელი. რა გვინდა გამოუვა არის, ამ ეტაპზე, შეამოწმეთ მშობლის ღირებულება და ვხედავ - ისე, gosh, თუ მშობლის მნიშვნელობა ნაკლებია მიმდინარე ღირებულება, მაშინ მშობლის უფლება ბავშვი უნდა იყოს ახალი კვანძში; წინააღმდეგ შემთხვევაში, მშობლის მარცხენა ბავშვი უნდა იყოს ახალი კვანძში. მაგრამ, ჩვენ არ გვაქვს ამ მშობელს მაჩვენებელი საკმაოდ ამჟამად. 

იმისათვის, რომ მიიღოთ ის, რომ ჩვენ რეალურად აპირებს უნდა აკონტროლოთ, როგორც ჩვენ გაიაროს ხე და იპოვოს შესაბამისი ლაქა ჩვენს loop ზემოთ. ჩვენ შეგვიძლია გავაკეთოთ, რომ სენსორული უკან მდე ზევით ჩვენი ჩანართით ფუნქცია და თვალთვალის სხვა კურსორი ცვლადში მშობელი. ჩვენ სხვებისათვის იგი ტოლია null თავდაპირველად, და შემდეგ ყოველ ჯერზე ჩვენ გაიაროს ხე, ჩვენ სხვებისათვის მშობელი მაჩვენებელი ემთხვევა მიმდინარე მაჩვენებელი. უცნობია მშობლის ტოლი მიმდ.. ეს გზა, ყოველ ჯერზე ჩვენ გაიაროს, ჩვენ ვაპირებთ, რომ უზრუნველყოფილ იქნას როგორც მიმდინარე კურსორი იღებს incremented მშობელი მაჩვენებელი შემდეგნაირად ეს - მხოლოდ ერთი დონის უფრო მაღალია, ვიდრე მიმდინარე წელს მაჩვენებელი ხე. რომ ყველა გამოიყურება საკმაოდ კარგი. 

ვფიქრობ, ერთი რამ, რომ ჩვენ გვინდა შეცვალოს ეს აშენება კვანძის დაბრუნების null. მისაღებად აშენება კვანძის რეალურად წარმატებით დაბრუნებას null, ჩვენ უნდა ცვლილებები, რომ კოდი, რადგან აქ, ჩვენ არასოდეს ტესტირება, რათა დავრწმუნდეთ, რომ malloc დაბრუნდა სწორი მაჩვენებელი. ასე რომ, თუ (N! = NULL), მაშინ - თუ malloc დაბრუნდა სწორი მაჩვენებელი, მაშინ ჩვენ ინიციალიზაცია მას; წინააღმდეგ შემთხვევაში, ჩვენ უბრალოდ დაბრუნდება და რომ დასრულდება მდე დაბრუნების null ჩვენთვის. ახლა ყველა გამოიყურება საკმაოდ კარგი. მოდით დარწმუნდით ამ ფაქტობრივად ადგენს. ჩადება ორობითი ხე, და oh, გვაქვს რაღაცები ხდება აქ. 

გვაქვს დაფარული დეკლარაციის ფუნქციის აშენება კვანძში. ერთხელ, ამ compilers, ჩვენ ვაპირებთ დავიწყოთ ზედა. რა უნდა ნიშნავდეს ის არის, რომ მე მოუწოდებდა აშენება კვანძის ადრე მე რეალურად გამოაცხადა. მოდით დავუბრუნდეთ კოდი მართლაც სწრაფად. Scroll down, და დარწმუნებული საკმარისი, ჩემი ჩანართით ფუნქცია ცხადდება ზემოთ Build კვანძის ფუნქციას, მაგრამ ვცდილობ გამოიყენოთ აშენება კვანძის შიგნით ჩანართით. მე ვაპირებ წავიდეს და ასლი - და შემდეგ ჩასვით Build კვანძის ფუნქციას გზა აქ ზედა. ამ გზით, იმედია იმუშავებს. მოდით მივცეთ ამ მეორე წასვლა. ახლა კი ყველა ადგენს. ყველა კარგია. 

მაგრამ ამ ეტაპზე, ჩვენ არ რეალურად მოუწოდა ჩვენი ჩანართით ფუნქცია. ჩვენ უბრალოდ ვიცით, რომ ეს კომპილაციისას მოდით წავიდეთ და დააყენა რამდენიმე მოუწოდებს სისტემაში მოდით, რომ ჩვენი მთავარი ფუნქცია. აქ, ჩვენ კომენტარს გარეთ 5, 8, და 2, და მაშინ ჩვენ არ WIRE მათ ქვემოთ აქ. მოდით გარკვეული მოუწოდებს ჩასასმელად, და მოდით ასევე გამოიყენოთ იგივე პერსონალი, რომ ჩვენ გამოყენებული როცა ჩვენ მივიღეთ ამ printf მოუწოდებს დავრწმუნდეთ, რომ ყველაფერი ისე მიიღოს ჩასმული სწორად. მე ვაპირებ დააკოპირეთ და ჩასვით, და ნაცვლად შეიცავს ჩვენ ვაპირებთ ჩანართით. და ნაცვლად 6, 10 და 1, ჩვენ ვაპირებთ გამოვიყენოთ 5, 8, და 2. ეს უნდა იმედია ჩადეთ 5, 8, და 2 შევიდა ხე. კომპილირდება. ყველა კარგია. ახლა ჩვენ რეალურად აწარმოებს ჩვენი პროგრამა. 

ყველაფერი დაბრუნდა ყალბი. ასე რომ, 5, 8, და 2 არ წასვლა, და გამოიყურება შეიცავს ვერ მათ არც. რა ხდება? მოდით დააშორებს. პირველი პრობლემა ის იყო, რომ ჩანართით ჩანდა დაბრუნების ცრუ, და როგორც ჩანს ეს იმიტომ, რომ ჩვენ დარჩა ჩვენი დაბრუნების ცრუ ზარი, და ჩვენ არასოდეს რეალურად დაბრუნდა ჭეშმარიტი. ჩვენ შეგვიძლია მითითებული, რომ up. მეორე პრობლემა ისაა, ახლა კი, თუ ჩვენ გავაკეთებთ - შენახვა ამ, დატოვა ეს, აწარმოებს გააკეთოს ერთხელ, არ ის კომპილირება, მაშინ გაუშვით - ჩვენ ვხედავთ, რომ რაღაც მოხდა აქ. 5, 8 და 2 მაინც არასოდეს ნაპოვნი ხე. ასე რომ, რა ხდება? 

მოდით შევხედოთ ამ კოდექსში. მოდით ვნახოთ, თუ შევძლებთ გაერკვნენ ამ გარეთ. ჩვენ დავიწყებთ მშობელს არ ყოფნის null. ჩვენ დავსახეთ მიმდინარე მაჩვენებელი ტოლია root მაჩვენებელი, და ჩვენ ვაპირებთ მუშაობას ჩვენი გზა ქვემოთ მეშვეობით ხე. თუ მიმდინარე კვანძში არ null, მაშინ ჩვენ ვიცით, რომ ჩვენ შეგვიძლია ქვევით ცოტა. ჩვენ დავსახეთ ჩვენი მშობელი მომცეთ თანაბარია მიმდინარე მაჩვენებელი, შემოწმდება ღირებულება - თუ ღირებულებები იგივე დავბრუნდით ყალბი. თუ ღირებულებები ნაკლებად გადავედით უფლება; წინააღმდეგ შემთხვევაში, ჩვენ გადავიდა მარცხენა. მაშინ ჩვენ ავაშენებთ კვანძში. მე დიდი ზომით ცოტა. და აქ, ჩვენ ვაპირებთ ცდილობენ WIRE up ღირებულებების იყოს იგივე. რა ხდება? ვნახოთ, თუ შესაძლოა Valgrind შეუძლია მოგვცეს მინიშნება. 

მომწონს გამოიყენოს Valgrind მხოლოდ იმიტომ Valgrind მართლაც სწრაფად გადის და გიჩვენებთ, თუ არსებობს რაიმე მეხსიერების შეცდომები. როდესაც ჩვენ აწარმოებს Valgrind on კოდი, როგორც ხედავთ უფლება here--Valgrind./binary_tree--and დააჭიროთ. ხედავთ, რომ ჩვენ არ გვაქვს რაიმე მეხსიერების შეცდომა, ასე გამოიყურება ყველაფერი okay ჯერჯერობით. ჩვენ გვაქვს გარკვეული მეხსიერების ტბები, რომელიც ჩვენ ვიცით, იმიტომ, რომ ჩვენ არ ვართ ხდება გასათავისუფლებლად ჩვენს ნებისმიერ კვანძების. მოდით ვეცადოთ გაშვებული GDB რა სინამდვილეში ხდება. ჩვენ ყველაფერს გავაკეთებთ GDB. / Binary_tree. ეს გაიჭედოთ up მხოლოდ ჯარიმა. მოდით მითითებული შესვენების წერტილი ჩანართით. მოდით აწარმოებს. როგორც ჩანს ჩვენ არასოდეს რეალურად მოუწოდა ჩანართით. როგორც ჩანს პრობლემა იყო, რომ როდესაც მე შეიცვალა ქვემოთ აქ მთავარი - ყველა ამ printf ზარები შეიცავს - მე არასოდეს რეალურად შეიცვალა ამ მოვუწოდო ჩანართით. ახლა მოდით გინება. მოდით შეადგინონ. ყველა გამოიყურება კარგი არსებობს. ახლა მოდით შევეცადოთ გაშვებული ის, ვნახოთ, რა მოხდება. კარგად! ყველაფერი გამოიყურება საკმაოდ კარგი არსებობს. 

საბოლოო რამ ფიქრი არის, მოქმედებს თუ არა პირას შემთხვევებში ამ ჩანართით? და აღმოჩნდება, რომ, ისევე, ერთ კიდეზე შემთხვევაში, რომ ყოველთვის საინტერესო ფიქრი არის, რა მოხდება თუ თქვენი ხე არის ცარიელი და რეკავთ ამ ჩანართით ფუნქცია? Will მუშაობს იგი? კარგად, მოდით გინება. - Binary_tree. გ - გზა ჩვენ ვაპირებთ შევამოწმოთ ეს, ჩვენ ვაპირებთ ქვევით ჩვენი მთავარი ფუნქცია, და ვიდრე გაყვანილობა ამ კვანძების up მოსწონს, ჩვენ უბრალოდ აპირებს კომენტარის მთელი რამ, და ნაცვლად გაყვანილობა up კვანძების თავს, ჩვენ შეგვიძლია რეალურად მხოლოდ წავიდეთ წინ და წაშლა ყველა ამ. ჩვენ ვაპირებთ, რათა ყველაფერი ზარის ჩასასმელად. ასე რომ, მოდით - ის ნაცვლად 5, 8, და 2, ჩვენ ვაპირებთ ჩადეთ 7, 3, და 9. და მაშინ საბოლოოდ დავრწმუნდებით ასევე მინდა ჩადეთ 6 ისევე. შენახვა. Quit. ჩადება ორობითი ხე. ყველაფერი ადგენს. ჩვენ შეგვიძლია მხოლოდ აწარმოებს, როგორც არის და ვნახოთ, რა მოხდება, მაგრამ ასევე იქნება მართლაც მნიშვნელოვანია დავრწმუნდეთ, რომ ჩვენ არ გვაქვს რაიმე მეხსიერების შეცდომები, რადგან ეს არის ჩვენი ერთი პირას შემთხვევებში, რომ ვიცით. 

მოდით დარწმუნდით რომ იგი კარგად მუშაობს ქვეშ Valgrind, რომელსაც ჩვენ გავაკეთებთ მხოლოდ გაშვებული Valgrind. / binary_tree. როგორც ჩანს ჩვენ მართლაც გვაქვს ერთი შეცდომა ერთ კონტექსტში - ჩვენ გვაქვს ამ სეგმენტაცია ბრალია. რა მოხდა? Valgrind ფაქტობრივად გვეუბნება, სადაც იგი. დაპატარავება ცოტა. როგორც ჩანს ეს ხდება ჩვენი ჩანართით ფუნქცია, რომელშიც ჩვენ არასწორი წაკითხული of ზომა 4 საათზე ჩანართით, ხაზი 60. მოდით დავუბრუნდეთ და ვნახოთ, რა ხდება აქ. დაპატარავება მართლაც სწრაფი. მე გვინდა დავრწმუნდეთ, რომ არ წასულიყვნენ ზღვარზე ეკრანზე ასე ვხედავთ ყველაფერს. გაიგეთ, რომ ცოტა. კარგად. Scroll down, და პრობლემა ის არის, უფლება აქ. რა მოხდება თუ არ მივიღებთ ქვემოთ და ჩვენი დღევანდელი კვანძის უკვე null, ჩვენი მშობელი კვანძი არის null ასე რომ, თუ გადავხედავთ up at ძალიან დაბრუნება, სწორედ აქ - თუ ეს მაშინ, როცა მარყუჟის არასოდეს რეალურად ახორციელებს რადგან ჩვენი დღევანდელი ღირებულება null - ჩვენი root არის null ისე მიმდ. არის null - მაშინ ჩვენი მშობელი არასოდეს იღებს მითითებული მიმდ. ან სწორი ღირებულება, ამიტომ, მშობელი იქნება null. ჩვენ უნდა გვახსოვდეს, შევამოწმოთ, რომ იმ დროისთვის, მივიღებთ ქვემოთ აქ, და ჩვენ ვიწყებთ წვდომის მშობლის ღირებულება. ასე რომ, რა ხდება? ისე, თუ მშობელი არის null - თუ (მშობელი == NULL) - მაშინ ჩვენ ვიცით, რომ იქ არ უნდა იყოს არაფერი ხე. ჩვენ უნდა ცდილობს ჩადეთ იგი root. ჩვენ შეგვიძლია გავაკეთოთ, რომ მხოლოდ შექმნის root ტოლი ახალი კვანძში. მაშინ ამ ეტაპზე, ჩვენ არ ნამდვილად გინდათ გავლა ამ სხვა რამ. სამაგიეროდ, სწორედ აქ, ჩვენ შეგვიძლია გავაკეთოთ ან სხვაგან თუ-სხვაგან, ან ჩვენ შეგვიძლია დააკავშიროთ ყველაფერი up აქ სხვაგან, მაგრამ აქ ჩვენ მხოლოდ გამოიყენოს სხვაგან და ამის გაკეთება, რომ გზა. ახლა ჩვენ ვაპირებთ შევამოწმოთ რომ დავრწმუნდეთ, რომ ჩვენი მშობელი არ არის null ადრე მაშინ რეალურად ცდილობს წვდომას თავისი სფეროებში. ეს დაგვეხმარება თავიდან ავიცილოთ სეგმენტაცია ბრალია. ასე რომ, ჩვენ დატოვა, zoom out, კომპილაციის, აწარმოებს. 

არარის შეცდომები, მაგრამ ჩვენ ჯერ კიდევ არის რამოდენიმე მეხსიერების გაჟონვის რადგან ჩვენ ვერ გასათავისუფლებლად ჩვენს ნებისმიერ კვანძების. მაგრამ, თუ ჩვენ აქ და შევხედავთ ჩვენი ამონაწერი, ჩვენ ვხედავთ, რომ, ისევე, ჰგავს ყველა ჩვენი ჩანართები ბრუნდებოდა ჭეშმარიტი, რომელიც არის კარგი. ჩანართები ყველა ასეა, და შემდეგ შესაბამისი არსებული მოწოდებით ასევე ჭეშმარიტი. 

კარგ საქმეს! როგორც ჩანს ჩვენ წარმატებით წერილობითი ჩანართით. სულ ეს გვაქვს ამ კვირაში პრობლემა Set სპეციფიკაცია. ერთი fun გამოწვევა ფიქრი არის, როგორ რეალურად წავიდეს და თავისუფალი ყველა კვანძების ამ ხეს. ჩვენ შეგვიძლია ამის გაკეთება რამდენიმე განსხვავებული გზები, მაგრამ დავტოვებთ, რომ თქვენი ექსპერიმენტი, და როგორც fun გამოწვევა, სცადეთ და დარწმუნდით, რომ თქვენ შეგიძლიათ დარწმუნდეთ რომ ეს Valgrind ანგარიში ბრუნდება შეუცდომლობის და არ გაჟონვის. 

წარმატებებს გისურვებთ ამ კვირის Huffman კოდირების პრობლემა კომპლექტი, და ვნახავთ, თქვენ მომავალ კვირას? [CS50.TV]