1 00:00:00,000 --> 00:00:02,770 [Powered by Google Translate] [धारा 7: अधिक आरामदायक] 2 00:00:02,770 --> 00:00:05,090 [रोब Bowden] [हार्वर्ड विश्वविद्यालय] 3 00:00:05,090 --> 00:00:07,930 [यह CS50] [CS50.TV] 4 00:00:07,930 --> 00:00:10,110 सही सभी. तो मैं अपने ईमेल में कहा, 5 00:00:10,110 --> 00:00:14,060 यह करने के लिए एक द्विआधारी पेड़ गहन अनुभाग होने जा रहा है. 6 00:00:14,060 --> 00:00:16,820 लेकिन वहाँ है कि कई सवाल नहीं कर रहे हैं. 7 00:00:16,820 --> 00:00:18,920 इसलिए हम कोशिश करते हैं और प्रत्येक प्रश्न आकर्षित करने के लिए जा रहे हैं 8 00:00:18,920 --> 00:00:25,430 और बातें करने का सर्वोत्तम तरीकों में से दर्दनाक विस्तार में जाना. 9 00:00:25,430 --> 00:00:31,200 तो शुरुआत में ठीक है, हम द्विआधारी पेड़ और सामान के नमूने चित्र के माध्यम से जाना. 10 00:00:31,200 --> 00:00:35,970 तो यहाँ, "याद रखें कि एक द्विआधारी पेड़ एक लिंक सूची के उन लोगों के लिए समान नोड्स है, 11 00:00:35,970 --> 00:00:38,150 बाईं 'बच्चे' के लिए एक: बजाय एक सूचक के अलावा वहाँ दो हैं 12 00:00:38,150 --> 00:00:41,950 और एक सही 'बच्चा' के लिए. " 13 00:00:41,950 --> 00:00:45,630 एक द्विआधारी पेड़ तो एक लिंक्ड सूची की तरह ही है, 14 00:00:45,630 --> 00:00:47,910 struct को छोड़कर दो संकेत जा रहा है. 15 00:00:47,910 --> 00:00:51,390 वहाँ trinary पेड़ है, जो तीन संकेत जा रहे हैं, 16 00:00:51,390 --> 00:00:56,540 N-ary पेड़ है, जो सिर्फ एक सामान्य सूचक है 17 00:00:56,540 --> 00:01:00,320 कि तुम तो malloc के लिए काफी बड़ा करने के लिए किया है 18 00:01:00,320 --> 00:01:04,840 सभी संभव बच्चों को पर्याप्त संकेत. 19 00:01:04,840 --> 00:01:08,200 तो द्विआधारी पेड़ सिर्फ दो की एक निरंतर संख्या है होता है. 20 00:01:08,200 --> 00:01:11,260 यदि आप चाहते हैं, तो आप एक एकल पेड़ के रूप में एक लिंक सूची दे सकते हैं, 21 00:01:11,260 --> 00:01:15,360 लेकिन मुझे नहीं लगता कि किसी को भी यह है कि कॉल. 22 00:01:15,360 --> 00:01:18,060 "एक द्विआधारी पेड़ नोड के एक चित्र बक्से और तीर ड्रा 23 00:01:18,060 --> 00:01:24,110 युक्त नैट पसंदीदा संख्या, 7, जहां प्रत्येक बच्चे सूचक रिक्त है. " 24 00:01:24,110 --> 00:01:27,780 तो iPad मोड. 25 00:01:27,780 --> 00:01:30,280 >> यह बहुत सीधा होने जा रहा है. 26 00:01:30,280 --> 00:01:36,150 हम सिर्फ एक नोड के लिए जा रहे हैं, मैं इसे एक वर्ग के रूप में आकर्षित करेंगे. 27 00:01:36,150 --> 00:01:38,730 और मैं यहाँ में मूल्यों को आकर्षित करेंगे. 28 00:01:38,730 --> 00:01:41,090 तो मान में जाना होगा, 29 00:01:41,090 --> 00:01:44,770 और फिर नीचे यहाँ हम बाईं तरफ बाईं सूचक और सही पर सही सूचक होगा. 30 00:01:44,770 --> 00:01:50,430 और यह बहुत सम्मेलन तो यह बाएँ और दाएँ, सूचक नाम कॉल करने के लिए. 31 00:01:50,430 --> 00:01:52,460 इन दोनों के लिए अशक्त होने जा रहे हैं. 32 00:01:52,460 --> 00:01:57,870 वह सिर्फ रिक्त हो जाएगा, और कहा कि अभी रिक्त हो जाएगा. 33 00:01:57,870 --> 00:02:03,630 ठीक है. तो यहाँ वापस करने के लिए. 34 00:02:03,630 --> 00:02:05,700 "एक लिंक की गई सूची के साथ, हम केवल एक सूचक की दुकान थी 35 00:02:05,700 --> 00:02:09,639 सूची क्रम में पूरे लिंक की गई सूची को याद करने के लिए, या पूरी सूची में पहला नोड. 36 00:02:09,639 --> 00:02:11,650 इसी तरह, पेड़ के साथ, हम केवल एक सूचक की दुकान है 37 00:02:11,650 --> 00:02:13,420 क्रम में पूरे पेड़ को याद करने के लिए एक एकल नोड. 38 00:02:13,420 --> 00:02:15,980 इस नोड calle पेड़ की जड़ 'है. 39 00:02:15,980 --> 00:02:18,320 पहले से अपने चित्र पर निर्माण या एक नया आकर्षित 40 00:02:18,320 --> 00:02:21,690 ऐसी है कि आप एक द्विआधारी पेड़ बक्से और तीर का चित्रण है 41 00:02:21,690 --> 00:02:25,730 साथ 7 मूल्य, फिर छोड़ दिया में 3, 42 00:02:25,730 --> 00:02:32,760 तो सही पर 9, और फिर 6 3 की दाईं तरफ है. " 43 00:02:32,760 --> 00:02:34,810 चलो देखते हैं अगर मैं मेरे सिर में है कि सभी को याद कर सकते हैं. 44 00:02:34,810 --> 00:02:37,670 तो यह हमारे यहाँ जड़ होने जा रहा है. 45 00:02:37,670 --> 00:02:41,600 हम कुछ सूचक कहीं होगा, कुछ है कि हम जड़ फोन करता हूँ, 46 00:02:41,600 --> 00:02:45,140 और यह इस आदमी की ओर इशारा करते है. 47 00:02:45,140 --> 00:02:48,490 अब एक नया नोड बनाने के लिए, 48 00:02:48,490 --> 00:02:52,870 हम क्या है 3 बाईं तरफ? 49 00:02:52,870 --> 00:02:57,140 तो 3 के साथ एक नया नोड, और यह शुरू में अशक्त अंक. 50 00:02:57,140 --> 00:02:59,190 मैं सिर्फ एन डाल देता हूँ 51 00:02:59,190 --> 00:03:02,250 अब हम कि 7 की बाईं करने के लिए जाना चाहते हैं. 52 00:03:02,250 --> 00:03:06,840 इसलिए हम इस सूचक को बदलने के लिए अब इस आदमी के लिए बात. 53 00:03:06,840 --> 00:03:12,420 और हम भी ऐसा ही. हम यहाँ पर 9 54 00:03:12,420 --> 00:03:14,620 जो शुरू में सिर्फ रिक्त कहते हैं. 55 00:03:14,620 --> 00:03:19,600 हम 9 से इस बिंदु, सूचक बदलने के लिए जा रहे हैं, 56 00:03:19,600 --> 00:03:23,310 और अब हम सही करने के लिए 3 के 6 डाल करना चाहते हैं. 57 00:03:23,310 --> 00:03:32,170 तो यह जा रहा है - एक 6. 58 00:03:32,170 --> 00:03:34,310 और उस आदमी को बात करेंगे. 59 00:03:34,310 --> 00:03:38,320 ठीक है. तो यह है कि यह हमारे करने के लिए पूछता है. 60 00:03:38,320 --> 00:03:42,770 >> अब चलो कुछ शब्दावली पर जाना. 61 00:03:42,770 --> 00:03:46,690 हम पहले से ही कैसे पेड़ की जड़ वृक्ष के नोड सर्वोच्च है के बारे में बात की थी. 62 00:03:46,690 --> 00:03:54,720 एक 7 युक्त. पेड़ के नीचे नोड्स पत्तियों कहा जाता है. 63 00:03:54,720 --> 00:04:01,240 किसी भी नोड है जो सिर्फ अपने बच्चों के रूप में अशक्त है एक पत्ता है. 64 00:04:01,240 --> 00:04:03,680 तो यह संभव है, अगर हमारे द्विआधारी पेड़ सिर्फ एक नोड है, 65 00:04:03,680 --> 00:04:10,130 कि एक पेड़ के एक पत्ता है, और यह बात है. 66 00:04:10,130 --> 00:04:12,060 "पेड़ की 'ऊंचाई' hops आपको करना है की संख्या है 67 00:04:12,060 --> 00:04:16,620 ऊपर से एक पत्ती को मिलता है. " 68 00:04:16,620 --> 00:04:18,640 हम में मिलता है, एक दूसरे में, अंतर 69 00:04:18,640 --> 00:04:21,940 संतुलित और असंतुलित द्विआधारी पेड़ों के बीच, 70 00:04:21,940 --> 00:04:29,470 लेकिन अब के लिए, इस पेड़ की कुल ऊंचाई 71 00:04:29,470 --> 00:04:34,520 मैं 3 कहते हैं, हालांकि, अगर आप hops की संख्या गिनती 72 00:04:34,520 --> 00:04:39,710 आप क्रम में 9 से मिलता है, तो यह वास्तव में केवल 2 की ऊंचाई है. 73 00:04:39,710 --> 00:04:43,340 अभी यह एक असंतुलित द्विआधारी पेड़ है, 74 00:04:43,340 --> 00:04:49,840 लेकिन हम संतुलित के बारे में बात की थी जब यह प्रासंगिक हो जाता है. 75 00:04:49,840 --> 00:04:52,040 तो अब हम इस मामले में एक पेड़ में नोड्स के बारे में बात कर सकते हैं 76 00:04:52,040 --> 00:04:54,700 पेड़ में अन्य नोड्स के सापेक्ष. 77 00:04:54,700 --> 00:04:59,730 तो अब हम माता पिता, बच्चों, भाई बहन, पूर्वजों और वंश है. 78 00:04:59,730 --> 00:05:05,650 वे बहुत आम समझ रहे हैं, वे क्या मतलब है. 79 00:05:05,650 --> 00:05:09,610 यह माता - पिता यदि हम पूछना. 80 00:05:09,610 --> 00:05:12,830 तो 3 के माता - पिता क्या है? 81 00:05:12,830 --> 00:05:16,090 7 [छात्र]. >> हाँ. माता - पिता हो सकता है क्या आप के लिए अंक जा रहा है. 82 00:05:16,090 --> 00:05:20,510 फिर 7 के बच्चों को क्या कर रहे हैं? 83 00:05:20,510 --> 00:05:23,860 3 और 9 [छात्र]. >> हाँ. 84 00:05:23,860 --> 00:05:26,460 सूचना है कि "बच्चों" सचमुच बच्चों का मतलब, 85 00:05:26,460 --> 00:05:31,010 6 तो लागू नहीं है, क्योंकि यह एक पोता की तरह होता है. 86 00:05:31,010 --> 00:05:35,540 लेकिन फिर अगर हम वंश जाओ, तो 7 की सन्तान क्या कर रहे हैं? 87 00:05:35,540 --> 00:05:37,500 3, 6 और 9 [छात्र]. >> हाँ. 88 00:05:37,500 --> 00:05:42,330 रूट नोड की सन्तान पेड़ में सब कुछ होने जा रहा है, 89 00:05:42,330 --> 00:05:47,950 सिवाय शायद रूट नोड ही, यदि आप करने के लिए कि एक वंशज पर विचार नहीं करना चाहती. 90 00:05:47,950 --> 00:05:50,750 और अंत में, पूर्वजों, तो यह विपरीत दिशा है. 91 00:05:50,750 --> 00:05:55,740 तो 6 के पूर्वजों क्या कर रहे हैं? 92 00:05:55,740 --> 00:05:58,920 3 और 7 [छात्र]. >> हाँ. 9 शामिल नहीं है. 93 00:05:58,920 --> 00:06:02,520 यह सिर्फ प्रत्यक्ष वंश रूट करने के लिए वापस आ गया है 94 00:06:02,520 --> 00:06:13,230 अपने पूर्वजों की जा रही है. 95 00:06:13,230 --> 00:06:16,300 >> "हम कहते हैं कि एक द्विआधारी पेड़ पेड़ में प्रत्येक नोड के लिए अगर 'का आदेश दिया' 96 00:06:16,300 --> 00:06:19,530 बाईं तरफ उसके वंश के सभी कम मूल्यों है 97 00:06:19,530 --> 00:06:22,890 और सही पर लोगों की अधिक से अधिक मूल्यों है. 98 00:06:22,890 --> 00:06:27,060 उदाहरण के लिए, ऊपर पेड़ का आदेश दिया है, लेकिन यह तभी संभव आदेश दिया व्यवस्था नहीं है. " 99 00:06:27,060 --> 00:06:30,180 इससे पहले कि हम करने के लिए मिलता है, 100 00:06:30,180 --> 00:06:36,420 एक आदेश द्विआधारी पेड़ एक द्विआधारी खोज वृक्ष के रूप में भी जाना जाता है. 101 00:06:36,420 --> 00:06:38,660 यहाँ हम इसे एक आदेश द्विआधारी पेड़ बुला रहे हो, 102 00:06:38,660 --> 00:06:41,850 लेकिन मैं कभी नहीं सुना है यह एक आदेश द्विआधारी पेड़ से पहले कहा जाता है, 103 00:06:41,850 --> 00:06:46,650 और एक प्रश्नोत्तरी पर हम और अधिक के लिए द्विआधारी खोज वृक्ष डाल की संभावना हैं. 104 00:06:46,650 --> 00:06:49,250 वे एक और एक ही कर रहे हैं, 105 00:06:49,250 --> 00:06:54,580 और यह महत्वपूर्ण है कि आप द्विआधारी पेड़ और द्विआधारी खोज वृक्ष के बीच अंतर को समझते हैं. 106 00:06:54,580 --> 00:06:58,830 एक द्विआधारी पेड़ सिर्फ एक पेड़ है कि दो चीजों के लिए अंक. 107 00:06:58,830 --> 00:07:02,120 प्रत्येक नोड दो बातें करने के लिए कहते हैं. 108 00:07:02,120 --> 00:07:06,310 मूल्यों के बारे में कोई तर्क है कि यह करने के लिए अंक है. 109 00:07:06,310 --> 00:07:11,370 तो यहाँ पर करना चाहते हैं, क्योंकि यह एक द्विआधारी खोज वृक्ष है, 110 00:07:11,370 --> 00:07:14,030 हम जानते हैं कि अगर हम जाओ 7 के छोड़ दिया है, 111 00:07:14,030 --> 00:07:16,670 तो सभी मूल्यों है कि हम संभवतः तक पहुँच सकते हैं 112 00:07:16,670 --> 00:07:19,310 7 के छोड़ दिया जा रहा द्वारा 7 से कम हो. 113 00:07:19,310 --> 00:07:24,070 सूचना है कि 7 से कम सभी मान 3 और 6. 114 00:07:24,070 --> 00:07:26,040 उन 7 की बाईं सभी कर रहे हैं. 115 00:07:26,040 --> 00:07:29,020 अगर हम सही करने के लिए 7 के जाओ, सब कुछ करने के लिए 7 से अधिक हो गया है, 116 00:07:29,020 --> 00:07:33,220 इतना 9 7 के अधिकार के लिए है, तो हम अच्छा कर रहे हैं. 117 00:07:33,220 --> 00:07:36,150 यह एक द्विआधारी पेड़ के लिए मामला नहीं है, 118 00:07:36,150 --> 00:07:40,020 एक नियमित द्विआधारी पेड़ के लिए हम सिर्फ ऊपर, बाईं करने के लिए 7 पर 3 हो सकता है, 119 00:07:40,020 --> 00:07:47,630 9 7 की बाईं, वहाँ कोई नहीं है जो मूल्यों के आदेश है. 120 00:07:47,630 --> 00:07:56,140 अब, हम वास्तव में यह नहीं करना है क्योंकि यह थकाऊ और अनावश्यक है, 121 00:07:56,140 --> 00:07:59,400 लेकिन "के रूप में कई आदेश दिया के पेड़ के रूप में आप के बारे में सोच सकते हैं आकर्षित करने की कोशिश 122 00:07:59,400 --> 00:08:01,900 संख्या 7, 3, 9 का उपयोग कर, और 6. 123 00:08:01,900 --> 00:08:06,800 कितने अलग व्यवस्था कर रहे हैं? हर एक की ऊंचाई क्या है? " 124 00:08:06,800 --> 00:08:10,480 >> हम कुछ करेंगे, लेकिन मुख्य विचार है, 125 00:08:10,480 --> 00:08:16,530 यह एक द्विआधारी पेड़ के इन मूल्यों से युक्त एक अद्वितीय प्रतिनिधित्व कोई रास्ता नहीं में है. 126 00:08:16,530 --> 00:08:22,760 हम सब की ज़रूरत है कुछ द्विआधारी पेड़ है कि 7 शामिल हैं, 3, 6, और 9 है. 127 00:08:22,760 --> 00:08:25,960 एक अन्य संभावित वैध एक रूट 3 होगा, 128 00:08:25,960 --> 00:08:30,260 बाईं करने के लिए जाना है और यह 6 है, छोड़ दिया करने के लिए जाना है और यह 7 है, 129 00:08:30,260 --> 00:08:32,730 बाईं करने के लिए जाना है और यह 9 है. 130 00:08:32,730 --> 00:08:36,169 यह एक पूरी तरह से वैध द्विआधारी खोज वृक्ष है. 131 00:08:36,169 --> 00:08:39,570 यह बहुत उपयोगी नहीं है, क्योंकि यह सिर्फ एक लिंक सूची की तरह है 132 00:08:39,570 --> 00:08:43,750 और ये संकेत के सभी रिक्त हैं. 133 00:08:43,750 --> 00:08:48,900 लेकिन यह एक वैध पेड़ है. हाँ? 134 00:08:48,900 --> 00:08:51,310 [छात्र] मूल्यों सही पर अधिक होना नहीं है क्या? 135 00:08:51,310 --> 00:08:56,700 या यह है? >> ये मैं दूसरे रास्ते जाने का मतलब है. 136 00:08:56,700 --> 00:09:00,960 वहाँ भी है - हाँ, है कि स्विच. 137 00:09:00,960 --> 00:09:07,770 9, 7, 6, 3. अच्छी पकड़. 138 00:09:07,770 --> 00:09:11,730 यह अभी भी पालन करने के लिए क्या एक द्विआधारी पेड़ खोज करना चाहिए है. 139 00:09:11,730 --> 00:09:15,650 तो छोड़ दिया करने के लिए सब कुछ करने के लिए किसी भी नोड की तुलना में कम हो गया है. 140 00:09:15,650 --> 00:09:23,180 हम बस ले जाने के लिए, कह सकते हैं, यह 6 और इसे यहाँ रखा. 141 00:09:23,180 --> 00:09:26,880 नहीं, हम नहीं कर सकते. मैं कर रही है कि क्यों रहते हो? 142 00:09:26,880 --> 00:09:35,350 चलो करते हैं - यहाँ 6 है, यहाँ 7 है, 3 से 6 अंक है. 143 00:09:35,350 --> 00:09:39,290 यह अभी भी एक वैध द्विआधारी खोज वृक्ष है. 144 00:09:39,290 --> 00:09:49,260 क्या गलत है अगर मैं - चलो देखते हैं अगर मैं एक व्यवस्था के साथ आ सकते हैं. 145 00:09:49,260 --> 00:09:52,280 हाँ, ठीक है. तो इस पेड़ के साथ क्या गलत है? 146 00:09:52,280 --> 00:10:08,920 मुझे लगता है कि मैं पहले से ही आप एक संकेत दिया है कि वहाँ के साथ कुछ गड़बड़ है. 147 00:10:08,920 --> 00:10:14,430 मैं कर रही है कि क्यों रहते हो? 148 00:10:14,430 --> 00:10:18,510 ठीक है. यह उचित लग रहा है. 149 00:10:18,510 --> 00:10:22,590 यदि हम प्रत्येक नोड में, 7 की तरह है, तो 7 की बाईं देखो एक 3 है. 150 00:10:22,590 --> 00:10:24,960 तो हम 3 है, सही करने के लिए 3 की बात एक 6 है. 151 00:10:24,960 --> 00:10:27,750 और अगर आप 6 पर देखो, बात सही करने के लिए 6 की 9. 152 00:10:27,750 --> 00:10:30,910 तो यह एक वैध द्विआधारी खोज वृक्ष क्यों नहीं है? 153 00:10:30,910 --> 00:10:36,330 9 [छात्र] 7 की बाईं करने के लिए अभी भी है. >> हाँ. 154 00:10:36,330 --> 00:10:43,710 यह सच है कि सभी मूल्यों आप संभवतः 7 की बाईं करने के लिए जा रहा द्वारा पहुँच सकते हैं कम से कम 7 होना चाहिए. 155 00:10:43,710 --> 00:10:49,120 अगर हम 7 के छोड़ दिया जाना, हम 3 से मिलता है और हम अभी भी 6 से प्राप्त कर सकते हैं, 156 00:10:49,120 --> 00:10:52,520 हम अभी भी 9 से मिल सकता है, लेकिन कम से कम 7 चला गया, 157 00:10:52,520 --> 00:10:55,070 हम एक नंबर है कि 7 से अधिक प्राप्त करने में सक्षम नहीं होना चाहिए. 158 00:10:55,070 --> 00:10:59,830 तो यह एक वैध द्विआधारी खोज वृक्ष नहीं है. 159 00:10:59,830 --> 00:11:02,330 >> मेरा भाई वास्तव में एक साक्षात्कार सवाल था 160 00:11:02,330 --> 00:11:07,760 है कि मूल रूप से कुछ करने के लिए मान्य को इस बस कोड था 161 00:11:07,760 --> 00:11:10,500 क्या एक पेड़ एक द्विआधारी खोज वृक्ष है, 162 00:11:10,500 --> 00:11:13,580 और इसलिए पहली बात यह है कि वह सिर्फ देखने के लिए जाँच 163 00:11:13,580 --> 00:11:17,020 अगर छोड़ दिया और सही सही हैं, और फिर वहाँ नीचे पुनरावृति. 164 00:11:17,020 --> 00:11:19,700 लेकिन सिर्फ तुम नहीं कर सकते हैं कि करना, आप ट्रैक रखने के लिए है 165 00:11:19,700 --> 00:11:22,550 तथ्य यह है कि अब मैं 7 के छोड़ दिया गया है, 166 00:11:22,550 --> 00:11:26,340 यह subtree में सब कुछ 7 से कम होना चाहिए. 167 00:11:26,340 --> 00:11:28,430 सही एल्गोरिथ्म ट्रैक रखने की जरूरत है, 168 00:11:28,430 --> 00:11:35,970 सीमा है कि मूल्यों को संभवतः अंदर गिर सकता है 169 00:11:35,970 --> 00:11:38,360 हम उन सभी के माध्यम से नहीं जाऊँगा. 170 00:11:38,360 --> 00:11:41,630 वहाँ एक अच्छा पुनरावृत्ति संबंध है, 171 00:11:41,630 --> 00:11:44,810 हालांकि हम उन लोगों के लिए नहीं मिल गया है, या हम उन लोगों के लिए नहीं मिलेगा, 172 00:11:44,810 --> 00:11:47,030 परिभाषित कितने वहाँ वास्तव में कर रहे हैं. 173 00:11:47,030 --> 00:11:53,180 तो वहाँ 14 उनमें से एक हैं. 174 00:11:53,180 --> 00:11:56,020 आप इसे कैसे करना होगा विचार गणितीय की तरह है, 175 00:11:56,020 --> 00:11:59,770 आप किसी भी एक को लेने के लिए रूट नोड हो सकता है, 176 00:11:59,770 --> 00:12:03,160 और फिर अगर मैं 7 लेने के लिए रूट नोड हो, 177 00:12:03,160 --> 00:12:08,150 तो वहाँ कुछ कर रहे हैं, कहते हैं, संख्या कि मेरे बाएँ नोड होना जा सकते हैं, 178 00:12:08,150 --> 00:12:10,440 और वहाँ कुछ संख्या है कि मेरा अधिकार नोड हो सकता है, 179 00:12:10,440 --> 00:12:15,090 लेकिन अगर मैं कुल संख्या n है, तो राशि है कि बाईं करने के लिए जा सकते हैं 180 00:12:15,090 --> 00:12:18,820 1 - प्लस राशि है कि सही करने के लिए जा सकते हैं n है. 181 00:12:18,820 --> 00:12:26,130 तो शेष संख्या, वे या तो छोड़ दिया है या सही करने के लिए जाने के लिए सक्षम होना चाहिए. 182 00:12:26,130 --> 00:12:31,580 यह मुश्किल लगता है कि, अगर मैं 3 1 तो डाल सब कुछ करने के लिए छोड़ दिया करने के लिए जाना पड़ता है, 183 00:12:31,580 --> 00:12:35,080 लेकिन अगर मैं 7 डाल, तो कुछ बातों को छोड़ दिया जाना है और कुछ चीजों को सही करने के लिए जा सकते हैं कर सकते हैं. 184 00:12:35,080 --> 00:12:39,570 और मैं '3 1 'से मतलब है, सब कुछ ठीक करने के लिए जा सकते हैं. 185 00:12:39,570 --> 00:12:42,350 यह सच है, तो आप सिर्फ इसके बारे में सोचना है, 186 00:12:42,350 --> 00:12:47,980 कितनी बातें पेड़ के अगले स्तर पर जा सकते हैं. 187 00:12:47,980 --> 00:12:50,420 और यह पता करने के लिए आता है 14 हो, या आप उन सभी को आकर्षित कर सकते हैं, 188 00:12:50,420 --> 00:12:54,650 और फिर आप 14 मिलेगा. 189 00:12:54,650 --> 00:13:01,120 >> यहाँ वापस जा रहे हैं, 190 00:13:01,120 --> 00:13:03,510 "आदेश दिया द्विआधारी पेड़ शांत कर रहे हैं क्योंकि हम उन के माध्यम से खोज कर सकते हैं 191 00:13:03,510 --> 00:13:06,910 एक हल सरणी पर खोज करने के लिए एक बहुत ही रास्ते में. 192 00:13:06,910 --> 00:13:10,120 ऐसा करने के लिए, हम रूट पर शुरू करने के लिए और पेड़ के नीचे हमारे रास्ते काम 193 00:13:10,120 --> 00:13:13,440 पत्तियों की ओर, मानों हम के लिए खोज रहे हैं के खिलाफ प्रत्येक नोड मूल्यों की जाँच. 194 00:13:13,440 --> 00:13:15,810 यदि वर्तमान नोड मूल्य मूल्य से कम है कि हम देख रहे हैं, 195 00:13:15,810 --> 00:13:18,050 आप नोड सही बच्चे को बगल जाना. 196 00:13:18,050 --> 00:13:20,030 अन्यथा, आप नोड छोड़ दिया बच्चे को जाना. 197 00:13:20,030 --> 00:13:22,800 कुछ बिंदु पर, आप या तो आप के लिए देख रहे हैं मूल्य मिल जाए, या आप एक अशक्त में भाग लेंगे 198 00:13:22,800 --> 00:13:28,520 मूल्य संकेत पेड़ में नहीं है. " 199 00:13:28,520 --> 00:13:32,450 मैं पेड़ हम पहले था redraw है, कि एक मिनट लगेगा. 200 00:13:32,450 --> 00:13:38,280 लेकिन हम को देखने के लिए कि क्या 6, 10, और 1 पेड़ में करना चाहते हैं. 201 00:13:38,280 --> 00:13:49,180 तो यह क्या था, 7, 9, 3, 6. ठीक है. 202 00:13:49,180 --> 00:13:52,730 नंबर आप को देखने के लिए करना चाहते हैं, हम करने के लिए 6 देखना चाहता हूँ. 203 00:13:52,730 --> 00:13:55,440 कैसे इस एल्गोरिथ्म काम करता है? 204 00:13:55,440 --> 00:14:03,040 खैर, हम भी कुछ हमारे पेड़ को जड़ सूचक है. 205 00:14:03,040 --> 00:14:12,460 और हम रूट करने के लिए जाना और कहते हैं, इस मूल्य हम के लिए खोज कर रहे हैं बराबर मूल्य है? 206 00:14:12,460 --> 00:14:15,000 तो हम 6 के लिए देख रहे हैं, तो यह नहीं के बराबर है. 207 00:14:15,000 --> 00:14:20,140 तो हम जा रखने के लिए, और अब हम कह, ठीक है, तो 6 कम से कम 7 है. 208 00:14:20,140 --> 00:14:23,940 क्या इसका मतलब हम छोड़ दिया करने के लिए जाना चाहते हैं, या क्या हम सही करने के लिए जाना चाहते हैं? 209 00:14:23,940 --> 00:14:27,340 [छात्र] वाम. >> हाँ. 210 00:14:27,340 --> 00:14:33,340 यह काफी आसान है, सब तुम्हें क्या करना है एक पेड़ के संभव नोड आकर्षित करने के लिए है 211 00:14:33,340 --> 00:14:37,760 और फिर तुम नहींं - के बजाय अपने सिर में सोचने की कोशिश कर रहा है, 212 00:14:37,760 --> 00:14:40,020 ठीक है, अगर यह कम है, मैं छोड़ दिया करने के लिए जाना है या ठीक है, जाओ 213 00:14:40,020 --> 00:14:43,030 सिर्फ इस तस्वीर को देख रहे हैं, यह बहुत स्पष्ट है कि मैं करने के लिए छोड़ दिया जाना है 214 00:14:43,030 --> 00:14:47,700 अगर इस नोड मूल्य है कि मैं देख रहा हूँ से अधिक है. 215 00:14:47,700 --> 00:14:52,600 तो तुम छोड़ दिया करने के लिए जाना है, अब मैं 3 पर हूँ. 216 00:14:52,600 --> 00:14:57,770 मैं चाहता हूँ - 3 मूल्य के लिए मैं देख रहा हूँ, जो 6 है की तुलना में कम है. 217 00:14:57,770 --> 00:15:03,420 तो हम जाने के लिए सही है, और अब मैं 6 पर खत्म होता है, 218 00:15:03,420 --> 00:15:07,380 जो मूल्य के लिए मैं देख रहा हूँ, तो मैं वापसी सच है. 219 00:15:07,380 --> 00:15:15,760 मैं अगले मूल्य को देखने के लिए जा रहा हूँ 10 है. 220 00:15:15,760 --> 00:15:23,230 ठीक है. 10 तो काट दिया है कि - जड़ का पालन करने के लिए जा, अब, के लिए जा रहा है. 221 00:15:23,230 --> 00:15:27,670 अब 10, 7 से अधिक होने जा रहा है, तो मैं सही करने के लिए देखना चाहता हूँ. 222 00:15:27,670 --> 00:15:31,660 मैं यहाँ आने के लिए जा रहा हूँ 10, 9 से अधिक होने जा रहा है, 223 00:15:31,660 --> 00:15:34,520 तो मैं करने के लिए सही करने के लिए देखना चाहता हूँ जा रहा हूँ. 224 00:15:34,520 --> 00:15:42,100 मैं यहाँ आते हैं, लेकिन अब यहाँ पर मैं अशक्त पर हूँ. 225 00:15:42,100 --> 00:15:44,170 मैं क्या अगर मैं अशक्त मारा करते हो? 226 00:15:44,170 --> 00:15:47,440 [छात्र] झूठी वापसी? >> हाँ. मैं 10 नहीं मिला. 227 00:15:47,440 --> 00:15:49,800 1 के लिए लगभग समान मामला होने जा रहा है, 228 00:15:49,800 --> 00:15:51,950 सिवाय इसके कि यह सिर्फ फ़्लिप किया जा जा रहा है, के बजाय देख 229 00:15:51,950 --> 00:15:56,540 सही पक्ष नीचे, मैं नीचे बाईं ओर देखने के लिए जा रहा हूँ. 230 00:15:56,540 --> 00:16:00,430 >> अब मुझे लगता है कि हम वास्तव में कोड करने के लिए मिलता है. 231 00:16:00,430 --> 00:16:04,070 यहाँ है जहाँ - CS50 उपकरण खोलने के लिए और अपना रास्ता नेविगेट, 232 00:16:04,070 --> 00:16:07,010 लेकिन आप भी अंतरिक्ष में यह सिर्फ कर सकते हैं. 233 00:16:07,010 --> 00:16:09,170 यह शायद यह अंतरिक्ष में क्या करने के लिए आदर्श है, 234 00:16:09,170 --> 00:16:13,760 क्योंकि हम अंतरिक्ष में काम कर सकते हैं. 235 00:16:13,760 --> 00:16:19,170 "सबसे पहले हम एक द्विआधारी पेड़ नोड int मूल्यों से युक्त करने के लिए एक नए प्रकार परिभाषा की आवश्यकता होगी. 236 00:16:19,170 --> 00:16:21,400 नीचे typedef बॉयलरप्लेट का प्रयोग, 237 00:16:21,400 --> 00:16:24,510 एक द्विआधारी पेड़ में एक नोड के लिए एक नए प्रकार परिभाषा बनाने के लिए. 238 00:16:24,510 --> 00:16:27,930 यदि आप अटक जाते हैं. . . "ब्ला ब्ला ब्ला, ठीक है. 239 00:16:27,930 --> 00:16:30,380 तो चलो boilerplate यहाँ डाल, 240 00:16:30,380 --> 00:16:41,630 typedef struct नोड, और नोड. हाँ, ठीक है. 241 00:16:41,630 --> 00:16:44,270 तो खेतों हम हमारे नोड में चाहते करने के लिए जा रहे हैं क्या कर रहे हैं? 242 00:16:44,270 --> 00:16:46,520 [छात्र] Int और फिर दो संकेत? 243 00:16:46,520 --> 00:16:49,700 >> Int मूल्य, दो संकेत? मैं संकेत कैसे लिख सकता हूँ? 244 00:16:49,700 --> 00:16:58,440 [छात्र] Struct. >> मैं अंदर ज़ूम हाँ, तो struct नोड छोड़ * 245 00:16:58,440 --> 00:17:01,320 और संरचना नोड सही *. 246 00:17:01,320 --> 00:17:03,460 और पिछली बार से चर्चा याद है, 247 00:17:03,460 --> 00:17:15,290 कि यह नहीं समझ में आता है, यह नहीं समझ में आता है, 248 00:17:15,290 --> 00:17:18,270 यह नहीं समझ में आता. 249 00:17:18,270 --> 00:17:25,000 तुम वहाँ सब कुछ की जरूरत है ताकि इस पुनरावर्ती struct को परिभाषित. 250 00:17:25,000 --> 00:17:27,970 ठीक है, ताकि हमारे पेड़ की तरह लग रहा है. 251 00:17:27,970 --> 00:17:37,670 यदि हम एक trinary पेड़ किया, तो एक नोड B1, B2, संरचना नोड b3 * की तरह लग सकता है, 252 00:17:37,670 --> 00:17:43,470 जहां ख एक शाखा है - वास्तव में, मैं और अधिक सुना है इसे छोड़ दिया, मध्यम, सही है, लेकिन जो कुछ भी. 253 00:17:43,470 --> 00:17:55,610 हम केवल द्विआधारी के बारे में परवाह है, तो ठीक है, छोड़ दिया. 254 00:17:55,610 --> 00:17:59,110 "अब पेड़ की जड़ के लिए एक वैश्विक नोड * चर घोषित कर दिया." 255 00:17:59,110 --> 00:18:01,510 तो हम ऐसा करने के लिए नहीं जा रहे हैं. 256 00:18:01,510 --> 00:18:08,950 आदेश में चीजों को थोड़ा और अधिक कठिन और अधिक सामान्यकृत बनाने के लिए, 257 00:18:08,950 --> 00:18:11,570 हम एक वैश्विक नोड चर नहीं होगा. 258 00:18:11,570 --> 00:18:16,710 इसके बजाय, मुख्य में हम हमारे सभी नोड बातें की घोषणा करेंगे, 259 00:18:16,710 --> 00:18:20,500 और वह है कि नीचे का मतलब है, जब हम चल रहे शुरू 260 00:18:20,500 --> 00:18:23,130 हमारे शामिल हैं समारोह और हमारे डालने समारोह, 261 00:18:23,130 --> 00:18:27,410 हमारे होता है की बजाय सिर्फ इस वैश्विक नोड चर का उपयोग कर समारोह, 262 00:18:27,410 --> 00:18:34,280 हम यह एक तर्क के रूप में पेड़ ले जा रहे हैं कि हम यह प्रक्रिया करने के लिए करना चाहते हैं. 263 00:18:34,280 --> 00:18:36,650 वैश्विक चर के बाद चीजों को आसान बनाने के लिए चाहिए था. 264 00:18:36,650 --> 00:18:42,310 हम चीजों को कठिन बनाने के लिए जा रहे हैं. 265 00:18:42,310 --> 00:18:51,210 अब या तो एक मिनट के लेने के लिए इस तरह की बात करने के लिए बस, 266 00:18:51,210 --> 00:18:57,690 जहां अंदर मुख्य आप इस पेड़ बनाने चाहते हैं, और कि आप सब करना चाहते हैं. 267 00:18:57,690 --> 00:19:04,530 कोशिश करते हैं और अपने मुख्य समारोह में इस पेड़ का निर्माण. 268 00:19:42,760 --> 00:19:47,610 >> ठीक है. तो तुम भी पेड़ पूरी तरह से निर्माण किया है अभी तक नहीं है. 269 00:19:47,610 --> 00:19:49,840 लेकिन किसी को भी कुछ मैं खींच सकता है 270 00:19:49,840 --> 00:20:03,130 दिखाने के लिए कैसे एक इस तरह के एक पेड़ के निर्माण शुरू हो सकता है? 271 00:20:03,130 --> 00:20:08,080 [छात्र] किसी की पिटाई, बाहर निकलने की कोशिश. 272 00:20:08,080 --> 00:20:13,100 [Bowden] अपने पेड़ के निर्माण के साथ सहज कोई है? 273 00:20:13,100 --> 00:20:15,520 [छात्र] ज़रूर. यह नहीं किया है. >> यह ठीक है. हम बस खत्म कर सकते हैं - 274 00:20:15,520 --> 00:20:26,860 ओह, आप इसे बचा सकते हैं? हुर्रे. 275 00:20:26,860 --> 00:20:32,020 यहाँ तो हम है - ओह, मैं थोड़ा दूर काट रहा हूँ. 276 00:20:32,020 --> 00:20:34,770 मैं कर रहा हूँ में तेजी से बढ़ी है? 277 00:20:34,770 --> 00:20:37,730 में ज़ूम, स्क्रॉल. >> मैं एक सवाल है. >> हाँ? 278 00:20:37,730 --> 00:20:44,410 [छात्र] जब आप struct को परिभाषित, initialized की तरह कुछ भी करने के लिए बातें कर रहे हैं? 279 00:20:44,410 --> 00:20:47,160 [Bowden] नहीं >> ठीक है. तो आप इनिशियलाइज़ करना होगा - 280 00:20:47,160 --> 00:20:50,450 [Bowden] नहीं, जब आप को परिभाषित करने के लिए, या जब आप की घोषणा एक struct 281 00:20:50,450 --> 00:20:55,600 यह डिफ़ॉल्ट रूप से प्रारंभ नहीं किया है, यह सिर्फ अगर तुम एक int घोषित करना है. 282 00:20:55,600 --> 00:20:59,020 यह वास्तव में एक ही बात है. यह अपनी व्यक्तिगत क्षेत्रों में से प्रत्येक की तरह है 283 00:20:59,020 --> 00:21:04,460 उस में एक कचरा मूल्य हो सकता है. >> और यह संभव को परिभाषित करने की घोषणा करने के लिए एक struct 284 00:21:04,460 --> 00:21:07,740 उन्हें एक तरीका है कि यह करता है में हस्ताक्षर? 285 00:21:07,740 --> 00:21:13,200 [Bowden] हाँ. तो, शॉर्टकट initialization वाक्यविन्यास 286 00:21:13,200 --> 00:21:18,660 की तरह लग रहा है - 287 00:21:18,660 --> 00:21:22,200 वहाँ दो तरीकों से हम यह कर सकते है. मुझे लगता है कि हम यह संकलन चाहिए 288 00:21:22,200 --> 00:21:25,840 यकीन है कि बजना बनाने के लिए भी करता है. 289 00:21:25,840 --> 00:21:28,510 तर्कों के आदेश है कि struct में आता है, 290 00:21:28,510 --> 00:21:32,170 आप इन घुंघराले ब्रेसिज़ के अंदर बहस के आदेश के रूप में डाल दिया. 291 00:21:32,170 --> 00:21:35,690 तो अगर आप यह 9 इनिशियलाइज़ चाहते हैं और छोड़ दिया तो सही अशक्त और अशक्त हो सकता है, 292 00:21:35,690 --> 00:21:41,570 यह 9, अशक्त, अशक्त होगा. 293 00:21:41,570 --> 00:21:47,890 विकल्प है, और संपादक इस वाक्यविन्यास पसंद नहीं करता है, 294 00:21:47,890 --> 00:21:50,300 और यह सोचता है कि मैं एक नया खंड चाहते हैं, 295 00:21:50,300 --> 00:22:01,800 लेकिन विकल्प की तरह कुछ है - 296 00:22:01,800 --> 00:22:04,190 यहाँ, मैं इसे एक नई लाइन पर डाल देता हूँ. 297 00:22:04,190 --> 00:22:09,140 आप स्पष्ट रूप से कह सकते हैं, मैं सटीक वाक्यविन्यास भूल जाते हैं. 298 00:22:09,140 --> 00:22:13,110 तो आप स्पष्ट रूप से उनके नाम से पता कर सकते हैं, और कहते हैं, 299 00:22:13,110 --> 00:22:21,570 ग, या. मूल्य = 9, बाएँ रिक्त =. 300 00:22:21,570 --> 00:22:24,540 मैं इन अल्पविराम होने की जरूरत लग रहा है. 301 00:22:24,540 --> 00:22:29,110 सही = रिक्त तो, इस तरह तुम नहीं 302 00:22:29,110 --> 00:22:33,780 वास्तव में struct के आदेश पता करने की आवश्यकता है, 303 00:22:33,780 --> 00:22:36,650 और जब आप यह पढ़ रहे हैं, यह बहुत अधिक स्पष्ट है 304 00:22:36,650 --> 00:22:41,920 के बारे में क्या मूल्य initialized किया जा रहा है. 305 00:22:41,920 --> 00:22:44,080 >> यह चीजें हैं जो होना होता है - 306 00:22:44,080 --> 00:22:49,100 हां, तो सबसे अधिक भाग के लिए, सी + + सी. के एक superset 307 00:22:49,100 --> 00:22:54,160 आप सी कोड ले, सी + +, और यह संकलन चाहिए यह स्थानांतरित कर सकते हैं. 308 00:22:54,160 --> 00:22:59,570 यह एक चीज़ें है कि सी + + का समर्थन नहीं करता है, तो लोगों को यह नहीं करते हैं. 309 00:22:59,570 --> 00:23:01,850 मैं जानता हूँ कि अगर वह एकमात्र कारण है कि लोगों को यह नहीं करते हैं पता नहीं है, 310 00:23:01,850 --> 00:23:10,540 लेकिन इस मामले में जहां मैं इसे इस्तेमाल करने की जरूरत है सी + + और इसलिए मैं यह नहीं इस्तेमाल कर सकते हैं के साथ काम करने की जरूरत है. 311 00:23:10,540 --> 00:23:14,000 कुछ है कि एक और उदाहरण है सी + + है साथ काम नहीं करता 312 00:23:14,000 --> 00:23:16,940 malloc एक "शून्य *," कैसे देता है, तकनीकी रूप से, 313 00:23:16,940 --> 00:23:20,200 लेकिन तुम सिर्फ चार * x = malloc जो कुछ भी कह सकते हैं, 314 00:23:20,200 --> 00:23:22,840 और यह स्वचालित रूप से एक चार * के लिए डाली जाएगा. 315 00:23:22,840 --> 00:23:25,450 यह स्वचालित डाली में नहीं होता है सी + +. 316 00:23:25,450 --> 00:23:28,150 कि संकलन नहीं है, और आप स्पष्ट रूप से कहने की ज़रूरत नहीं होगा 317 00:23:28,150 --> 00:23:34,510 चार *, malloc, जो कुछ भी है, के लिए यह एक चार * डाली. 318 00:23:34,510 --> 00:23:37,270 वहाँ कई चीजें है कि सी और सी + + पर असहमत नहीं हैं, 319 00:23:37,270 --> 00:23:40,620 लेकिन उन दो हैं. 320 00:23:40,620 --> 00:23:43,120 तो हम इस सिंटैक्स के साथ जाना होगा. 321 00:23:43,120 --> 00:23:46,150 लेकिन फिर भी अगर हम उस वाक्य रचना के साथ जाना नहीं था, 322 00:23:46,150 --> 00:23:49,470 क्या है इस के साथ गलत हो सकता है? 323 00:23:49,470 --> 00:23:52,170 [छात्र] मैं यह भिन्नता करने की जरूरत नहीं है? >> हाँ. 324 00:23:52,170 --> 00:23:55,110 याद रखें कि तीर एक अंतर्निहित भिन्नता है, 325 00:23:55,110 --> 00:23:58,230 और इसलिए जब हम सिर्फ एक struct के साथ काम कर रहे हैं, 326 00:23:58,230 --> 00:24:04,300 हम प्रयोग करना चाहते हैं. struct के एक क्षेत्र के अंदर में मिलता है. 327 00:24:04,300 --> 00:24:07,200 और केवल समय हम तीर का उपयोग है जब हम करना चाहते हैं - 328 00:24:07,200 --> 00:24:13,450 ठीक है, तीर के बराबर है - 329 00:24:13,450 --> 00:24:17,020 है कि यह क्या अगर मैं तीर का इस्तेमाल करने का मतलब होगा. 330 00:24:17,020 --> 00:24:24,600 सभी तीर का मतलब है, यह भिन्नता है, अब मैं एक struct में हूँ, और मैं इस क्षेत्र में प्राप्त कर सकते हैं. 331 00:24:24,600 --> 00:24:28,040 क्षेत्र या तो सीधे या भिन्नता पाने के लिए और क्षेत्र - 332 00:24:28,040 --> 00:24:30,380 मुझे लगता है कि इस मूल्य होना चाहिए. 333 00:24:30,380 --> 00:24:33,910 लेकिन यहाँ मैं सिर्फ एक, एक struct के लिए एक सूचक नहीं struct के साथ काम कर रहा हूँ, 334 00:24:33,910 --> 00:24:38,780 और इसलिए मैं तीर का उपयोग नहीं कर सकते हैं. 335 00:24:38,780 --> 00:24:47,510 लेकिन इस तरह की बात हम सभी नोड्स के लिए कर सकते हैं. 336 00:24:47,510 --> 00:24:55,790 हे भगवान. 337 00:24:55,790 --> 00:25:09,540 यह 6, 7, और 3 में से एक है. 338 00:25:09,540 --> 00:25:16,470 तो हम हमारे पेड़ में शाखाओं की स्थापना कर सकते हैं, हम कर सकते हैं 7 - 339 00:25:16,470 --> 00:25:21,650 हम, अपनी बाईं 3 से बात कर सकते हैं. 340 00:25:21,650 --> 00:25:25,130 तो हम कैसे करते हैं? 341 00:25:25,130 --> 00:25:29,320 [छात्रों, unintelligible] >> हाँ. node3 के पते, 342 00:25:29,320 --> 00:25:34,170 और अगर आप पता नहीं था, तो यह न सिर्फ संकलन होगा. 343 00:25:34,170 --> 00:25:38,190 लेकिन याद रखना कि इन अगले नोड के संकेत दिए गए हैं. 344 00:25:38,190 --> 00:25:44,930 सही 9 में बात करनी चाहिए, 345 00:25:44,930 --> 00:25:53,330 और 3 6 के लिए सही पर बात करनी चाहिए. 346 00:25:53,330 --> 00:25:58,480 मुझे लगता है कि यह सब सेट है. किसी भी टिप्पणी या प्रश्न? 347 00:25:58,480 --> 00:26:02,060 [छात्र, unintelligible] जड़ से 7 हो जा रहा है. 348 00:26:02,060 --> 00:26:08,210 हम सिर्फ नोड कह सकते हैं * ptr = 349 00:26:08,210 --> 00:26:14,160 या रूट =, और node7. 350 00:26:14,160 --> 00:26:20,730 >> हमारे प्रयोजनों के लिए, हम डालने के साथ काम करने जा रहे हैं, 351 00:26:20,730 --> 00:26:25,490 तो हम इस द्विआधारी पेड़ में सम्मिलित करने के लिए एक समारोह में लिखने के लिए चाहते करने जा रहे हैं 352 00:26:25,490 --> 00:26:34,230 और डालने के अनिवार्य रूप से malloc कॉल करने के लिए इस पेड़ के लिए एक नया नोड बनाने जा रहा है. 353 00:26:34,230 --> 00:26:36,590 तो चीजें इस तथ्य के साथ गंदा हो जा रहे हैं कि कुछ नोड्स 354 00:26:36,590 --> 00:26:38,590 ढेर पर वर्तमान में कर रहे हैं 355 00:26:38,590 --> 00:26:43,680 और अन्य नोड्स के लिए ढेर पर खत्म होता है जब हम उन्हें डालने के लिए जा रहे हैं. 356 00:26:43,680 --> 00:26:47,640 यह पूरी तरह से वैध है, लेकिन एक ही कारण 357 00:26:47,640 --> 00:26:49,600 हम ढेर पर ऐसा करने में सक्षम हैं 358 00:26:49,600 --> 00:26:51,840 क्योंकि यह एक ऐसी काल्पनिक उदाहरण है कि हम जानते हैं कि 359 00:26:51,840 --> 00:26:56,360 7, 3, 6, 9 के रूप में निर्माण किया जा पेड़ माना जाता है. 360 00:26:56,360 --> 00:27:02,970 यदि हम ऐसा नहीं किया, तो हम पहली जगह में malloc नहीं करना होगा. 361 00:27:02,970 --> 00:27:06,160 जैसा कि हम थोड़ा बाद में देखेंगे, हम malloc'ing किया जाना चाहिए. 362 00:27:06,160 --> 00:27:08,570 अभी यह पूरी तरह से उचित है के ढेर पर डाल दिया है, 363 00:27:08,570 --> 00:27:14,750 लेकिन एक malloc कार्यान्वयन के लिए इस परिवर्तन. 364 00:27:14,750 --> 00:27:17,160 तो इनमें से प्रत्येक के लिए कुछ तरह होने जा रहा है 365 00:27:17,160 --> 00:27:24,240 नोड node9 * = malloc ((नोड) sizeof). 366 00:27:24,240 --> 00:27:28,040 और अब हम हमारे चेक करने के लिए जा रहे हैं. 367 00:27:28,040 --> 00:27:34,010 अगर (== Null node9) - मैं नहीं चाहता था कि - 368 00:27:34,010 --> 00:27:40,950 1 लौटने के लिए, और फिर हम node9> नहीं है क्योंकि अब यह एक सूचक है, 369 00:27:40,950 --> 00:27:45,300 मूल्य = 6, node9> = रिक्त छोड़ दिया, 370 00:27:45,300 --> 00:27:48,930 node9 रिक्त> सही = 371 00:27:48,930 --> 00:27:51,410 और हम उन नोड्स में से प्रत्येक के लिए कि क्या करना है करने के लिए जा रहे हैं. 372 00:27:51,410 --> 00:27:57,490 तो बजाय, चलो यह एक अलग समारोह के अंदर रख दिया. 373 00:27:57,490 --> 00:28:00,620 चलो नोड build_node * कहते हैं, 374 00:28:00,620 --> 00:28:09,050 और यह कुछ APIs हम Huffman कोडिंग के लिए उपलब्ध कराने के लिए इसी तरह की है. 375 00:28:09,050 --> 00:28:12,730 हम आपको एक पेड़ के लिए initializer कार्यों दे 376 00:28:12,730 --> 00:28:20,520 और deconstructor उन पेड़ों और जंगलों के लिए एक ही के लिए "कार्य". 377 00:28:20,520 --> 00:28:22,570 >> तो यहाँ हम एक initializer समारोह के लिए जा रहे हैं 378 00:28:22,570 --> 00:28:25,170 सिर्फ हमारे लिए एक नोड का निर्माण. 379 00:28:25,170 --> 00:28:29,320 और यह वास्तव में इस तरह बहुत ज्यादा लग रहा है. 380 00:28:29,320 --> 00:28:32,230 और मैं भी आलसी हो जा रहा हूँ और चर का नाम बदलने के लिए नहीं, 381 00:28:32,230 --> 00:28:34,380 भले ही node9 अब और कोई मतलब नहीं बनाता है. 382 00:28:34,380 --> 00:28:38,610 ओह, मैं node9 मूल्य लगता है कि नहीं होना चाहिए 6. 383 00:28:38,610 --> 00:28:42,800 अब हम node9 लौट सकते हैं. 384 00:28:42,800 --> 00:28:49,550 और यहाँ हम अशक्त लौट जाना चाहिए. 385 00:28:49,550 --> 00:28:52,690 हर कोई है कि समारोह में निर्माण एक नोड पर सहमत हैं? 386 00:28:52,690 --> 00:28:59,780 तो अब हम सिर्फ फोन है कि किसी दिए गए मूल्य और अशक्त संकेत के साथ किसी भी नोड का निर्माण करने के लिए कर सकते हैं. 387 00:28:59,780 --> 00:29:09,750 अब हम कह सकते हैं, हम नोड node9 * = build_node (9) कर सकते हैं. 388 00:29:09,750 --> 00:29:25,810 और करना. . . 389 00:29:25,810 --> 00:29:33,980 6, 3, 7, 6, 3, 7. 390 00:29:33,980 --> 00:29:39,330 और अब हम एक ही संकेत सेट करना चाहते हैं, 391 00:29:39,330 --> 00:29:42,470 अब के अलावा सब कुछ संकेत के मामले में पहले से ही है 392 00:29:42,470 --> 00:29:48,480 इसलिए नहीं के पते की आवश्यकता है. 393 00:29:48,480 --> 00:29:56,300 ठीक है. तो आखिरी बात मैं करना चाहता क्या है? 394 00:29:56,300 --> 00:30:03,850 वहाँ एक त्रुटि जाँच है कि मैं नहीं कर रहा हूँ. 395 00:30:03,850 --> 00:30:06,800 क्या नोड वापसी निर्माण करता है? 396 00:30:06,800 --> 00:30:11,660 [छात्र, unintelligible] >> हाँ. यदि malloc विफल रहा है, यह शून्य वापस कर देंगे. 397 00:30:11,660 --> 00:30:16,460 तो मैं lazily यहाँ प्रत्येक के लिए एक शर्त करने के बजाय इसे नीचे रख करने के लिए जा रहा हूँ. 398 00:30:16,460 --> 00:30:22,320 अगर (रिक्त node9 ==, या और भी आसान, 399 00:30:22,320 --> 00:30:28,020 इस node9 ही नहीं, अगर करने के लिए बराबर है. 400 00:30:28,020 --> 00:30:38,310 तो अगर node9 नहीं है, या नहीं node6, या नहीं node3, या नहीं node7, 1 लौटने के लिए. 401 00:30:38,310 --> 00:30:42,850 शायद हम प्रिंट चाहिए malloc विफल रहा है, या कुछ और. 402 00:30:42,850 --> 00:30:46,680 [छात्र] बराबर गलत के रूप में अच्छी तरह से अशक्त है? 403 00:30:46,680 --> 00:30:51,290 [Bowden] कोई शून्य मान गलत है. 404 00:30:51,290 --> 00:30:53,920 तो अशक्त एक शून्य मान है. 405 00:30:53,920 --> 00:30:56,780 शून्य एक शून्य मान है. झूठा एक शून्य मान है. 406 00:30:56,780 --> 00:31:02,130 कोई बहुत ज्यादा केवल 2 शून्य मान शून्य और शून्य हैं, 407 00:31:02,130 --> 00:31:07,900 झूठी सिर्फ शून्य के रूप में परिभाषित किया हैश है. 408 00:31:07,900 --> 00:31:13,030 यह भी लागू होता है अगर हम वैश्विक चर घोषणा करते हैं. 409 00:31:13,030 --> 00:31:17,890 अगर हम नोड * जड़ है यहाँ था, 410 00:31:17,890 --> 00:31:24,150 फिर वैश्विक चर के बारे में अच्छी बात यह है कि वे हमेशा एक प्रारंभिक मूल्य है. 411 00:31:24,150 --> 00:31:27,500 यह कार्यों का सच नहीं है, यहाँ के अंदर कैसे, 412 00:31:27,500 --> 00:31:34,870 अगर हम, जैसे, नोड * या नोड एक्स. 413 00:31:34,870 --> 00:31:37,380 हम पता नहीं क्या x.value, x.whatever है, 414 00:31:37,380 --> 00:31:40,700 या हम उन्हें प्रिंट और वे मनमाने ढंग से हो सकता सकता है. 415 00:31:40,700 --> 00:31:44,980 यह वैश्विक चर का सच नहीं है. 416 00:31:44,980 --> 00:31:47,450 तो नोड जड़ या नोड एक्स. 417 00:31:47,450 --> 00:31:53,410 डिफ़ॉल्ट रूप से, सब कुछ है कि वैश्विक है, नहीं तो कुछ मूल्य के लिए स्पष्ट रूप से पड़ेगा, 418 00:31:53,410 --> 00:31:57,390 अपने मूल्य के रूप में एक शून्य मान है. 419 00:31:57,390 --> 00:32:01,150 तो यहाँ, नोड * जड़, हम कुछ भी करने के लिए स्पष्ट रूप से यह नहीं इनिशियलाइज़ करते हैं, 420 00:32:01,150 --> 00:32:06,350 तो उसके डिफ़ॉल्ट मान शून्य हो सकता है, जो संकेत के शून्य मान है. 421 00:32:06,350 --> 00:32:11,870 एक्स के डिफ़ॉल्ट मान मतलब कि x.value शून्य है जा रहा है, 422 00:32:11,870 --> 00:32:14,260 x.left अशक्त है, है और x.right रिक्त है. 423 00:32:14,260 --> 00:32:21,070 इतने के बाद से यह एक struct है struct के क्षेत्रों के सभी शून्य मान होगा. 424 00:32:21,070 --> 00:32:24,410 कि हम यहाँ का उपयोग की जरूरत नहीं है, फिर भी. 425 00:32:24,410 --> 00:32:27,320 [छात्र] structs अन्य चर से अलग कर रहे हैं, और अन्य चर रहे हैं 426 00:32:27,320 --> 00:32:31,400 कचरा मूल्यों, इन शून्य हैं? 427 00:32:31,400 --> 00:32:36,220 [Bowden] भी मान. तो एक्स, एक्स शून्य हो जाएगा. 428 00:32:36,220 --> 00:32:40,070 यदि यह वैश्विक दायरे में है, यह एक प्रारंभिक मूल्य है. ठीक है. >> 429 00:32:40,070 --> 00:32:48,950 [Bowden] या तो प्रारंभिक मूल्य आप यह या शून्य दिया. 430 00:32:48,950 --> 00:32:53,260 मुझे लगता है कि इस सब का ख्याल रखता है. 431 00:32:53,260 --> 00:32:58,390 >> ठीक है. तो प्रश्न के अगले भाग पूछता है, 432 00:32:58,390 --> 00:33:01,260 "अब हमें बुलाया शामिल एक समारोह लिखने के लिए चाहते हैं 433 00:33:01,260 --> 00:33:04,930 bool के एक प्रोटोटाइप के साथ int मूल्य शामिल हैं. " 434 00:33:04,930 --> 00:33:08,340 हम bool int मूल्य शामिल करने के लिए नहीं जा रहे हैं. 435 00:33:08,340 --> 00:33:15,110 हमारे प्रोटोटाइप की तरह लग रहा है 436 00:33:15,110 --> 00:33:22,380 bool (int मूल्य शामिल हैं. 437 00:33:22,380 --> 00:33:24,490 और फिर हम भी यह पेड़ पारित करने के लिए जा रहे हैं 438 00:33:24,490 --> 00:33:28,870 कि यह देखने के लिए अगर यह है कि मूल्य है की जाँच की जानी चाहिए. 439 00:33:28,870 --> 00:33:38,290 तो नोड * पेड़). ठीक है. 440 00:33:38,290 --> 00:33:44,440 और फिर हम ऐसा कुछ के साथ कॉल कर सकते हैं, 441 00:33:44,440 --> 00:33:46,090 शायद हम printf या कुछ और करने के लिए चाहता हूँ. 442 00:33:46,090 --> 00:33:51,040 6, हमारी जड़ में शामिल हैं. 443 00:33:51,040 --> 00:33:54,300 यह एक है, या सच लौट जाना चाहिए, 444 00:33:54,300 --> 00:33:59,390 जबकि 5 जड़ होता झूठी लौट जाना चाहिए. 445 00:33:59,390 --> 00:34:02,690 तो एक दूसरे से इस लागू करने. 446 00:34:02,690 --> 00:34:06,780 आप इसे या तो iteratively या बारी बारी से कर सकते हैं. 447 00:34:06,780 --> 00:34:09,739 जिस तरह से हम चीजों को स्थापित किया है के बारे में अच्छी बात यह है कि 448 00:34:09,739 --> 00:34:12,300 यह ही हमारे पुनरावर्ती बहुत आसान समाधान के लिए उधार देता है 449 00:34:12,300 --> 00:34:14,719 की तुलना में वैश्विक चर का रास्ता था. 450 00:34:14,719 --> 00:34:19,750 क्योंकि अगर हम सिर्फ int मूल्य होता है, तो हम नीचे subtrees recursing का कोई रास्ता नहीं है. 451 00:34:19,750 --> 00:34:24,130 हम एक अलग सहायक समारोह में कहा कि हमारे लिए subtrees recurses होता है. 452 00:34:24,130 --> 00:34:29,610 लेकिन जब से हम बदल दिया है यह एक तर्क के रूप में पेड़ लेने के लिए, 453 00:34:29,610 --> 00:34:32,760 जो यह हमेशा पहली जगह में होना चाहिए था, 454 00:34:32,760 --> 00:34:35,710 अब हम recurse और अधिक आसानी से कर सकते हैं. 455 00:34:35,710 --> 00:34:38,960 चलने का या तो पुनरावर्ती, हम दोनों पर जायेंगे, 456 00:34:38,960 --> 00:34:46,139 लेकिन हम काफी आसान किया जा रहा है कि पुनरावर्ती समाप्त होता देखेंगे. 457 00:34:59,140 --> 00:35:02,480 ठीक है. क्या किसी को कुछ हम साथ काम कर सकते है? 458 00:35:02,480 --> 00:35:12,000 >> [छात्र] मुझे मिल गया है एक समाधान के चलने का. >> ठीक है, चलने का. 459 00:35:12,000 --> 00:35:16,030 ठीक है, यह अच्छा लग रहा है. 460 00:35:16,030 --> 00:35:18,920 तो, हमें इसे माध्यम से चलना चाहते हैं? 461 00:35:18,920 --> 00:35:25,780 [छात्र] ज़रूर. तो मैं एक अस्थायी चर सेट करने के पेड़ की 1 नोड. 462 00:35:25,780 --> 00:35:28,330 और फिर मैं बस जबकि अस्थायी बराबर अशक्त नहीं करता है के माध्यम से looped, 463 00:35:28,330 --> 00:35:31,700 जबकि पेड़ में अभी भी था, मुझे लगता है. 464 00:35:31,700 --> 00:35:35,710 और अगर मान मूल्य के बराबर है कि अस्थायी इशारा कर रहा है, 465 00:35:35,710 --> 00:35:37,640 तो यह है कि मान देता है. 466 00:35:37,640 --> 00:35:40,210 अन्यथा, यह चेक अगर यह सही पक्ष या बाईं ओर है. 467 00:35:40,210 --> 00:35:43,400 अगर तुम कभी एक स्थिति पाने के लिए जहां वहाँ कोई और अधिक पेड़ है, 468 00:35:43,400 --> 00:35:47,330 तो यह देता है - यह बाहर निकलता है पाश और झूठे रिटर्न. 469 00:35:47,330 --> 00:35:52,190 [Bowden] ठीक है. तो यह है कि अच्छा लगता है. 470 00:35:52,190 --> 00:35:58,470 किसी को कुछ भी पर कोई टिप्पणी है? 471 00:35:58,470 --> 00:36:02,400 मैं सब पर कोई शुद्धता टिप्पणी है. 472 00:36:02,400 --> 00:36:11,020 एक बात हम क्या कर सकते हैं इस आदमी है. 473 00:36:11,020 --> 00:36:21,660 ओह, यह एक छोटे से दीर्घाकार जाना जा रहा है. 474 00:36:21,660 --> 00:36:33,460 मुझे लगता है कि इसे ठीक कर दूँगा. ठीक है. 475 00:36:33,460 --> 00:36:37,150 >> हर कोई याद रखना चाहिए कैसे त्रिगुट काम करता है. 476 00:36:37,150 --> 00:36:38,610 वहाँ निश्चित रूप से अतीत में quizzes किया गया 477 00:36:38,610 --> 00:36:41,170 है कि आप एक त्रिगुट ऑपरेटर के साथ एक समारोह दे, 478 00:36:41,170 --> 00:36:45,750 और कहते हैं, इस का अनुवाद करने के लिए, कुछ है कि त्रिगुट का उपयोग नहीं करता है. 479 00:36:45,750 --> 00:36:49,140 तो यह एक बहुत ही आम का मामला है जब मैं त्रिगुट का उपयोग करने के लिए लगता है कि होगा, 480 00:36:49,140 --> 00:36:54,610 जहां अगर कुछ हालत कुछ करने के लिए एक चर सेट, 481 00:36:54,610 --> 00:36:58,580 और कुछ और करने के लिए है कि एक ही चर सेट. 482 00:36:58,580 --> 00:37:03,390 यह कुछ है कि बहुत बार इस तरह की बात में तब्दील किया जा सकता है 483 00:37:03,390 --> 00:37:14,420 जहां यह है कि चर सेट - या, ठीक है, यह सच है? तो यह है, और इस. 484 00:37:14,420 --> 00:37:18,550 [छात्र] पहले एक यह है कि अगर यह सच है, है ना? 485 00:37:18,550 --> 00:37:25,570 [Bowden] हाँ. जिस तरह से मैं हमेशा इसे पढ़ा है, अस्थायी अस्थायी मूल्य से अधिक मूल्य के बराबर है, 486 00:37:25,570 --> 00:37:30,680 तो यह है, और इस. यह एक सवाल पूछ रहा है. 487 00:37:30,680 --> 00:37:35,200 यह अधिक से अधिक है? तो पहली बात करते हैं. वरना दूसरी बात करते हैं. 488 00:37:35,200 --> 00:37:41,670 मैं लगभग हमेशा बृहदान्त्र, मैं सिर्फ मेरे सिर में, मैं के रूप में और पढ़ें. 489 00:37:41,670 --> 00:37:47,180 >> क्या किसी को एक पुनरावर्ती समाधान है? 490 00:37:47,180 --> 00:37:49,670 ठीक है. यह एक हम करने के लिए जा रहे हैं - यह पहले से ही बहुत अच्छा हो सकता है, 491 00:37:49,670 --> 00:37:53,990 लेकिन हम इसे और भी बेहतर बनाने के लिए जा रहे हैं. 492 00:37:53,990 --> 00:37:58,720 यह बहुत ज्यादा एक ही सटीक विचार है. 493 00:37:58,720 --> 00:38:03,060 यह सिर्फ है, ठीक है, आप को समझाने चाहते हो? 494 00:38:03,060 --> 00:38:08,340 [छात्र] ज़रूर. तो हमें यकीन है कि पेड़ 1 अशक्त नहीं है के लिए कर रहे हैं, 495 00:38:08,340 --> 00:38:13,380 क्योंकि अगर पेड़ रिक्त है तो यह वापसी झूठी जा रहा है क्योंकि हम यह नहीं मिला है. 496 00:38:13,380 --> 00:38:19,200 और अगर वहाँ अभी भी एक पेड़ है, हम में जाने - हम पहले की जाँच करें अगर मूल्य वर्तमान नोड है. 497 00:38:19,200 --> 00:38:23,740 सच लौटें अगर यह है, और अगर हम नहीं छोड़ दिया है या सही पर recurse. 498 00:38:23,740 --> 00:38:25,970 कि ध्वनि करता है उचित है? >> मम - हम्म. (अनुबंध) 499 00:38:25,970 --> 00:38:33,880 तो सूचना है कि यह लगभग structurally बहुत समाधान चलने का समान. 500 00:38:33,880 --> 00:38:38,200 यह सिर्फ है कि recursing के बजाय, हम एक समय पाश था. 501 00:38:38,200 --> 00:38:40,840 और आधार यहाँ मामले में जहां पेड़ बराबर अशक्त नहीं करता 502 00:38:40,840 --> 00:38:44,850 शर्त है जिसके तहत हम जबकि पाश से बाहर तोड़ दिया था. 503 00:38:44,850 --> 00:38:50,200 वे बहुत ही इसी तरह की हैं. लेकिन हम यह एक कदम आगे ले जा रहे हैं. 504 00:38:50,200 --> 00:38:54,190 अब, हम यहाँ एक ही बात करते हैं. 505 00:38:54,190 --> 00:38:57,680 सूचना हम इन लाइनों के दोनों में एक ही बात लौट रहे हैं, 506 00:38:57,680 --> 00:39:00,220 के लिए छोड़कर एक तर्क अलग है. 507 00:39:00,220 --> 00:39:07,950 तो हम एक त्रिगुट में बनाने जा रहे हैं. 508 00:39:07,950 --> 00:39:13,790 मैं विकल्प कुछ हिट, और यह एक प्रतीक बना दिया. ठीक है. 509 00:39:13,790 --> 00:39:21,720 तो हम वापस जा रहे हैं कि शामिल हैं. 510 00:39:21,720 --> 00:39:28,030 इस के लिए कई लाइनों हो रही है, ठीक है, यह है में तेजी से बढ़ी है. 511 00:39:28,030 --> 00:39:31,060 आमतौर पर, एक शैलीगत बात के रूप में, मैं कई लोगों को लगता है 512 00:39:31,060 --> 00:39:38,640 तीर के बाद एक जगह रखा है, लेकिन मुझे लगता है कि अगर आप लगातार कर रहे हैं, यह ठीक है. 513 00:39:38,640 --> 00:39:44,320 यदि मान पेड़ मूल्य से भी कम है, हम पेड़ बाईं पर recurse चाहते हैं, 514 00:39:44,320 --> 00:39:53,890 और हम पेड़ सही पर recurse करने के लिए करना चाहते हैं. 515 00:39:53,890 --> 00:39:58,610 तो यह है कि यह देखो छोटे बनाने के एक कदम था. 516 00:39:58,610 --> 00:40:02,660 यह देखो छोटे बनाने के दो कदम - 517 00:40:02,660 --> 00:40:09,150 हम यह कई लाइनों को अलग नहीं कर सकते हैं. 518 00:40:09,150 --> 00:40:16,500 ठीक है. यह छोटे देखो बनाने के चरण दो यहाँ है, 519 00:40:16,500 --> 00:40:25,860 इतना वापसी मूल्य पेड़ मूल्य के बराबर होती है, या जो भी शामिल हैं. 520 00:40:25,860 --> 00:40:28,340 >> यह एक महत्वपूर्ण बात है. 521 00:40:28,340 --> 00:40:30,860 मुझे यकीन है कि अगर उन्होंने कहा कि यह वर्ग में स्पष्ट रूप से नहीं कर रहा हूँ, 522 00:40:30,860 --> 00:40:34,740 लेकिन यह शॉर्ट सर्किट मूल्यांकन कहा जाता है. 523 00:40:34,740 --> 00:40:41,060 यहाँ विचार मूल्य == पेड़ मूल्य. 524 00:40:41,060 --> 00:40:49,960 अगर यह सच है, तो यह सच है, और हम चाहते हैं 'या' उस के साथ जो कुछ भी यहाँ पर है. 525 00:40:49,960 --> 00:40:52,520 तो भी जो कुछ भी यहाँ पर है के बारे में सोच के बिना, 526 00:40:52,520 --> 00:40:55,070 पूरे करने के लिए वापस जा अभिव्यक्ति क्या है? 527 00:40:55,070 --> 00:40:59,430 [छात्र] यह सच है? >> हाँ, क्योंकि कुछ का सच 528 00:40:59,430 --> 00:41:04,990 कुछ के साथ or'd - या सच or'd जरूरी सच है. 529 00:41:04,990 --> 00:41:08,150 इसलिए जैसे ही हम वापसी मान = पेड़ मूल्य देखते हैं, 530 00:41:08,150 --> 00:41:10,140 हम सिर्फ सच वापसी करने के लिए जा रहे हैं. 531 00:41:10,140 --> 00:41:15,710 Recurse करने के लिए भी नहीं जा रहा है और आगे नीचे पंक्ति है. 532 00:41:15,710 --> 00:41:20,980 हम इस एक कदम आगे ले जा सकते हैं. 533 00:41:20,980 --> 00:41:29,490 वापसी बराबर अशक्त और इस सब के पेड़ नहीं है. 534 00:41:29,490 --> 00:41:32,650 यह यह एक समारोह में एक पंक्ति बनाया है. 535 00:41:32,650 --> 00:41:36,790 यह भी शॉर्ट सर्किट मूल्यांकन का एक उदाहरण है. 536 00:41:36,790 --> 00:41:40,680 लेकिन अब यह एक ही विचार है - 537 00:41:40,680 --> 00:41:47,320 के बजाय यदि ऐसा है तो पेड़ नहीं अशक्त बराबर करता है - या, ठीक है, 538 00:41:47,320 --> 00:41:49,580 अगर पेड़ बराबर अशक्त करता है, जो खराब मामला है, 539 00:41:49,580 --> 00:41:54,790 अगर पेड़ अशक्त के बराबर होती है, तो पहली शर्त के लिए झूठी होने जा रहा है. 540 00:41:54,790 --> 00:42:00,550 तो कुछ के साथ anded झूठी क्या होने जा रहा है? 541 00:42:00,550 --> 00:42:04,640 [छात्र] झूठा. >> हाँ. यह शॉर्ट सर्किट मूल्यांकन के अन्य आधा है, 542 00:42:04,640 --> 00:42:10,710 जहां अगर पेड़ बराबर अशक्त नहीं करता है तो हम जा रहे हैं के लिए भी जाना नहीं - 543 00:42:10,710 --> 00:42:14,930 या अगर पेड़ बराबर अशक्त करता है, तो हम == मूल्य पेड़ मूल्य नहीं जा रहे हैं. 544 00:42:14,930 --> 00:42:17,010 हम सिर्फ तुरंत झूठी वापसी करने के लिए जा रहे हैं. 545 00:42:17,010 --> 00:42:20,970 जो महत्वपूर्ण है, क्योंकि अगर यह मूल्यांकन शॉर्ट सर्किट नहीं किया, 546 00:42:20,970 --> 00:42:25,860 फिर अगर पेड़ बराबर अशक्त करता है, इस दूसरी शर्त seg गलती के लिए जा रहा है, 547 00:42:25,860 --> 00:42:32,510 क्योंकि पेड़ -> मूल्य अशक्त dereferencing है. 548 00:42:32,510 --> 00:42:40,490 तो वह है कि. यह कर सकते हैं - शिफ्ट करने के लिए एक बार से अधिक. 549 00:42:40,490 --> 00:42:44,840 यह एक बहुत ही आम बात है, इस के साथ इस एक लाइन नहीं है, 550 00:42:44,840 --> 00:42:49,000 लेकिन यह परिस्थितियों में एक आम बात है, यहीं शायद नहीं, 551 00:42:49,000 --> 00:42:59,380 लेकिन अगर (पेड़ = NULL!, और पेड़ -> मूल्य == मूल्य), जो कुछ भी करते हैं. 552 00:42:59,380 --> 00:43:01,560 यह एक बहुत ही सामान्य स्थिति है, जहां होने के बजाय 553 00:43:01,560 --> 00:43:06,770 दो ifs हैं में यह टूट गया है, जहां चाहें, पेड़ अशक्त है? 554 00:43:06,770 --> 00:43:11,780 ठीक है, यह शून्य नहीं है, तो अब पेड़ के मूल्य के बराबर मूल्य है? यह मत करो. 555 00:43:11,780 --> 00:43:17,300 इसके बजाय, इस हालत है, इस गलती कभी नहीं seg जाएगा 556 00:43:17,300 --> 00:43:21,220 क्योंकि यह बाहर तोड़ने के लिए अगर यह होता रिक्त हो जाएगा. 557 00:43:21,220 --> 00:43:24,000 खैर, मुझे लगता है कि यदि आपके पेड़ एक पूरी तरह से अमान्य सूचक है, यह अभी भी फॉल्ट कर सकते हैं, 558 00:43:24,000 --> 00:43:26,620 लेकिन यह गलती नहीं seg है अगर पेड़ रिक्त है कर सकते हैं. 559 00:43:26,620 --> 00:43:32,900 अगर यह शून्य थे, यह बाहर तोड़ने से पहले आप कभी पहली जगह में सूचक dereferenced होगा. 560 00:43:32,900 --> 00:43:35,000 [छात्र] इस आलसी मूल्यांकन बुलाया है? 561 00:43:35,000 --> 00:43:40,770 >> [Bowden] आलसी मूल्यांकन एक अलग बात है. 562 00:43:40,770 --> 00:43:49,880 आलसी मूल्यांकन है और अधिक की तरह आप एक मूल्य के लिए पूछना, 563 00:43:49,880 --> 00:43:54,270 आप के लिए एक मूल्य की तरह की गणना पूछना है, लेकिन आप इसे तुरंत की जरूरत नहीं है. 564 00:43:54,270 --> 00:43:59,040 तो जब तक आप वास्तव में इसे जरूरत है, यह मूल्यांकन नहीं किया जाता. 565 00:43:59,040 --> 00:44:03,920 यह वास्तव में एक ही बात नहीं है, लेकिन Huffman pset में, 566 00:44:03,920 --> 00:44:06,520 यह कहते हैं कि हम "lazily" लिखने. 567 00:44:06,520 --> 00:44:08,670 कारण है कि हम ऐसा कर है क्योंकि हम वास्तव में लिखने buffering रहे हैं - 568 00:44:08,670 --> 00:44:11,820 हम एक समय में अलग - अलग बिट्स लिखना नहीं चाहता, 569 00:44:11,820 --> 00:44:15,450 या एक समय में अलग - अलग बाइट्स, हम बजाय बाइट्स का एक हिस्सा प्राप्त करना चाहते हैं. 570 00:44:15,450 --> 00:44:19,270 फिर एक बार हम बाइट्स का एक हिस्सा है, तो हम इसे लिखने के बाहर हूँ. 571 00:44:19,270 --> 00:44:22,640 हालांकि आप यह पूछना लिखने और fwrite और fread बात की ही तरह है. 572 00:44:22,640 --> 00:44:26,260 वे अपने पढ़ता और लिखता बफर. 573 00:44:26,260 --> 00:44:31,610 भले ही आप यह पूछने के लिए तुरंत लिखना है, यह शायद नहीं होगी. 574 00:44:31,610 --> 00:44:34,540 और आप यकीन है कि चीजें करने के लिए लिखा जा रहा है नहीं किया जा सकता है 575 00:44:34,540 --> 00:44:37,540 जब तक आप hfclose कॉल या जो भी है, 576 00:44:37,540 --> 00:44:39,620 जो कहते हैं, तो ठीक है, मैं मेरी फाइल को बंद कर रहा हूँ, 577 00:44:39,620 --> 00:44:43,450 इसका मतलब है कि मैं बेहतर सब कुछ लिखना चाहते हैं मैं अभी तक नहीं लिखा है. 578 00:44:43,450 --> 00:44:45,770 यह कोई सब कुछ लिखने के लिए बाहर की जरूरत है 579 00:44:45,770 --> 00:44:49,010 जब तक आप फाइल बंद कर रहे हैं, और फिर यह करने की जरूरत है. 580 00:44:49,010 --> 00:44:56,220 तो यह है कि आलसी अभी क्या है - यह इंतजार कर रहा है जब तक यह होता है. 581 00:44:56,220 --> 00:44:59,990 यह 51 ले और आप इसे में और अधिक विस्तार में जाना होगा, 582 00:44:59,990 --> 00:45:05,470 क्योंकि OCaml और 51 में सब कुछ है, सब कुछ recursion है. 583 00:45:05,470 --> 00:45:08,890 कोई समाधान चलने मूल रूप से. 584 00:45:08,890 --> 00:45:11,550 सब कुछ recursion, और आलसी मूल्यांकन 585 00:45:11,550 --> 00:45:14,790 परिस्थितियों का एक बहुत कुछ करने के लिए महत्वपूर्ण होने जा रहा है 586 00:45:14,790 --> 00:45:19,920 , जहां अगर आप lazily मूल्यांकन नहीं किया, इसका मतलब है - 587 00:45:19,920 --> 00:45:24,760 उदाहरण धाराओं, जो असीम रूप से लंबे होते हैं. 588 00:45:24,760 --> 00:45:30,990 सिद्धांत रूप में, आप 1-2-3-4-5-6-7 की एक धारा के रूप में प्राकृतिक संख्या के बारे में सोच सकते हैं, 589 00:45:30,990 --> 00:45:33,090 तो lazily मूल्यांकन चीजों को ठीक कर रहे हैं. 590 00:45:33,090 --> 00:45:37,210 अगर मैं कहूँ कि मैं 10 संख्या चाहते हैं, तो मैं 10 नंबर करने के लिए मूल्यांकन कर सकते हैं. 591 00:45:37,210 --> 00:45:40,300 यदि मैं सौवां संख्या चाहते हैं, तो मैं सौवां संख्या का मूल्यांकन कर सकते हैं. 592 00:45:40,300 --> 00:45:46,290 आलसी मूल्यांकन के बिना, तो यह करने के लिए सभी नंबरों को तुरंत मूल्यांकन करने की कोशिश करने जा रहा है. 593 00:45:46,290 --> 00:45:50,000 आप कई infinitely संख्या का मूल्यांकन कर रहे हैं, और कहा कि अभी संभव नहीं है. 594 00:45:50,000 --> 00:45:52,080 तो परिस्थितियों का एक बहुत कुछ कर रहे हैं, जहां आलसी मूल्यांकन 595 00:45:52,080 --> 00:45:57,840 बस चीजों को काम करने के लिए हो रही करने के लिए आवश्यक है. 596 00:45:57,840 --> 00:46:05,260 >> अब हम डालने लिखने के लिए जहां डालने के लिए होने जा रहा है 597 00:46:05,260 --> 00:46:08,430 इसी तरह अपनी परिभाषा में बदल रहा है. 598 00:46:08,430 --> 00:46:10,470 इसलिए अभी यह bool डालने (int मूल्य) है. 599 00:46:10,470 --> 00:46:23,850 हम bool डालने (int मूल्य, नोड * पेड़) बदलने के लिए जा रहे हैं. 600 00:46:23,850 --> 00:46:29,120 हम वास्तव में एक बिट में है कि फिर से बदलने के लिए जा रहे हैं, हम क्यों देखेंगे. 601 00:46:29,120 --> 00:46:32,210 और चलो build_node बस की बिल्ली के लिए ले जाने के लिए, 602 00:46:32,210 --> 00:46:36,730 ऊपर डालें तो हम एक समारोह प्रोटोटाइप लिखना नहीं है. 603 00:46:36,730 --> 00:46:42,450 जो एक संकेत है कि आप डालने में build_node का उपयोग किया जा रहे हैं. 604 00:46:42,450 --> 00:46:49,590 ठीक है. उस के लिए एक मिनट ले लो. 605 00:46:49,590 --> 00:46:52,130 मुझे लगता है कि मैं संशोधन बचाया अगर आप उस से खींच चाहते हैं, 606 00:46:52,130 --> 00:47:00,240 या कम से कम, मैं अब किया. 607 00:47:00,240 --> 00:47:04,190 मैं एक मामूली डालने के तर्क के बारे में सोचने के लिए तोड़ना चाहता था, 608 00:47:04,190 --> 00:47:08,750 अगर आप इसके बारे में नहीं सोच सकते हैं. 609 00:47:08,750 --> 00:47:12,860 असल में, आप केवल कभी पत्तियों में डालने जाएगा. 610 00:47:12,860 --> 00:47:18,640 की तरह, अगर मैं 1 डालने, तो मैं निश्चित रूप से 1 डालने जा रहा हूँ - 611 00:47:18,640 --> 00:47:21,820 मैं काला करने के लिए बदल देंगे - I'll यहाँ पर 1 डालने. 612 00:47:21,820 --> 00:47:28,070 या अगर मैं 4 सम्मिलित करते हैं, मैं यहाँ पर 4 डालने होना चाहता हूँ. 613 00:47:28,070 --> 00:47:32,180 तो कोई फर्क नहीं पड़ता कि तुम क्या करते हो, आप एक पत्ता में सम्मिलित होने जा रहे हैं. 614 00:47:32,180 --> 00:47:36,130 सब तुम्हें क्या करना है है नीचे पेड़ पुनरावृति जब तक आप नोड के लिए मिलता है 615 00:47:36,130 --> 00:47:40,890 कि नोड के माता पिता, नए नोड के माता पिता होना चाहिए, 616 00:47:40,890 --> 00:47:44,560 और फिर छोड़ दिया है या सही सूचक बदलने के लिए, इस बात पर निर्भर करता है 617 00:47:44,560 --> 00:47:47,060 यह से अधिक है या कम से कम वर्तमान नोड है. 618 00:47:47,060 --> 00:47:51,180 अपने नए नोड को इंगित करने के लिए कि सूचक बदलो. 619 00:47:51,180 --> 00:48:05,490 तो नीचे पेड़ पुनरावृति, नए नोड पत्ती बिंदु बनाते हैं. 620 00:48:05,490 --> 00:48:09,810 इसके अलावा, क्यों कि इससे पहले कि स्थिति के प्रकार मनाही के बारे में सोचते हैं, 621 00:48:09,810 --> 00:48:17,990 जहां मैं द्विआधारी पेड़ का निर्माण जहां यह सही था 622 00:48:17,990 --> 00:48:19,920 अगर आप केवल एक नोड को देखा, 623 00:48:19,920 --> 00:48:24,830 लेकिन 9 7 की बाईं करने के लिए किया गया था यदि आप नीचे सभी तरह दोहराया. 624 00:48:24,830 --> 00:48:29,770 इसलिए कि इस परिदृश्य में असंभव है क्योंकि, 625 00:48:29,770 --> 00:48:32,530 लगता है के बारे में 9 या कुछ डालने, बहुत पहले नोड पर, 626 00:48:32,530 --> 00:48:35,350 मैं 7 देखने के लिए जा रहा हूँ और मैं सिर्फ सही करने के लिए जा रहा हूँ. 627 00:48:35,350 --> 00:48:38,490 तो कोई फर्क नहीं पड़ता कि मुझे क्या करना है, अगर मैं एक पत्ता जाकर सम्मिलित कर रहा हूँ, 628 00:48:38,490 --> 00:48:40,790 और एक उपयुक्त एल्गोरिथ्म का उपयोग कर पत्ती, 629 00:48:40,790 --> 00:48:43,130 यह करने के लिए असंभव हो सकता है मेरे लिए 9 7 की बाईं डालने के लिए जा रहा है 630 00:48:43,130 --> 00:48:48,250 क्योंकि जैसे ही के रूप में मैं 7 मारा मैं सही करने के लिए जा रहा हूँ. 631 00:48:59,740 --> 00:49:02,070 किसी को भी करता है के साथ शुरू करने के लिए कुछ है? 632 00:49:02,070 --> 00:49:05,480 [छात्र] मुझे क्या करना है. ज़रूर. >> 633 00:49:05,480 --> 00:49:09,200 [छात्र, unintelligible] 634 00:49:09,200 --> 00:49:14,390 [अन्य छात्र, unintelligible] 635 00:49:14,390 --> 00:49:18,330 [Bowden] यह सराहना की है. ठीक है. समझाना चाहते हैं? 636 00:49:18,330 --> 00:49:20,690 >> [छात्र] के बाद से हम जानते हैं कि हम डालने थे 637 00:49:20,690 --> 00:49:24,060 पेड़ के अंत में नई नोड्स, 638 00:49:24,060 --> 00:49:28,070 मैं पेड़ के माध्यम से iteratively looped 639 00:49:28,070 --> 00:49:31,360 जब तक मैं एक नोड कि अशक्त ओर इशारा करने के लिए मिला है. 640 00:49:31,360 --> 00:49:34,220 और फिर मैं यह दाईं ओर या बाईं ओर भी डाल करने का फैसला किया 641 00:49:34,220 --> 00:49:37,420 यह सही चर का उपयोग कर रहा है, यह मुझे बताया यह डाल दिया, जहां. 642 00:49:37,420 --> 00:49:41,850 और फिर, अनिवार्य रूप से, मैं सिर्फ कि पिछले बनाया - 643 00:49:41,850 --> 00:49:47,520 नए नोड का निर्माण किया गया है कि यह है कि अस्थायी नोड बिंदु, 644 00:49:47,520 --> 00:49:50,770 या तो बाईं ओर या दाईं ओर, मूल्य क्या सही था पर निर्भर करता है. 645 00:49:50,770 --> 00:49:56,530 अंत में, मैं नए नोड अपने परीक्षण के मूल्य के लिए मूल्य निर्धारित किया है. 646 00:49:56,530 --> 00:49:59,550 [Bowden] ठीक है, तो मैं एक मुद्दा यहाँ देखें. 647 00:49:59,550 --> 00:50:02,050 यह वहाँ रास्ते से 95% की तरह है. 648 00:50:02,050 --> 00:50:07,550 एक मुद्दा यह है कि मैं देख रहा हूँ, ठीक है, किसी और को एक मुद्दा देख नहीं है? 649 00:50:07,550 --> 00:50:18,400 परिस्थिति है जिसके तहत वे पाश से बाहर तोड़ने के क्या है? 650 00:50:18,400 --> 00:50:22,100 [छात्र] यदि अस्थायी अशक्त है? >> हाँ. तो कैसे आप लूप के बाहर तोड़ अगर अस्थायी अशक्त है. 651 00:50:22,100 --> 00:50:30,220 लेकिन मैं सही यहाँ क्या करते हो? 652 00:50:30,220 --> 00:50:35,410 मैं भिन्नता अस्थायी है, जो अनिवार्य रूप से अशक्त है. 653 00:50:35,410 --> 00:50:39,840 तो अन्य बात तुम क्या करने की जरूरत नहीं है सिर्फ ट्रैक रखने जब तक अस्थायी अशक्त है, 654 00:50:39,840 --> 00:50:45,590 आप करने के लिए माता पिता के सभी समय पर नज़र रखना चाहते हैं. 655 00:50:45,590 --> 00:50:52,190 हम भी नोड * माता - पिता चाहते हैं, मुझे लगता है कि हम पहली बार में अशक्त पर रख सकते हैं. 656 00:50:52,190 --> 00:50:55,480 इस पेड़ की जड़ के लिए अजीब व्यवहार किया जा रहा है, 657 00:50:55,480 --> 00:50:59,210 लेकिन हम है कि मिल जाएगा. 658 00:50:59,210 --> 00:51:03,950 यदि मूल्य जो भी अधिक है, तो अस्थायी अस्थायी = सही. 659 00:51:03,950 --> 00:51:07,910 लेकिन इससे पहले कि हम जानते हैं कि माता - पिता = अस्थायी. 660 00:51:07,910 --> 00:51:14,500 या माता - पिता को हमेशा बराबर अस्थायी जा रहे हैं? मामला है कि? 661 00:51:14,500 --> 00:51:19,560 यदि अस्थायी रिक्त नहीं है, तो मैं करने के लिए नीचे ले जाने के लिए, कोई बात नहीं क्या करने के लिए जा रहा हूँ, 662 00:51:19,560 --> 00:51:24,030 एक नोड है जिसके लिए अस्थायी माता पिता है. 663 00:51:24,030 --> 00:51:27,500 तो माता पिता के लिए अस्थायी हो जा रहा है, और फिर मैं अस्थायी नीचे स्थानांतरित करने के लिए. 664 00:51:27,500 --> 00:51:32,410 अब अस्थायी रिक्त है, लेकिन बात यह है कि अशक्त है के माता पिता के लिए माता - पिता बताते हैं. 665 00:51:32,410 --> 00:51:39,110 तो यहाँ नीचे, मैं सही बराबरहै 1 सेट नहीं करना चाहती. 666 00:51:39,110 --> 00:51:41,300 तो मैं सही करने के लिए ले जाया गया है, यदि ऐसा है तो सही = 1, 667 00:51:41,300 --> 00:51:45,130 और मुझे लगता है कि आप भी करना चाहते हैं - 668 00:51:45,130 --> 00:51:48,530 यदि आप बाईं करने के लिए ले जाने के लिए, आप सही 0 के बराबर सेट करना चाहते हैं. 669 00:51:48,530 --> 00:51:55,950 वरना अगर तुम कभी सही करने के लिए कदम. 670 00:51:55,950 --> 00:51:58,590 तो सही = 0. यदि सही = 1, 671 00:51:58,590 --> 00:52:04,260 अब हम माता पिता सही सूचक newnode बनाना चाहते हैं, 672 00:52:04,260 --> 00:52:08,520 और हम माता - पिता छोड़ दिया सूचक newnode बनाना चाहते. 673 00:52:08,520 --> 00:52:16,850 उस पर सवाल? 674 00:52:16,850 --> 00:52:24,880 ठीक है. तो इस तरह से हम है - ठीक है, वास्तव में, इस कर के बजाय, 675 00:52:24,880 --> 00:52:29,630 हम आधा आप build_node का उपयोग करने के लिए उम्मीद है. 676 00:52:29,630 --> 00:52:40,450 और फिर अगर newnode अशक्त के बराबर होती है, झूठी वापसी. 677 00:52:40,450 --> 00:52:44,170 वह है कि. अब, यह है कि हम क्या तुम क्या करने की उम्मीद है. 678 00:52:44,170 --> 00:52:47,690 >> यह है कि स्टाफ समाधान क्या करना है. 679 00:52:47,690 --> 00:52:52,360 मैं इसके बारे में जाने के "" सही तरीका के रूप में इस से असहमत 680 00:52:52,360 --> 00:52:57,820 लेकिन यह पूरी तरह से ठीक है और यह काम करेगा. 681 00:52:57,820 --> 00:53:02,840 एक बात है कि एक छोटे से अजीब अब ठीक है 682 00:53:02,840 --> 00:53:08,310 अगर पेड़ अशक्त रूप में शुरू होता है, तो हम एक अशक्त पेड़ में गुजरती हैं. 683 00:53:08,310 --> 00:53:12,650 मुझे लगता है कि यह कैसे आप एक अशक्त पेड़ में पारित करने के व्यवहार को परिभाषित करने पर निर्भर करता है. 684 00:53:12,650 --> 00:53:15,490 मुझे लगता है कि अगर आप एक अशक्त पेड़ में पारित 685 00:53:15,490 --> 00:53:17,520 तो एक अशक्त पेड़ में मूल्य डालने 686 00:53:17,520 --> 00:53:23,030 सिर्फ एक पेड़ लौट जाना चाहिए जहां केवल मूल्य कि एक नोड है. 687 00:53:23,030 --> 00:53:25,830 क्या लोगों के साथ सहमत हैं? तुम्हें पता है, अगर तुम चाहते थे सकता है, 688 00:53:25,830 --> 00:53:28,050 अगर तुम एक अशक्त पेड़ में पारित 689 00:53:28,050 --> 00:53:31,320 और आप इसे में एक मान सम्मिलित करना चाहते हैं, तो वापसी झूठी. 690 00:53:31,320 --> 00:53:33,830 यह आप पर निर्भर है कि को परिभाषित. 691 00:53:33,830 --> 00:53:38,320 पहली बात मैं कहा और फिर करने के लिए - 692 00:53:38,320 --> 00:53:40,720 ठीक है, तुम कर रही है कि मुसीबत के लिए जा रहे हैं, क्योंकि 693 00:53:40,720 --> 00:53:44,090 यह आसान हो सकता है अगर हम बात करने के लिए एक वैश्विक सूचक होता था, 694 00:53:44,090 --> 00:53:48,570 लेकिन हम ऐसा नहीं अगर पेड़ अशक्त है, वहाँ कुछ भी नहीं है हम उस बारे में क्या कर सकते हैं. 695 00:53:48,570 --> 00:53:50,960 हम सिर्फ झूठी लौट सकते हैं. 696 00:53:50,960 --> 00:53:52,840 तो मैं डालने बदलने के लिए जा रहा हूँ. 697 00:53:52,840 --> 00:53:56,540 हम तकनीकी रूप से यह सही यहाँ बदल सकता है, 698 00:53:56,540 --> 00:53:58,400 यह बातों पर कैसे iterating है, 699 00:53:58,400 --> 00:54:04,530 लेकिन मैं डालने को बदलने के लिए एक नोड ** पेड़ ले जा रहा हूँ. 700 00:54:04,530 --> 00:54:07,510 डबल संकेत दिए. 701 00:54:07,510 --> 00:54:09,710 इसका क्या मतलब है? 702 00:54:09,710 --> 00:54:12,330 नोड्स के लिए संकेत के साथ काम करने के बजाय, 703 00:54:12,330 --> 00:54:16,690 बात मैं जोड़ तोड़ करने जा रहा हूँ यह सूचक है. 704 00:54:16,690 --> 00:54:18,790 मैं यह सूचक से छेड़छाड़ करने जा रहा हूँ. 705 00:54:18,790 --> 00:54:21,770 मैं संकेत जोड़ तोड़ सीधे जा रहा हूँ. 706 00:54:21,770 --> 00:54:25,760 यह समझ में आता है के बाद से, नीचे के बारे में सोचते हैं - 707 00:54:25,760 --> 00:54:33,340 ठीक है, ठीक है अब इस अंक को अशक्त करने के लिए. 708 00:54:33,340 --> 00:54:38,130 मैं क्या करना चाहते है इस सूचक में हेरफेर करने के लिए अशक्त करने के लिए बात नहीं है. 709 00:54:38,130 --> 00:54:40,970 मैं यह मेरी नई नोड के लिए बात करने के लिए करना चाहते हैं. 710 00:54:40,970 --> 00:54:44,870 अगर मैं सिर्फ संकेत के ट्रैक मेरे संकेत के लिए रखने के लिए, 711 00:54:44,870 --> 00:54:47,840 तो मैं एक माता पिता सूचक का ट्रैक रखने की जरूरत नहीं है. 712 00:54:47,840 --> 00:54:52,640 मैं सिर्फ ट्रैक रखने के लिए देखने के लिए अगर सूचक को अशक्त इशारा कर रहा है, 713 00:54:52,640 --> 00:54:54,580 और अशक्त करने के लिए अगर सूचक इशारा कर रहा है, 714 00:54:54,580 --> 00:54:57,370 इसे बदलने के लिए मैं चाहता हूँ नोड को इंगित करने के लिए. 715 00:54:57,370 --> 00:55:00,070 और मैं इसे बदल के बाद से मैं संकेतक के लिए एक सूचक हो सकता है. 716 00:55:00,070 --> 00:55:02,040 यह अभी देखते हैं. 717 00:55:02,040 --> 00:55:05,470 आप वास्तव में इसे बारी बारी से बहुत आसानी से कर सकते हैं. 718 00:55:05,470 --> 00:55:08,080 क्या हम ऐसा करने के लिए करना चाहते हैं? 719 00:55:08,080 --> 00:55:10,980 हाँ, हम करते हैं. 720 00:55:10,980 --> 00:55:16,790 >> चलो यह recursively देख. 721 00:55:16,790 --> 00:55:24,070 सबसे पहले, हमारे आधार के मामले में क्या होने जा रहा है? 722 00:55:24,070 --> 00:55:29,140 लगभग हमेशा हमारे आधार मामला है, लेकिन वास्तव में, यह मुश्किल की तरह है. 723 00:55:29,140 --> 00:55:34,370 सबसे पहली बात, अगर पेड़ (== रिक्त) 724 00:55:34,370 --> 00:55:37,550 मुझे लगता है कि हम सिर्फ झूठी वापसी करने जा रहे हैं. 725 00:55:37,550 --> 00:55:40,460 यह अपने पेड़ बातिल से अलग है. 726 00:55:40,460 --> 00:55:44,510 यह अपने रूट अशक्त जा रहा है सूचक सूचक है 727 00:55:44,510 --> 00:55:48,360 जिसका अर्थ है कि अपने रूट सूचक मौजूद नहीं है. 728 00:55:48,360 --> 00:55:52,390 तो यहाँ नीचे, अगर मैं 729 00:55:52,390 --> 00:55:55,760 नोड * - हम सिर्फ इस पुनः प्रयोग. 730 00:55:55,760 --> 00:55:58,960 नोड * जड़ = रिक्त, 731 00:55:58,960 --> 00:56:00,730 और फिर मैं जैसे कुछ करके डालने फोन करने के लिए जा रहा हूँ, 732 00:56:00,730 --> 00:56:04,540 रूट में 4 सम्मिलित करें. 733 00:56:04,540 --> 00:56:06,560 तो और जड़, अगर एक जड़ नोड * 734 00:56:06,560 --> 00:56:11,170 और फिर जड़ एक नोड ** होने जा रहा है. 735 00:56:11,170 --> 00:56:15,120 यह वैध है. इस मामले में, पेड़, यहाँ, 736 00:56:15,120 --> 00:56:20,120 या डालने पेड़ रिक्त नहीं है. 737 00:56:20,120 --> 00:56:24,630 यहाँ. ट्री रिक्त नहीं है, पेड़ * अशक्त है, जो ठीक है 738 00:56:24,630 --> 00:56:26,680 क्योंकि अगर * पेड़ रिक्त है, तो मैं इसे में हेरफेर कर सकते हैं 739 00:56:26,680 --> 00:56:29,210 अब मैं क्या यह करने के लिए बात करने के लिए करना चाहते हैं इंगित. 740 00:56:29,210 --> 00:56:34,750 लेकिन अगर पेड़ अशक्त है, इसका मतलब है कि मैं बस यहाँ आए थे और अशक्त कहा. 741 00:56:34,750 --> 00:56:42,710 यह समझ में नहीं पड़ता है. मैं उस के साथ कुछ भी नहीं कर सकते. 742 00:56:42,710 --> 00:56:45,540 यदि पेड़ अशक्त है, झूठी वापसी. 743 00:56:45,540 --> 00:56:48,220 तो मैं मूल रूप से पहले से ही ने कहा कि हमारी असली आधार मामला क्या है. 744 00:56:48,220 --> 00:56:50,580 और कहा कि क्या होने जा रहा है? 745 00:56:50,580 --> 00:56:55,030 [छात्र, unintelligible] 746 00:56:55,030 --> 00:57:00,000 [Bowden] हाँ. तो अगर (* पेड़ == रिक्त). 747 00:57:00,000 --> 00:57:04,520 यह यहाँ पर मामले से संबंधित है 748 00:57:04,520 --> 00:57:09,640 जहां अगर मेरे लाल सूचक सूचक है कि मैं पर ध्यान केंद्रित कर रहा हूँ, 749 00:57:09,640 --> 00:57:12,960 तो जैसे मैं इस सूचक पर ध्यान केंद्रित कर रहा हूँ, अब मैं इस सूचक पर ध्यान केंद्रित कर रहा हूँ. 750 00:57:12,960 --> 00:57:15,150 अब मैं इस सूचक पर ध्यान केंद्रित कर रहा हूँ. 751 00:57:15,150 --> 00:57:18,160 तो अगर मेरे लाल सूचक है, जो मेरे नोड ** है, 752 00:57:18,160 --> 00:57:22,880 कभी - * अगर मेरे लाल सूचक, कभी अशक्त है, 753 00:57:22,880 --> 00:57:28,470 इसका मतलब है कि मैं मामले में जहां मैं एक सूचक है कि अंक पर ध्यान केंद्रित कर रहा हूँ - 754 00:57:28,470 --> 00:57:32,530 यह एक सूचक है कि एक पत्ती के अंतर्गत आता है. 755 00:57:32,530 --> 00:57:41,090 मैं इस सूचक को बदलने के लिए अपने नए नोड करने के लिए बात करना चाहते हैं. 756 00:57:41,090 --> 00:57:45,230 यहाँ पर वापस आ जाओ. 757 00:57:45,230 --> 00:57:56,490 मेरा newnode सिर्फ नोड * n = build_node (मान) हो जाएगा 758 00:57:56,490 --> 00:58:07,300 तो n, n = रिक्त यदि वापसी झूठी. 759 00:58:07,300 --> 00:58:12,600 वरना हम बदल सूचक वर्तमान में क्या इशारा कर रहा है 760 00:58:12,600 --> 00:58:17,830 अब हमारे नव निर्मित नोड को इंगित. 761 00:58:17,830 --> 00:58:20,280 हम वास्तव में है कि यहाँ कर सकते हैं. 762 00:58:20,280 --> 00:58:30,660 N कह के बजाय, हम कहते हैं कि पेड़ * = * पेड़ अगर. 763 00:58:30,660 --> 00:58:35,450 हर कोई है कि समझ में आया? यह संकेत करने के लिए संकेत के साथ काम करके, 764 00:58:35,450 --> 00:58:40,750 हम अशक्त संकेत बदलने के लिए बातें हम उन पर बात करने के लिए करना चाहते हैं के लिए बात कर सकते हैं. 765 00:58:40,750 --> 00:58:42,820 कि हमारे आधार मामला है. 766 00:58:42,820 --> 00:58:45,740 >> अब हमारे पुनरावृत्ति, या हमारे recursion 767 00:58:45,740 --> 00:58:51,430 बहुत अन्य सभी recursions हम कर दिया गया है के लिए इसी तरह की होने जा रहा है. 768 00:58:51,430 --> 00:58:55,830 हम करने के लिए मान सम्मिलित करना चाहते करने के लिए जा रहे हैं, 769 00:58:55,830 --> 00:58:59,040 और अब मैं त्रिगुट फिर से उपयोग के लिए जा रहा हूँ, लेकिन हमारी हालत क्या होने जा रहा है? 770 00:58:59,040 --> 00:59:05,180 क्या यह हम तय करना होगा कि हम करने के लिए छोड़ दिया है या सही जाना चाहते हैं के लिए देख रहे है? 771 00:59:05,180 --> 00:59:07,760 चलो यह अलग - अलग चरणों में करते हैं. 772 00:59:07,760 --> 00:59:18,850 यदि (मूल्य) क्या है? 773 00:59:18,850 --> 00:59:23,200 [छात्र] पेड़ मूल्य? 774 00:59:23,200 --> 00:59:27,490 [Bowden] इतना याद है कि मैं वर्तमान में हूँ - 775 00:59:27,490 --> 00:59:31,260 [छात्रों, unintelligible] 776 00:59:31,260 --> 00:59:34,140 [Bowden] हाँ, तो ठीक है यहाँ, चलो का कहना है कि इस हरी तीर 777 00:59:34,140 --> 00:59:39,050 पेड़ क्या वर्तमान का एक उदाहरण है, इस सूचक के लिए एक सूचक है. 778 00:59:39,050 --> 00:59:46,610 तो इसका मतलब है कि मैं 3 करने के लिए एक संकेतक के लिए एक सूचक हूँ. 779 00:59:46,610 --> 00:59:48,800 भिन्नता दो बार अच्छा लग रहा था. 780 00:59:48,800 --> 00:59:51,010 मैं क्या - मैं कैसे है कि क्या करते हो? 781 00:59:51,010 --> 00:59:53,210 [छात्र] एक बार भिन्नता है, और फिर करना तीर तरीका है कि? 782 00:59:53,210 --> 00:59:58,420 तो [Bowden] (* पेड़) भिन्नता है, एक बार मूल्य> 783 00:59:58,420 --> 01:00:05,960 मुझे कि मैं परोक्ष रूप से इशारा कर रहा हूँ नोड के मूल्य देने के लिए जा रहा है. 784 01:00:05,960 --> 01:00:11,980 तो मैं भी इसे लिखने tree.value ** अगर आपको लगता है कि पसंद करते हैं कर सकते हैं. 785 01:00:11,980 --> 01:00:18,490 या तो काम करता है. 786 01:00:18,490 --> 01:00:26,190 यदि यह मामला है, तो मैं मूल्य के साथ डालने कॉल करने के लिए करना चाहते हैं. 787 01:00:26,190 --> 01:00:32,590 और मेरे अद्यतन नोड ** होने जा रहा है? 788 01:00:32,590 --> 01:00:39,440 मैं बाईं करने के लिए जाना चाहते हैं, तो ** tree.left मेरे बाएँ होने जा रहा है. 789 01:00:39,440 --> 01:00:41,900 और मुझे लगता है कि बात करने के लिए सूचक चाहते 790 01:00:41,900 --> 01:00:44,930 इतना है कि अगर छोड़ दिया शून्य सूचक की जा रही समाप्त होता है, 791 01:00:44,930 --> 01:00:48,360 मैं इसे संशोधित करने के लिए अपने नए नोड के लिए बात कर सकते हैं. 792 01:00:48,360 --> 01:00:51,460 >> और अन्य मामले बहुत ही इसी तरह की हो सकती है. 793 01:00:51,460 --> 01:00:55,600 चलो वास्तव में सही है कि अब मेरी त्रिगुट. 794 01:00:55,600 --> 01:01:04,480 यदि मान <(** पेड़). मूल्य मूल्य डालें. 795 01:01:04,480 --> 01:01:11,040 तो फिर हम करने के लिए छोड़ दिया करने के लिए हमारे ** अद्यतन करना चाहते हैं, 796 01:01:11,040 --> 01:01:17,030 और हम सही करने के लिए हमारे ** अद्यतन करना चाहते हैं. 797 01:01:17,030 --> 01:01:22,540 [छात्र] कि सूचक सूचक के लिए क्या मिलता है? 798 01:01:22,540 --> 01:01:30,940 [Bowden] याद रखें कि - ** tree.right एक नोड सितारा है. 799 01:01:30,940 --> 01:01:35,040 [छात्र, unintelligible] >> हाँ. 800 01:01:35,040 --> 01:01:41,140 ** Tree.right इस सूचक या कुछ और की तरह है. 801 01:01:41,140 --> 01:01:45,140 इसलिए कि एक सूचक लेने के द्वारा, कि मुझे देता है मैं क्या चाहता हूँ 802 01:01:45,140 --> 01:01:50,090 उस आदमी के लिए सूचक की. 803 01:01:50,090 --> 01:01:54,260 [छात्र] हम पर फिर से जा सकते हैं इसलिए हम दो संकेत का उपयोग कर रहे हैं? 804 01:01:54,260 --> 01:01:58,220 [Bowden] हाँ. - तो नहीं, आप, और है कि समाधान कर सकते हैं पहले 805 01:01:58,220 --> 01:02:04,540 यह दो संकेत कर के बिना करने का एक तरीका था. 806 01:02:04,540 --> 01:02:08,740 आप दो संकेत का उपयोग को समझने में सक्षम होने की जरूरत है, 807 01:02:08,740 --> 01:02:11,660 और यह एक स्वच्छ समाधान है. 808 01:02:11,660 --> 01:02:16,090 इसके अलावा, सूचना है कि, क्या होता है अगर मेरी पेड़ - 809 01:02:16,090 --> 01:02:24,480 क्या होता है अगर मेरी जड़ अशक्त था? क्या होता है अगर मैं इस मामले को सही यहाँ करते हैं? 810 01:02:24,480 --> 01:02:30,540 तो नोड जड़ * = रिक्त, 4 रूट में सम्मिलित करें. 811 01:02:30,540 --> 01:02:35,110 जड़ क्या इस के बाद होने जा रहा है? 812 01:02:35,110 --> 01:02:37,470 [छात्र, unintelligible] >> हाँ. 813 01:02:37,470 --> 01:02:41,710 रूट मूल्य 4 होने जा रहा है. 814 01:02:41,710 --> 01:02:45,510 जड़ बाईं अशक्त होने जा रहा है, जड़ सही अशक्त होने जा रहा है. 815 01:02:45,510 --> 01:02:49,490 मामले में हम जड़ जहां पते द्वारा पारित नहीं किया था, 816 01:02:49,490 --> 01:02:52,490 हम जड़ को संशोधित नहीं कर सकता है. 817 01:02:52,490 --> 01:02:56,020 मामले में जहां पेड़ - जहां जड़ अशक्त था, 818 01:02:56,020 --> 01:02:58,410 हम सिर्फ झूठी लौटना पड़ा. हम कुछ नहीं कर सकता है. 819 01:02:58,410 --> 01:03:01,520 हम एक खाली पेड़ में एक नोड नहीं डाल सकते. 820 01:03:01,520 --> 01:03:06,810 लेकिन अब हम कर सकते हैं, हम सिर्फ एक नोड एक पेड़ में एक खाली पेड़ बना. 821 01:03:06,810 --> 01:03:13,400 जो आम तौर पर उम्मीद की तरह है कि यह काम करने वाला है. 822 01:03:13,400 --> 01:03:21,610 >> इसके अलावा, इस तुलना में काफी कम है 823 01:03:21,610 --> 01:03:26,240 माता पिता का ट्रैक रखने, और तो आप नीचे सभी तरह पुनरावृति. 824 01:03:26,240 --> 01:03:30,140 अब मैं अपने माता पिता है, और मैं सिर्फ अपने माता - पिता सही जो कुछ भी करने के लिए सूचक है. 825 01:03:30,140 --> 01:03:35,640 इसके बजाय, अगर हम इस iteratively किया, यह एक समय पाश के साथ एक ही विचार होना चाहते हैं. 826 01:03:35,640 --> 01:03:38,100 लेकिन मेरे माता पिता सूचक के साथ सौदा करने के बजाय, 827 01:03:38,100 --> 01:03:40,600 बजाय मेरे वर्तमान सूचक बात होगी 828 01:03:40,600 --> 01:03:43,790 कि मैं सीधे अपने नए नोड को इंगित करने के लिए संशोधित कर रहा हूँ. 829 01:03:43,790 --> 01:03:46,090 मैं चाहे वह बाईं ओर इशारा करते है के साथ सौदा नहीं है. 830 01:03:46,090 --> 01:03:48,810 मैं क्या यह सही है की ओर इशारा करते है के साथ सौदा नहीं है. 831 01:03:48,810 --> 01:04:00,860 यह बस है जो कुछ भी यह सूचक, मैं इसे स्थापित करने के अपने नए नोड करने के लिए बात कर रहा हूँ जा रहा है. 832 01:04:00,860 --> 01:04:05,740 हर कोई समझ है कि यह कैसे काम करता है? 833 01:04:05,740 --> 01:04:09,460 यदि नहीं तो हम इसे इस तरह से क्यों करना चाहते हो, 834 01:04:09,460 --> 01:04:14,920 लेकिन कम से कम है कि एक समाधान के रूप में यह काम करता है? 835 01:04:14,920 --> 01:04:17,110 [छात्र] हम सच कहां लौटा? 836 01:04:17,110 --> 01:04:21,550 [Bowden] कि शायद यहीं पर है. 837 01:04:21,550 --> 01:04:26,690 अगर हम सही ढंग से इसे डालने, सच वापसी. 838 01:04:26,690 --> 01:04:32,010 वरना, नीचे यहाँ हम करने के लिए जो कुछ भी डालने रिटर्न वापसी करना चाहते जा रहे हैं. 839 01:04:32,010 --> 01:04:35,950 >> और इस पुनरावर्ती समारोह के बारे में क्या खास है? 840 01:04:35,950 --> 01:04:43,010 यह पुनरावर्ती पूंछ है, इसलिए जब तक हम कुछ अनुकूलन के साथ संकलन, 841 01:04:43,010 --> 01:04:48,060 यह है कि पहचान और आप इस से एक ढेर अतिप्रवाह कभी नहीं मिल जाएगा, 842 01:04:48,060 --> 01:04:53,230 भले ही हमारे पेड़ 10,000 या 10 लाख की एक ऊंचाई है. 843 01:04:53,230 --> 01:04:55,630 [छात्र, unintelligible] 844 01:04:55,630 --> 01:05:00,310 [Bowden] मुझे लगता है कि यह डैश में करता है - या क्या अनुकूलन स्तर 845 01:05:00,310 --> 01:05:03,820 एक पूंछ recursion के लिए मान्यता प्राप्त होना आवश्यक है. 846 01:05:03,820 --> 01:05:09,350 मुझे लगता है कि इसे पहचानता - जीसीसी और बजना 847 01:05:09,350 --> 01:05:12,610 भी उनके अनुकूलन स्तर के लिए अलग अलग अर्थ है. 848 01:05:12,610 --> 01:05:17,870 मैं कहना है कि यह यकीन है कि यह पूंछ recursion पहचान के लिए 2, DashO चाहते हैं. 849 01:05:17,870 --> 01:05:27,880 लेकिन हम - आप एक Fibonocci उदाहरण या कुछ तरह का निर्माण कर सकता है. 850 01:05:27,880 --> 01:05:30,030 यह इस के साथ परीक्षण करने के लिए आसान नहीं है, क्योंकि यह मुश्किल है निर्माण करने के लिए 851 01:05:30,030 --> 01:05:32,600 एक द्विआधारी पेड़ है कि इतनी बड़ी है. 852 01:05:32,600 --> 01:05:37,140 लेकिन हाँ, मुझे लगता है कि यह 2 DashO, कि 853 01:05:37,140 --> 01:05:40,580 अगर आप 2 DashO के साथ संकलन, यह पूंछ recursion लिए देखो 854 01:05:40,580 --> 01:05:54,030 और अनुकूलन है कि बाहर. 855 01:05:54,030 --> 01:05:58,190 वापस करने के लिए जाने - डालें सचमुच आखिरी बात यह की जरूरत है. 856 01:05:58,190 --> 01:06:04,900 चलो यहाँ पर डालने के लिए वापस जाना 857 01:06:04,900 --> 01:06:07,840 जहां हम एक ही विचार करने के लिए जा रहे हैं. 858 01:06:07,840 --> 01:06:14,340 यह अभी भी पूरी तरह से संभाल करने में सक्षम नहीं किया जा रहा है की दोष होगा 859 01:06:14,340 --> 01:06:17,940 जब जड़ ही रिक्त है, या पिछले प्रविष्टि शून्य है, 860 01:06:17,940 --> 01:06:20,060 लेकिन बजाय एक माता पिता सूचक के साथ निपटने की, 861 01:06:20,060 --> 01:06:27,430 चलो संकेत संकेत रखने का एक ही तर्क लागू. 862 01:06:27,430 --> 01:06:35,580 यहाँ अगर हम हमारे नोड ** चालू रखने के लिए, 863 01:06:35,580 --> 01:06:37,860 और हम का ट्रैक रखने के सही अब जरूरत नहीं है, 864 01:06:37,860 --> 01:06:47,190 लेकिन नोड चालू ** = पेड़ और. 865 01:06:47,190 --> 01:06:54,800 और अब हमारे जबकि पाश जबकि * चालू बराबर रिक्त नहीं करता जा रहा है. 866 01:06:54,800 --> 01:07:00,270 माता पिता का ट्रैक अब रखने की ज़रूरत नहीं है. 867 01:07:00,270 --> 01:07:04,180 छोड़ दिया और सही का ट्रैक रखने की जरूरत नहीं है. 868 01:07:04,180 --> 01:07:10,190 और मैं इसे अस्थायी फोन है, क्योंकि हम पहले से ही अस्थायी का उपयोग कर रहे हैं. 869 01:07:10,190 --> 01:07:17,200 ठीक है. तो अगर (मूल्य> * अस्थायी), 870 01:07:17,200 --> 01:07:24,010 और फिर (* अस्थायी) - ठीक है> 871 01:07:24,010 --> 01:07:29,250 अन्यथा अस्थायी = & (* अस्थायी) -> छोड़ दिया. 872 01:07:29,250 --> 01:07:32,730 और अब, इस बिंदु पर, इस जबकि पाश के बाद, 873 01:07:32,730 --> 01:07:36,380 मैं केवल यह नहीं है क्योंकि शायद यह आसान है के बारे में iteratively recursively की तुलना में लगता है, 874 01:07:36,380 --> 01:07:39,010 लेकिन इस जबकि पाश के बाद, 875 01:07:39,010 --> 01:07:43,820 * अस्थायी सूचक हम बदलना चाहते है. 876 01:07:43,820 --> 01:07:48,960 >> इससे पहले कि हम माता पिता था, और हम या तो माता - पिता छोड़ दिया है या सही माता पिता को बदलना चाहते थे, 877 01:07:48,960 --> 01:07:51,310 लेकिन अगर हम करने के लिए माता पिता सही बदलना चाहते हैं, 878 01:07:51,310 --> 01:07:54,550 फिर * अस्थायी माता पिता का अधिकार है, और हम इसे सीधे बदल सकते हैं. 879 01:07:54,550 --> 01:08:05,860 तो यहाँ नीचे, हम * अस्थायी = newnode करते हैं, कर सकते हैं और यह बात है. 880 01:08:05,860 --> 01:08:09,540 सूचना के तो, हम इस में किया था कोड की लाइनों लेने के लिए गया था. 881 01:08:09,540 --> 01:08:14,770 आदेश में सभी में अपने माता पिता की है कि अतिरिक्त प्रयास का ट्रैक रखने के. 882 01:08:14,770 --> 01:08:18,689 यहाँ, अगर हम सिर्फ सूचक सूचक का ट्रैक रखने के लिए, 883 01:08:18,689 --> 01:08:22,990 और यहां तक ​​कि अगर हम इन सभी घुंघराले ब्रेसिज़ से छुटकारा पाने के लिए अब चाहता था, 884 01:08:22,990 --> 01:08:27,170 यह कम लग रही है. 885 01:08:27,170 --> 01:08:32,529 अब यह सटीक एक ही समाधान है, 886 01:08:32,529 --> 01:08:38,210 लेकिन कोड के कम लाइनों. 887 01:08:38,210 --> 01:08:41,229 एक बार जब आप एक मान्य हल के रूप में यह पहचानने शुरू, 888 01:08:41,229 --> 01:08:43,529 यह भी कारण के बारे में तरह से आसान है, ठीक है, 889 01:08:43,529 --> 01:08:45,779 मैं क्यों int सही पर इस ध्वज है? 890 01:08:45,779 --> 01:08:49,290 इसका क्या मतलब है? ओह, यह वाचक है कि 891 01:08:49,290 --> 01:08:51,370 हर समय मैं सही जाओ, मैं इसे स्थापित करने की आवश्यकता है, 892 01:08:51,370 --> 01:08:53,819 और अगर मैं जाना छोड़ दिया है मैं इसे शून्य करने के लिए सेट की जरूरत है. 893 01:08:53,819 --> 01:09:04,060 यहाँ, मैं उस के बारे में कारण नहीं है, यह सिर्फ आसान है के बारे में सोचते हैं. 894 01:09:04,060 --> 01:09:06,710 प्रश्न? 895 01:09:06,710 --> 01:09:16,290 [छात्र, unintelligible] >> हाँ. 896 01:09:16,290 --> 01:09:23,359 ठीक है, तो पिछले बिट में - 897 01:09:23,359 --> 01:09:28,080 मुझे लगता है कि एक त्वरित और आसान समारोह हम क्या कर सकते है, 898 01:09:28,080 --> 01:09:34,910 let's - साथ मुझे लगता है, कोशिश करते हैं और लिखने के एक समारोह शामिल हैं 899 01:09:34,910 --> 01:09:38,899 जो परवाह नहीं है कि क्या यह एक द्विआधारी खोज वृक्ष है. 900 01:09:38,899 --> 01:09:43,770 यह शामिल समारोह सच लौट जाना चाहिए 901 01:09:43,770 --> 01:09:58,330 अगर यह सामान्य द्विआधारी पेड़ में कहीं भी मूल्य के लिए हम देख रहे हैं. 902 01:09:58,330 --> 01:10:02,520 तो चलो पहले यह recursively करते हैं और फिर हम यह iteratively करूँगा. 903 01:10:02,520 --> 01:10:07,300 हम वास्तव में सिर्फ यह कर सकते हैं एक साथ, क्योंकि यह वास्तव में कम होने जा रहा है. 904 01:10:07,300 --> 01:10:11,510 >> मेरे आधार मामला क्या करने जा रहे हो? 905 01:10:11,510 --> 01:10:13,890 [छात्र, unintelligible] 906 01:10:13,890 --> 01:10:18,230 [Bowden] तो अगर (पेड़ == रिक्त) तो, क्या? 907 01:10:18,230 --> 01:10:22,740 [छात्र] झूठी वापसी. 908 01:10:22,740 --> 01:10:26,160 Bowden [] वरना, ठीक है, मैं और नहीं की जरूरत नहीं है. 909 01:10:26,160 --> 01:10:30,250 अगर मेरे अन्य आधार मामला था. 910 01:10:30,250 --> 01:10:32,450 [छात्र] पेड़ के मूल्य है? >> हाँ. 911 01:10:32,450 --> 01:10:36,430 (पेड़ -> मूल्य == मूल्य. 912 01:10:36,430 --> 01:10:39,920 सूचना हम नोड * वापस आ गए हैं नोड है ** नहीं? 913 01:10:39,920 --> 01:10:42,990 शामिल करने के लिए एक नोड ** का उपयोग करने की जरूरत नहीं होगी, 914 01:10:42,990 --> 01:10:45,480 जब से हम संकेत नहीं संशोधित कर रहे हैं. 915 01:10:45,480 --> 01:10:50,540 हम सिर्फ उन्हें traversing कर रहे हैं. 916 01:10:50,540 --> 01:10:53,830 अगर ऐसा होता है, तो हम सच वापसी करना चाहते हैं. 917 01:10:53,830 --> 01:10:58,270 वरना हम बच्चों को पार करना चाहते हैं. 918 01:10:58,270 --> 01:11:02,620 तो हम क्या छोड़ दिया करने के लिए सब कुछ कम है, के बारे में नहीं कर सकते 919 01:11:02,620 --> 01:11:05,390 और सही करने के लिए सब कुछ अधिक है. 920 01:11:05,390 --> 01:11:09,590 तो हमारी हालत क्या यहाँ होने जा रहा है - या, हम क्या करने जा रहे हैं? 921 01:11:09,590 --> 01:11:11,840 [छात्र, unintelligible] >> हाँ. 922 01:11:11,840 --> 01:11:17,400 वापसी शामिल है (मूल्य, पेड़ -> बाईं) 923 01:11:17,400 --> 01:11:26,860 या (मूल्य, पेड़ -> सही). और यह बात है. 924 01:11:26,860 --> 01:11:29,080 नोटिस और वहाँ कुछ शॉर्ट सर्किट मूल्यांकन है, 925 01:11:29,080 --> 01:11:32,520 जहां अगर हम छोड़ दिया पेड़ में मूल्य मिल होगा, 926 01:11:32,520 --> 01:11:36,820 हम कभी सही पेड़ को देखने की जरूरत है. 927 01:11:36,820 --> 01:11:40,430 कि पूरे समारोह है. 928 01:11:40,430 --> 01:11:43,690 अब यह iteratively करते हैं, 929 01:11:43,690 --> 01:11:48,060 जो कम अच्छा होने जा रहा है. 930 01:11:48,060 --> 01:11:54,750 हम नोड * चालू = पेड़ की सामान्य शुरुआत ले जाऊँगा. 931 01:11:54,750 --> 01:12:03,250 जबकि (चालू = रिक्त). 932 01:12:03,250 --> 01:12:08,600 जल्दी से एक समस्या को देखने के लिए जा रहा है. 933 01:12:08,600 --> 01:12:12,250 यदि चालू - यहाँ, अगर हम कभी भी इस से बाहर तोड़ने, 934 01:12:12,250 --> 01:12:16,020 तो हम बाहर की बातें चला है के लिए देखो, तो वापसी झूठी. 935 01:12:16,020 --> 01:12:24,810 यदि (चालू> मूल्य == मूल्य), सच वापसी. 936 01:12:24,810 --> 01:12:32,910 तो अब, हम एक जगह पर कर रहे हैं - 937 01:12:32,910 --> 01:12:36,250 हम नहीं जानते कि क्या हम छोड़ दिया है या सही जाना चाहते हैं. 938 01:12:36,250 --> 01:12:44,590 तो मनमाने ढंग से, चलो बस जाने के लिए छोड़ दिया. 939 01:12:44,590 --> 01:12:47,910 मैं स्पष्ट रूप से एक मुद्दा है जहाँ मैं पूरी तरह से सब कुछ त्याग दिया है में भाग लिया - 940 01:12:47,910 --> 01:12:50,760 मैं सिर्फ कभी एक पेड़ के बाईं ओर की जाँच करेगा. 941 01:12:50,760 --> 01:12:56,050 मैं कुछ भी है कि कुछ भी की एक सही बच्चा है कभी नहीं की जाँच करेगा. 942 01:12:56,050 --> 01:13:00,910 मैं यह कैसे तय करते हैं? 943 01:13:00,910 --> 01:13:05,260 [छात्र] आप एक ढेर में छोड़ दिया और सही का ट्रैक रखने के लिए किया है. 944 01:13:05,260 --> 01:13:13,710 [Bowden] हाँ. तो चलो इसे बनाने 945 01:13:13,710 --> 01:13:32,360 संरचना सूची, नोड * n, और फिर नोड अगले? ** 946 01:13:32,360 --> 01:13:40,240 मुझे लगता है कि ठीक काम करता है. 947 01:13:40,240 --> 01:13:45,940 ऊपर यहाँ हम पर छोड़ दिया है, या let's जाना चाहते. 948 01:13:45,940 --> 01:13:54,350 Struct सूची सूची =, यह शुरू करेंगे 949 01:13:54,350 --> 01:13:58,170 बाहर इस struct सूची पर. 950 01:13:58,170 --> 01:14:04,040 सूची * = रिक्त. तो यह है कि हमारे लिंक्ड सूची होने जा रहा है 951 01:14:04,040 --> 01:14:08,430 subtrees कि हम पर छोड़ दिया है. 952 01:14:08,430 --> 01:14:13,800 हम अब छोड़ दिया Traverse जा रहे हैं, 953 01:14:13,800 --> 01:14:17,870 लेकिन जब से हम निश्चित रूप से सही करने के लिए वापस आने की जरूरत है, 954 01:14:17,870 --> 01:14:26,140 हम हमारे struct सूची के अंदर सही पक्ष रखने के लिए जा रहे हैं. 955 01:14:26,140 --> 01:14:32,620 फिर हम new_list या struct होगा, 956 01:14:32,620 --> 01:14:41,080 संरचना सूची *, new_list = malloc ((सूची) sizeof). 957 01:14:41,080 --> 01:14:44,920 मैं कि त्रुटि जाँच अनदेखा करने जा रहा हूँ, लेकिन आप अगर यह अशक्त देखने की जाँच करनी चाहिए. 958 01:14:44,920 --> 01:14:50,540 New_list नोड को इंगित करने के लिए जा रहा है - 959 01:14:50,540 --> 01:14:56,890 ओह, यही कारण है कि मैं यह करना चाहता था यहाँ. यह एक दूसरे struct सूची को इंगित करने के लिए जा रहा है. 960 01:14:56,890 --> 01:15:02,380 इसका सिर्फ कैसे सूचियों काम से जुड़े हैं. 961 01:15:02,380 --> 01:15:04,810 यह एक int लिंक सूची के रूप में एक ही है 962 01:15:04,810 --> 01:15:06,960 को छोड़कर हम सिर्फ नोड * के साथ कर रहे हैं int की जगह. 963 01:15:06,960 --> 01:15:11,040 यह बिल्कुल वैसा ही है. 964 01:15:11,040 --> 01:15:15,100 तो new_list, हमारे new_list नोड के मूल्य, 965 01:15:15,100 --> 01:15:19,120 चालू> सही होने जा रहा है. 966 01:15:19,120 --> 01:15:24,280 हमारे मूल्य की new_list> अगले करने के लिए हमारी मूल सूची होने जा रहा है, 967 01:15:24,280 --> 01:15:30,760 और फिर हम हमारी सूची को अद्यतन करने के लिए new_list को इंगित करने के लिए जा रहे हैं. 968 01:15:30,760 --> 01:15:33,650 >> अब हम खींच चीजों में से एक रास्ते के कुछ प्रकार की जरूरत है, 969 01:15:33,650 --> 01:15:37,020 जैसे हम पूरे छोड़ दिया subtree तय किया. 970 01:15:37,020 --> 01:15:40,480 अब हम सामान से बाहर निकलने की जरूरत है, 971 01:15:40,480 --> 01:15:43,850 तरह चालू रिक्त है, हम सिर्फ झूठी वापसी नहीं करना चाहती. 972 01:15:43,850 --> 01:15:50,370 हम अब हमारी नई सूची में बाहर खींच करना चाहते हैं. 973 01:15:50,370 --> 01:15:53,690 ऐसा करने का एक सुविधाजनक तरीका है - ठीक है, वास्तव में, वहाँ ऐसा करने के कई तरीके है. 974 01:15:53,690 --> 01:15:56,680 किसी को भी एक सुझाव है? 975 01:15:56,680 --> 01:15:58,790 जहाँ मैं इस या कैसे मैं यह करना चाहिए करना चाहिए? 976 01:15:58,790 --> 01:16:08,010 हम केवल कुछ मिनट है, लेकिन किसी भी सुझाव? 977 01:16:08,010 --> 01:16:14,750 के बजाय एक ही रास्ता है, बजाय हमारी हालत की जा रही है, जबकि 978 01:16:14,750 --> 01:16:17,090 हम वर्तमान में क्या देख रहे हैं रिक्त नहीं है, 979 01:16:17,090 --> 01:16:22,340 बजाय हम करने के लिए जाने के लिए जारी जब तक हमारी सूची में ही रिक्त है करने के लिए जा रहे हैं. 980 01:16:22,340 --> 01:16:25,680 तो अगर हमारी सूची समाप्त होता है अशक्त जा रहा है, 981 01:16:25,680 --> 01:16:30,680 तो हम बाहर की बातें चलाने के लिए के लिए देखो, पर खोज. 982 01:16:30,680 --> 01:16:39,860 लेकिन इसका मतलब है कि हमारी सूची में पहली बात सिर्फ 1 नोड होने जा रहा है. 983 01:16:39,860 --> 01:16:49,730 बहुत पहले की बात है - हम नहीं रह गया है कि देखने की जरूरत है. 984 01:16:49,730 --> 01:16:58,710 तो सूची n> हमारे पेड़ हो जाएगा. 985 01:16:58,710 --> 01:17:02,860 सूची> अगले अशक्त होने जा रहा है. 986 01:17:02,860 --> 01:17:07,580 और अब जबकि सूची बराबर अशक्त नहीं करता है. 987 01:17:07,580 --> 01:17:11,610 Cur हमारी सूची से कुछ खींचने के लिए जा रहा है. 988 01:17:11,610 --> 01:17:13,500 तो बराबर सूची n> चालू करने जा रहा है. 989 01:17:13,500 --> 01:17:20,850 और फिर सूची बराबर सूची n> जा रहा है, या सूची -> अगले. 990 01:17:20,850 --> 01:17:23,480 तो अगर चालू मूल्य मूल्य के बराबर होती है. 991 01:17:23,480 --> 01:17:28,790 अब हम दोनों हमारे सही सूचक जोड़ सकते हैं और हमारे वाम संकेतक 992 01:17:28,790 --> 01:17:32,900 के रूप में लंबे समय के रूप में वे रिक्त नहीं हैं. 993 01:17:32,900 --> 01:17:36,390 यहाँ नीचे, मुझे लगता है कि हम किया जाना चाहिए कि पहली जगह में. 994 01:17:36,390 --> 01:17:44,080 यदि (चालू> सही = रिक्त) 995 01:17:44,080 --> 01:17:56,380 तो हम हमारी सूची में है कि नोड सम्मिलित करने के लिए जा रहे हैं. 996 01:17:56,380 --> 01:17:59,290 यदि (चालू> बाएं), इस अतिरिक्त काम का एक छोटा सा है, लेकिन यह ठीक है. 997 01:17:59,290 --> 01:18:02,690 अगर, (चालू> बाईं = रिक्त) 998 01:18:02,690 --> 01:18:14,310 और हम हमारे लिंक सूची में छोड़ दिया डालने के लिए जा रहे हैं, 999 01:18:14,310 --> 01:18:19,700 और कि यह होना चाहिए. 1000 01:18:19,700 --> 01:18:22,670 हम पुनरावृति - के रूप में लंबे समय के रूप में हम अपनी सूची में कुछ है, 1001 01:18:22,670 --> 01:18:26,640 हम दूसरे को देखने के नोड है. 1002 01:18:26,640 --> 01:18:28,920 तो हम उस नोड पर देखो, 1003 01:18:28,920 --> 01:18:31,390 हम अगले एक करने के लिए हमारी सूची अग्रिम. 1004 01:18:31,390 --> 01:18:34,060 यदि उस नोड मूल्य के लिए हम देख रहे हैं, हम सच्चे लौट सकते हैं. 1005 01:18:34,060 --> 01:18:37,640 वरना हमारे दोनों बाएँ और दाएँ subtrees डालने, 1006 01:18:37,640 --> 01:18:40,510 के रूप में लंबे समय के रूप में वे अशक्त नहीं कर रहे हैं, हमारी सूची में 1007 01:18:40,510 --> 01:18:43,120 इतना है कि हम निश्चित रूप से उन पर जाना. 1008 01:18:43,120 --> 01:18:45,160 तो अगर वे अशक्त नहीं थे, 1009 01:18:45,160 --> 01:18:47,950 अगर हमारी जड़ सूचक दो चीजों के लिए ओर इशारा किया, 1010 01:18:47,950 --> 01:18:51,670 तो पहली बार में हम कुछ बाहर खींच लिया तो हमारी सूची समाप्त होता है अशक्त जा रहा है. 1011 01:18:51,670 --> 01:18:56,890 और फिर हम दो चीजों में वापस डाल दिया है, इसलिए अब हमारी सूची 2 आकार की है. 1012 01:18:56,890 --> 01:19:00,030 तो फिर हम पाश करने के लिए जा रहे हैं वापस ऊपर और हम सिर्फ खींचने के लिए जा रहे हैं, 1013 01:19:00,030 --> 01:19:04,250 हम कहते हैं, हमारे रूट नोड के बाईं सूचक. 1014 01:19:04,250 --> 01:19:07,730 और कहा कि अभी हो रहा रख देती हूँ, हम अंत में सब कुछ खत्म पाशन. 1015 01:19:07,730 --> 01:19:11,280 >> सूचना है कि यह काफी अधिक जटिल था 1016 01:19:11,280 --> 01:19:14,160 पुनरावर्ती समाधान में. 1017 01:19:14,160 --> 01:19:17,260 और मैं कई बार कहा है 1018 01:19:17,260 --> 01:19:25,120 कि पुनरावर्ती समाधान आमतौर पर आम में ज्यादा चलने का समाधान के साथ है. 1019 01:19:25,120 --> 01:19:30,820 यहाँ यह है कि क्या वास्तव में पुनरावर्ती समाधान कर रही है. 1020 01:19:30,820 --> 01:19:36,740 केवल परिवर्तन है कि उलझाव से ढेर का उपयोग करने के बजाय, इस कार्यक्रम के ढेर, 1021 01:19:36,740 --> 01:19:40,840 नोड्स क्या आप अभी भी यात्रा करने के लिए की जरूरत का ट्रैक रखने के अपने रास्ते के रूप में, 1022 01:19:40,840 --> 01:19:45,430 अब आप स्पष्ट रूप से एक लिंक की गई सूची का उपयोग करने के लिए किया है. 1023 01:19:45,430 --> 01:19:49,070 दोनों ही मामलों में आप ट्रैक रखने के नोड क्या अभी भी दौरा किया जाना चाहिए. 1024 01:19:49,070 --> 01:19:51,790 पुनरावर्ती मामले में यह सिर्फ आसान है क्योंकि एक ढेर 1025 01:19:51,790 --> 01:19:57,100 कार्यक्रम ढेर के रूप में आप के लिए लागू है. 1026 01:19:57,100 --> 01:19:59,550 सूचना है कि इस लिंक सूची, यह एक ढेर है. 1027 01:19:59,550 --> 01:20:01,580 जो कुछ भी हम सिर्फ ढेर पर डाल दिया 1028 01:20:01,580 --> 01:20:09,960 तुरंत है कि हम क्या ढेर खींचने के लिए अगली यात्रा के लिए रवाना करने के लिए जा रहे हैं. 1029 01:20:09,960 --> 01:20:14,380 हम समय से बाहर कर रहे हैं, लेकिन किसी भी सवाल? 1030 01:20:14,380 --> 01:20:23,530 [छात्र, unintelligible] 1031 01:20:23,530 --> 01:20:27,790 [Bowden] हाँ. तो अगर हम हमारे लिंक सूची है, 1032 01:20:27,790 --> 01:20:30,150 वर्तमान के इस आदमी को इंगित करने के लिए जा रहा है, 1033 01:20:30,150 --> 01:20:34,690 और अब हम सिर्फ हमारे लिंक की गई सूची को आगे कर रहे हैं इस आदमी पर ध्यान केंद्रित. 1034 01:20:34,690 --> 01:20:44,200 हम उस पंक्ति में लिंक की गई सूची पर traversing रहे हैं. 1035 01:20:44,200 --> 01:20:51,200 और फिर मुझे लगता है कि हम हमारे लिंक्ड सूची और सामान मुक्त करना चाहिए 1036 01:20:51,200 --> 01:20:53,880 एक बार सही है या गलत लौटने से पहले, हमें जरूरत है 1037 01:20:53,880 --> 01:20:57,360 हमारे लिंक सूची पर पुनरावृति और हमेशा यहाँ नीचे, मुझे लगता है, 1038 01:20:57,360 --> 01:21:03,900 अगर हम चालू सही के बराबर नहीं है, यह जोड़ने के लिए, तो अब हम मुक्त करने के लिए करना चाहते हैं 1039 01:21:03,900 --> 01:21:09,600 चालू क्योंकि, ठीक है, हम पूरी तरह से सूची के बारे में भूल जाते हैं? हाँ. 1040 01:21:09,600 --> 01:21:12,880 तो है कि क्या हम यहाँ क्या करना चाहते. 1041 01:21:12,880 --> 01:21:16,730 सूचक कहाँ है? 1042 01:21:16,730 --> 01:21:23,320 चालू तो था - हम चाहते हैं एक struct सूची 10 * सूची अगले बराबर होती है. 1043 01:21:23,320 --> 01:21:29,240 नि: शुल्क सूची, सूची = अस्थायी. 1044 01:21:29,240 --> 01:21:32,820 और मामले में जहां हम वापसी सच, हम पुनरावृति की क्या ज़रूरत है 1045 01:21:32,820 --> 01:21:37,050 हमारे लिंक्ड चीजों को मुक्त कराने सूची के शेष पर. 1046 01:21:37,050 --> 01:21:39,700 पुनरावर्ती समाधान के बारे में अच्छी बात यह बातें मुक्त है 1047 01:21:39,700 --> 01:21:44,930 ढेर है जो आप के लिए होगा बंद popping factorings मतलब है. 1048 01:21:44,930 --> 01:21:50,720 इसलिए हम कुछ है कि मुश्किल से लगता है कि के बारे में कोड की 3 लाइनों की तरह से चले गए 1049 01:21:50,720 --> 01:21:57,520 कुछ उल्लेखनीय है कि कई और अधिक के लिए कड़ी मेहनत करने के लिए लगता है कि के बारे में कोड की लाइनों. 1050 01:21:57,520 --> 01:22:00,620 अधिक कोई सवाल? 1051 01:22:00,620 --> 01:22:08,760 सही सभी. हम अच्छा कर रहे हैं. अलविदा! 1052 01:22:08,760 --> 01:22:11,760 [CS50.TV]