[Powered by Google Translate] [धारा 7: अधिक आरामदायक] [रोब Bowden] [हार्वर्ड विश्वविद्यालय] [यह CS50] [CS50.TV] सही सभी. तो मैं अपने ईमेल में कहा, यह करने के लिए एक द्विआधारी पेड़ गहन अनुभाग होने जा रहा है. लेकिन वहाँ है कि कई सवाल नहीं कर रहे हैं. इसलिए हम कोशिश करते हैं और प्रत्येक प्रश्न आकर्षित करने के लिए जा रहे हैं और बातें करने का सर्वोत्तम तरीकों में से दर्दनाक विस्तार में जाना. तो शुरुआत में ठीक है, हम द्विआधारी पेड़ और सामान के नमूने चित्र के माध्यम से जाना. तो यहाँ, "याद रखें कि एक द्विआधारी पेड़ एक लिंक सूची के उन लोगों के लिए समान नोड्स है, बाईं 'बच्चे' के लिए एक: बजाय एक सूचक के अलावा वहाँ दो हैं और एक सही 'बच्चा' के लिए. " एक द्विआधारी पेड़ तो एक लिंक्ड सूची की तरह ही है, struct को छोड़कर दो संकेत जा रहा है. वहाँ trinary पेड़ है, जो तीन संकेत जा रहे हैं, N-ary पेड़ है, जो सिर्फ एक सामान्य सूचक है कि तुम तो malloc के लिए काफी बड़ा करने के लिए किया है सभी संभव बच्चों को पर्याप्त संकेत. तो द्विआधारी पेड़ सिर्फ दो की एक निरंतर संख्या है होता है. यदि आप चाहते हैं, तो आप एक एकल पेड़ के रूप में एक लिंक सूची दे सकते हैं, लेकिन मुझे नहीं लगता कि किसी को भी यह है कि कॉल. "एक द्विआधारी पेड़ नोड के एक चित्र बक्से और तीर ड्रा युक्त नैट पसंदीदा संख्या, 7, जहां प्रत्येक बच्चे सूचक रिक्त है. " तो iPad मोड. 

यह बहुत सीधा होने जा रहा है. हम सिर्फ एक नोड के लिए जा रहे हैं, मैं इसे एक वर्ग के रूप में आकर्षित करेंगे. और मैं यहाँ में मूल्यों को आकर्षित करेंगे. तो मान में जाना होगा, और फिर नीचे यहाँ हम बाईं तरफ बाईं सूचक और सही पर सही सूचक होगा. और यह बहुत सम्मेलन तो यह बाएँ और दाएँ, सूचक नाम कॉल करने के लिए. इन दोनों के लिए अशक्त होने जा रहे हैं. वह सिर्फ रिक्त हो जाएगा, और कहा कि अभी रिक्त हो जाएगा. ठीक है. तो यहाँ वापस करने के लिए. "एक लिंक की गई सूची के साथ, हम केवल एक सूचक की दुकान थी सूची क्रम में पूरे लिंक की गई सूची को याद करने के लिए, या पूरी सूची में पहला नोड. इसी तरह, पेड़ के साथ, हम केवल एक सूचक की दुकान है क्रम में पूरे पेड़ को याद करने के लिए एक एकल नोड. इस नोड calle पेड़ की जड़ 'है. पहले से अपने चित्र पर निर्माण या एक नया आकर्षित ऐसी है कि आप एक द्विआधारी पेड़ बक्से और तीर का चित्रण है साथ 7 मूल्य, फिर छोड़ दिया में 3, तो सही पर 9, और फिर 6 3 की दाईं तरफ है. " चलो देखते हैं अगर मैं मेरे सिर में है कि सभी को याद कर सकते हैं. तो यह हमारे यहाँ जड़ होने जा रहा है. हम कुछ सूचक कहीं होगा, कुछ है कि हम जड़ फोन करता हूँ, और यह इस आदमी की ओर इशारा करते है. अब एक नया नोड बनाने के लिए, हम क्या है 3 बाईं तरफ? तो 3 के साथ एक नया नोड, और यह शुरू में अशक्त अंक. मैं सिर्फ एन डाल देता हूँ अब हम कि 7 की बाईं करने के लिए जाना चाहते हैं. इसलिए हम इस सूचक को बदलने के लिए अब इस आदमी के लिए बात. और हम भी ऐसा ही. हम यहाँ पर 9 जो शुरू में सिर्फ रिक्त कहते हैं. हम 9 से इस बिंदु, सूचक बदलने के लिए जा रहे हैं, और अब हम सही करने के लिए 3 के 6 डाल करना चाहते हैं. तो यह जा रहा है - एक 6. और उस आदमी को बात करेंगे. ठीक है. तो यह है कि यह हमारे करने के लिए पूछता है. 

अब चलो कुछ शब्दावली पर जाना. हम पहले से ही कैसे पेड़ की जड़ वृक्ष के नोड सर्वोच्च है के बारे में बात की थी. एक 7 युक्त. पेड़ के नीचे नोड्स पत्तियों कहा जाता है. किसी भी नोड है जो सिर्फ अपने बच्चों के रूप में अशक्त है एक पत्ता है. तो यह संभव है, अगर हमारे द्विआधारी पेड़ सिर्फ एक नोड है, कि एक पेड़ के एक पत्ता है, और यह बात है. "पेड़ की 'ऊंचाई' hops आपको करना है की संख्या है ऊपर से एक पत्ती को मिलता है. " हम में मिलता है, एक दूसरे में, अंतर संतुलित और असंतुलित द्विआधारी पेड़ों के बीच, लेकिन अब के लिए, इस पेड़ की कुल ऊंचाई मैं 3 कहते हैं, हालांकि, अगर आप hops की संख्या गिनती आप क्रम में 9 से मिलता है, तो यह वास्तव में केवल 2 की ऊंचाई है. अभी यह एक असंतुलित द्विआधारी पेड़ है, लेकिन हम संतुलित के बारे में बात की थी जब यह प्रासंगिक हो जाता है. तो अब हम इस मामले में एक पेड़ में नोड्स के बारे में बात कर सकते हैं पेड़ में अन्य नोड्स के सापेक्ष. तो अब हम माता पिता, बच्चों, भाई बहन, पूर्वजों और वंश है. वे बहुत आम समझ रहे हैं, वे क्या मतलब है. यह माता - पिता यदि हम पूछना. तो 3 के माता - पिता क्या है? 7 [छात्र]. >> हाँ. माता - पिता हो सकता है क्या आप के लिए अंक जा रहा है. फिर 7 के बच्चों को क्या कर रहे हैं? 3 और 9 [छात्र]. >> हाँ. सूचना है कि "बच्चों" सचमुच बच्चों का मतलब, 6 तो लागू नहीं है, क्योंकि यह एक पोता की तरह होता है. लेकिन फिर अगर हम वंश जाओ, तो 7 की सन्तान क्या कर रहे हैं? 3, 6 और 9 [छात्र]. >> हाँ. रूट नोड की सन्तान पेड़ में सब कुछ होने जा रहा है, सिवाय शायद रूट नोड ही, यदि आप करने के लिए कि एक वंशज पर विचार नहीं करना चाहती. और अंत में, पूर्वजों, तो यह विपरीत दिशा है. तो 6 के पूर्वजों क्या कर रहे हैं? 3 और 7 [छात्र]. >> हाँ. 9 शामिल नहीं है. यह सिर्फ प्रत्यक्ष वंश रूट करने के लिए वापस आ गया है अपने पूर्वजों की जा रही है. 

"हम कहते हैं कि एक द्विआधारी पेड़ पेड़ में प्रत्येक नोड के लिए अगर 'का आदेश दिया' बाईं तरफ उसके वंश के सभी कम मूल्यों है और सही पर लोगों की अधिक से अधिक मूल्यों है. उदाहरण के लिए, ऊपर पेड़ का आदेश दिया है, लेकिन यह तभी संभव आदेश दिया व्यवस्था नहीं है. " इससे पहले कि हम करने के लिए मिलता है, एक आदेश द्विआधारी पेड़ एक द्विआधारी खोज वृक्ष के रूप में भी जाना जाता है. यहाँ हम इसे एक आदेश द्विआधारी पेड़ बुला रहे हो, लेकिन मैं कभी नहीं सुना है यह एक आदेश द्विआधारी पेड़ से पहले कहा जाता है, और एक प्रश्नोत्तरी पर हम और अधिक के लिए द्विआधारी खोज वृक्ष डाल की संभावना हैं. वे एक और एक ही कर रहे हैं, और यह महत्वपूर्ण है कि आप द्विआधारी पेड़ और द्विआधारी खोज वृक्ष के बीच अंतर को समझते हैं. एक द्विआधारी पेड़ सिर्फ एक पेड़ है कि दो चीजों के लिए अंक. प्रत्येक नोड दो बातें करने के लिए कहते हैं. मूल्यों के बारे में कोई तर्क है कि यह करने के लिए अंक है. तो यहाँ पर करना चाहते हैं, क्योंकि यह एक द्विआधारी खोज वृक्ष है, हम जानते हैं कि अगर हम जाओ 7 के छोड़ दिया है, तो सभी मूल्यों है कि हम संभवतः तक पहुँच सकते हैं 7 के छोड़ दिया जा रहा द्वारा 7 से कम हो. सूचना है कि 7 से कम सभी मान 3 और 6. उन 7 की बाईं सभी कर रहे हैं. अगर हम सही करने के लिए 7 के जाओ, सब कुछ करने के लिए 7 से अधिक हो गया है, इतना 9 7 के अधिकार के लिए है, तो हम अच्छा कर रहे हैं. यह एक द्विआधारी पेड़ के लिए मामला नहीं है, एक नियमित द्विआधारी पेड़ के लिए हम सिर्फ ऊपर, बाईं करने के लिए 7 पर 3 हो सकता है, 9 7 की बाईं, वहाँ कोई नहीं है जो मूल्यों के आदेश है. अब, हम वास्तव में यह नहीं करना है क्योंकि यह थकाऊ और अनावश्यक है, लेकिन "के रूप में कई आदेश दिया के पेड़ के रूप में आप के बारे में सोच सकते हैं आकर्षित करने की कोशिश संख्या 7, 3, 9 का उपयोग कर, और 6. कितने अलग व्यवस्था कर रहे हैं? हर एक की ऊंचाई क्या है? " 

हम कुछ करेंगे, लेकिन मुख्य विचार है, यह एक द्विआधारी पेड़ के इन मूल्यों से युक्त एक अद्वितीय प्रतिनिधित्व कोई रास्ता नहीं में है. हम सब की ज़रूरत है कुछ द्विआधारी पेड़ है कि 7 शामिल हैं, 3, 6, और 9 है. एक अन्य संभावित वैध एक रूट 3 होगा, बाईं करने के लिए जाना है और यह 6 है, छोड़ दिया करने के लिए जाना है और यह 7 है, बाईं करने के लिए जाना है और यह 9 है. यह एक पूरी तरह से वैध द्विआधारी खोज वृक्ष है. यह बहुत उपयोगी नहीं है, क्योंकि यह सिर्फ एक लिंक सूची की तरह है और ये संकेत के सभी रिक्त हैं. लेकिन यह एक वैध पेड़ है. हाँ? [छात्र] मूल्यों सही पर अधिक होना नहीं है क्या? या यह है? >> ये मैं दूसरे रास्ते जाने का मतलब है. वहाँ भी है - हाँ, है कि स्विच. 9, 7, 6, 3. अच्छी पकड़. यह अभी भी पालन करने के लिए क्या एक द्विआधारी पेड़ खोज करना चाहिए है. तो छोड़ दिया करने के लिए सब कुछ करने के लिए किसी भी नोड की तुलना में कम हो गया है. हम बस ले जाने के लिए, कह सकते हैं, यह 6 और इसे यहाँ रखा. नहीं, हम नहीं कर सकते. मैं कर रही है कि क्यों रहते हो? चलो करते हैं - यहाँ 6 है, यहाँ 7 है, 3 से 6 अंक है. यह अभी भी एक वैध द्विआधारी खोज वृक्ष है. क्या गलत है अगर मैं - चलो देखते हैं अगर मैं एक व्यवस्था के साथ आ सकते हैं. हाँ, ठीक है. तो इस पेड़ के साथ क्या गलत है? मुझे लगता है कि मैं पहले से ही आप एक संकेत दिया है कि वहाँ के साथ कुछ गड़बड़ है. मैं कर रही है कि क्यों रहते हो? ठीक है. यह उचित लग रहा है. यदि हम प्रत्येक नोड में, 7 की तरह है, तो 7 की बाईं देखो एक 3 है. तो हम 3 है, सही करने के लिए 3 की बात एक 6 है. और अगर आप 6 पर देखो, बात सही करने के लिए 6 की 9. तो यह एक वैध द्विआधारी खोज वृक्ष क्यों नहीं है? 9 [छात्र] 7 की बाईं करने के लिए अभी भी है. >> हाँ. यह सच है कि सभी मूल्यों आप संभवतः 7 की बाईं करने के लिए जा रहा द्वारा पहुँच सकते हैं कम से कम 7 होना चाहिए. अगर हम 7 के छोड़ दिया जाना, हम 3 से मिलता है और हम अभी भी 6 से प्राप्त कर सकते हैं, हम अभी भी 9 से मिल सकता है, लेकिन कम से कम 7 चला गया, हम एक नंबर है कि 7 से अधिक प्राप्त करने में सक्षम नहीं होना चाहिए. तो यह एक वैध द्विआधारी खोज वृक्ष नहीं है. 

मेरा भाई वास्तव में एक साक्षात्कार सवाल था है कि मूल रूप से कुछ करने के लिए मान्य को इस बस कोड था क्या एक पेड़ एक द्विआधारी खोज वृक्ष है, और इसलिए पहली बात यह है कि वह सिर्फ देखने के लिए जाँच अगर छोड़ दिया और सही सही हैं, और फिर वहाँ नीचे पुनरावृति. लेकिन सिर्फ तुम नहीं कर सकते हैं कि करना, आप ट्रैक रखने के लिए है तथ्य यह है कि अब मैं 7 के छोड़ दिया गया है, यह subtree में सब कुछ 7 से कम होना चाहिए. सही एल्गोरिथ्म ट्रैक रखने की जरूरत है, सीमा है कि मूल्यों को संभवतः अंदर गिर सकता है हम उन सभी के माध्यम से नहीं जाऊँगा. वहाँ एक अच्छा पुनरावृत्ति संबंध है, हालांकि हम उन लोगों के लिए नहीं मिल गया है, या हम उन लोगों के लिए नहीं मिलेगा, परिभाषित कितने वहाँ वास्तव में कर रहे हैं. तो वहाँ 14 उनमें से एक हैं. आप इसे कैसे करना होगा विचार गणितीय की तरह है, आप किसी भी एक को लेने के लिए रूट नोड हो सकता है, और फिर अगर मैं 7 लेने के लिए रूट नोड हो, तो वहाँ कुछ कर रहे हैं, कहते हैं, संख्या कि मेरे बाएँ नोड होना जा सकते हैं, और वहाँ कुछ संख्या है कि मेरा अधिकार नोड हो सकता है, लेकिन अगर मैं कुल संख्या n है, तो राशि है कि बाईं करने के लिए जा सकते हैं 1 - प्लस राशि है कि सही करने के लिए जा सकते हैं n है. तो शेष संख्या, वे या तो छोड़ दिया है या सही करने के लिए जाने के लिए सक्षम होना चाहिए. यह मुश्किल लगता है कि, अगर मैं 3 1 तो डाल सब कुछ करने के लिए छोड़ दिया करने के लिए जाना पड़ता है, लेकिन अगर मैं 7 डाल, तो कुछ बातों को छोड़ दिया जाना है और कुछ चीजों को सही करने के लिए जा सकते हैं कर सकते हैं. और मैं '3 1 'से मतलब है, सब कुछ ठीक करने के लिए जा सकते हैं. यह सच है, तो आप सिर्फ इसके बारे में सोचना है, कितनी बातें पेड़ के अगले स्तर पर जा सकते हैं. और यह पता करने के लिए आता है 14 हो, या आप उन सभी को आकर्षित कर सकते हैं, और फिर आप 14 मिलेगा. 

यहाँ वापस जा रहे हैं, "आदेश दिया द्विआधारी पेड़ शांत कर रहे हैं क्योंकि हम उन के माध्यम से खोज कर सकते हैं एक हल सरणी पर खोज करने के लिए एक बहुत ही रास्ते में. ऐसा करने के लिए, हम रूट पर शुरू करने के लिए और पेड़ के नीचे हमारे रास्ते काम पत्तियों की ओर, मानों हम के लिए खोज रहे हैं के खिलाफ प्रत्येक नोड मूल्यों की जाँच. यदि वर्तमान नोड मूल्य मूल्य से कम है कि हम देख रहे हैं, आप नोड सही बच्चे को बगल जाना. अन्यथा, आप नोड छोड़ दिया बच्चे को जाना. कुछ बिंदु पर, आप या तो आप के लिए देख रहे हैं मूल्य मिल जाए, या आप एक अशक्त में भाग लेंगे मूल्य संकेत पेड़ में नहीं है. " मैं पेड़ हम पहले था redraw है, कि एक मिनट लगेगा. लेकिन हम को देखने के लिए कि क्या 6, 10, और 1 पेड़ में करना चाहते हैं. तो यह क्या था, 7, 9, 3, 6. ठीक है. नंबर आप को देखने के लिए करना चाहते हैं, हम करने के लिए 6 देखना चाहता हूँ. कैसे इस एल्गोरिथ्म काम करता है? खैर, हम भी कुछ हमारे पेड़ को जड़ सूचक है. और हम रूट करने के लिए जाना और कहते हैं, इस मूल्य हम के लिए खोज कर रहे हैं बराबर मूल्य है? तो हम 6 के लिए देख रहे हैं, तो यह नहीं के बराबर है. तो हम जा रखने के लिए, और अब हम कह, ठीक है, तो 6 कम से कम 7 है. क्या इसका मतलब हम छोड़ दिया करने के लिए जाना चाहते हैं, या क्या हम सही करने के लिए जाना चाहते हैं? [छात्र] वाम. >> हाँ. यह काफी आसान है, सब तुम्हें क्या करना है एक पेड़ के संभव नोड आकर्षित करने के लिए है और फिर तुम नहींं - के बजाय अपने सिर में सोचने की कोशिश कर रहा है, ठीक है, अगर यह कम है, मैं छोड़ दिया करने के लिए जाना है या ठीक है, जाओ सिर्फ इस तस्वीर को देख रहे हैं, यह बहुत स्पष्ट है कि मैं करने के लिए छोड़ दिया जाना है अगर इस नोड मूल्य है कि मैं देख रहा हूँ से अधिक है. तो तुम छोड़ दिया करने के लिए जाना है, अब मैं 3 पर हूँ. मैं चाहता हूँ - 3 मूल्य के लिए मैं देख रहा हूँ, जो 6 है की तुलना में कम है. तो हम जाने के लिए सही है, और अब मैं 6 पर खत्म होता है, जो मूल्य के लिए मैं देख रहा हूँ, तो मैं वापसी सच है. मैं अगले मूल्य को देखने के लिए जा रहा हूँ 10 है. ठीक है. 10 तो काट दिया है कि - जड़ का पालन करने के लिए जा, अब, के लिए जा रहा है. अब 10, 7 से अधिक होने जा रहा है, तो मैं सही करने के लिए देखना चाहता हूँ. मैं यहाँ आने के लिए जा रहा हूँ 10, 9 से अधिक होने जा रहा है, तो मैं करने के लिए सही करने के लिए देखना चाहता हूँ जा रहा हूँ. मैं यहाँ आते हैं, लेकिन अब यहाँ पर मैं अशक्त पर हूँ. मैं क्या अगर मैं अशक्त मारा करते हो? [छात्र] झूठी वापसी? >> हाँ. मैं 10 नहीं मिला. 1 के लिए लगभग समान मामला होने जा रहा है, सिवाय इसके कि यह सिर्फ फ़्लिप किया जा जा रहा है, के बजाय देख सही पक्ष नीचे, मैं नीचे बाईं ओर देखने के लिए जा रहा हूँ. 

अब मुझे लगता है कि हम वास्तव में कोड करने के लिए मिलता है. यहाँ है जहाँ - CS50 उपकरण खोलने के लिए और अपना रास्ता नेविगेट, लेकिन आप भी अंतरिक्ष में यह सिर्फ कर सकते हैं. यह शायद यह अंतरिक्ष में क्या करने के लिए आदर्श है, क्योंकि हम अंतरिक्ष में काम कर सकते हैं. "सबसे पहले हम एक द्विआधारी पेड़ नोड int मूल्यों से युक्त करने के लिए एक नए प्रकार परिभाषा की आवश्यकता होगी. नीचे typedef बॉयलरप्लेट का प्रयोग, एक द्विआधारी पेड़ में एक नोड के लिए एक नए प्रकार परिभाषा बनाने के लिए. यदि आप अटक जाते हैं. . . "ब्ला ब्ला ब्ला, ठीक है. तो चलो boilerplate यहाँ डाल, typedef struct नोड, और नोड. हाँ, ठीक है. तो खेतों हम हमारे नोड में चाहते करने के लिए जा रहे हैं क्या कर रहे हैं? [छात्र] Int और फिर दो संकेत? >> Int मूल्य, दो संकेत? मैं संकेत कैसे लिख सकता हूँ? [छात्र] Struct. >> मैं अंदर ज़ूम हाँ, तो struct नोड छोड़ * और संरचना नोड सही *. और पिछली बार से चर्चा याद है, कि यह नहीं समझ में आता है, यह नहीं समझ में आता है, यह नहीं समझ में आता. तुम वहाँ सब कुछ की जरूरत है ताकि इस पुनरावर्ती struct को परिभाषित. ठीक है, ताकि हमारे पेड़ की तरह लग रहा है. यदि हम एक trinary पेड़ किया, तो एक नोड B1, B2, संरचना नोड b3 * की तरह लग सकता है, जहां ख एक शाखा है - वास्तव में, मैं और अधिक सुना है इसे छोड़ दिया, मध्यम, सही है, लेकिन जो कुछ भी. हम केवल द्विआधारी के बारे में परवाह है, तो ठीक है, छोड़ दिया. "अब पेड़ की जड़ के लिए एक वैश्विक नोड * चर घोषित कर दिया." तो हम ऐसा करने के लिए नहीं जा रहे हैं. आदेश में चीजों को थोड़ा और अधिक कठिन और अधिक सामान्यकृत बनाने के लिए, हम एक वैश्विक नोड चर नहीं होगा. इसके बजाय, मुख्य में हम हमारे सभी नोड बातें की घोषणा करेंगे, और वह है कि नीचे का मतलब है, जब हम चल रहे शुरू हमारे शामिल हैं समारोह और हमारे डालने समारोह, हमारे होता है की बजाय सिर्फ इस वैश्विक नोड चर का उपयोग कर समारोह, हम यह एक तर्क के रूप में पेड़ ले जा रहे हैं कि हम यह प्रक्रिया करने के लिए करना चाहते हैं. वैश्विक चर के बाद चीजों को आसान बनाने के लिए चाहिए था. हम चीजों को कठिन बनाने के लिए जा रहे हैं. अब या तो एक मिनट के लेने के लिए इस तरह की बात करने के लिए बस, जहां अंदर मुख्य आप इस पेड़ बनाने चाहते हैं, और कि आप सब करना चाहते हैं. कोशिश करते हैं और अपने मुख्य समारोह में इस पेड़ का निर्माण. 

ठीक है. तो तुम भी पेड़ पूरी तरह से निर्माण किया है अभी तक नहीं है. लेकिन किसी को भी कुछ मैं खींच सकता है दिखाने के लिए कैसे एक इस तरह के एक पेड़ के निर्माण शुरू हो सकता है? [छात्र] किसी की पिटाई, बाहर निकलने की कोशिश. [Bowden] अपने पेड़ के निर्माण के साथ सहज कोई है? [छात्र] ज़रूर. यह नहीं किया है. >> यह ठीक है. हम बस खत्म कर सकते हैं - ओह, आप इसे बचा सकते हैं? हुर्रे. यहाँ तो हम है - ओह, मैं थोड़ा दूर काट रहा हूँ. मैं कर रहा हूँ में तेजी से बढ़ी है? में ज़ूम, स्क्रॉल. >> मैं एक सवाल है. >> हाँ? [छात्र] जब आप struct को परिभाषित, initialized की तरह कुछ भी करने के लिए बातें कर रहे हैं? [Bowden] नहीं >> ठीक है. तो आप इनिशियलाइज़ करना होगा - [Bowden] नहीं, जब आप को परिभाषित करने के लिए, या जब आप की घोषणा एक struct यह डिफ़ॉल्ट रूप से प्रारंभ नहीं किया है, यह सिर्फ अगर तुम एक int घोषित करना है. यह वास्तव में एक ही बात है. यह अपनी व्यक्तिगत क्षेत्रों में से प्रत्येक की तरह है उस में एक कचरा मूल्य हो सकता है. >> और यह संभव को परिभाषित करने की घोषणा करने के लिए एक struct उन्हें एक तरीका है कि यह करता है में हस्ताक्षर? [Bowden] हाँ. तो, शॉर्टकट initialization वाक्यविन्यास की तरह लग रहा है - वहाँ दो तरीकों से हम यह कर सकते है. मुझे लगता है कि हम यह संकलन चाहिए यकीन है कि बजना बनाने के लिए भी करता है. तर्कों के आदेश है कि struct में आता है, आप इन घुंघराले ब्रेसिज़ के अंदर बहस के आदेश के रूप में डाल दिया. तो अगर आप यह 9 इनिशियलाइज़ चाहते हैं और छोड़ दिया तो सही अशक्त और अशक्त हो सकता है, यह 9, अशक्त, अशक्त होगा. विकल्प है, और संपादक इस वाक्यविन्यास पसंद नहीं करता है, और यह सोचता है कि मैं एक नया खंड चाहते हैं, लेकिन विकल्प की तरह कुछ है - यहाँ, मैं इसे एक नई लाइन पर डाल देता हूँ. आप स्पष्ट रूप से कह सकते हैं, मैं सटीक वाक्यविन्यास भूल जाते हैं. तो आप स्पष्ट रूप से उनके नाम से पता कर सकते हैं, और कहते हैं, ग, या. मूल्य = 9, बाएँ रिक्त =. मैं इन अल्पविराम होने की जरूरत लग रहा है. सही = रिक्त तो, इस तरह तुम नहीं वास्तव में struct के आदेश पता करने की आवश्यकता है, और जब आप यह पढ़ रहे हैं, यह बहुत अधिक स्पष्ट है के बारे में क्या मूल्य initialized किया जा रहा है. 

यह चीजें हैं जो होना होता है - हां, तो सबसे अधिक भाग के लिए, सी + + सी. के एक superset आप सी कोड ले, सी + +, और यह संकलन चाहिए यह स्थानांतरित कर सकते हैं. यह एक चीज़ें है कि सी + + का समर्थन नहीं करता है, तो लोगों को यह नहीं करते हैं. मैं जानता हूँ कि अगर वह एकमात्र कारण है कि लोगों को यह नहीं करते हैं पता नहीं है, लेकिन इस मामले में जहां मैं इसे इस्तेमाल करने की जरूरत है सी + + और इसलिए मैं यह नहीं इस्तेमाल कर सकते हैं के साथ काम करने की जरूरत है. कुछ है कि एक और उदाहरण है सी + + है साथ काम नहीं करता malloc एक "शून्य *," कैसे देता है, तकनीकी रूप से, लेकिन तुम सिर्फ चार * x = malloc जो कुछ भी कह सकते हैं, और यह स्वचालित रूप से एक चार * के लिए डाली जाएगा. यह स्वचालित डाली में नहीं होता है सी + +. कि संकलन नहीं है, और आप स्पष्ट रूप से कहने की ज़रूरत नहीं होगा चार *, malloc, जो कुछ भी है, के लिए यह एक चार * डाली. वहाँ कई चीजें है कि सी और सी + + पर असहमत नहीं हैं, लेकिन उन दो हैं. तो हम इस सिंटैक्स के साथ जाना होगा. लेकिन फिर भी अगर हम उस वाक्य रचना के साथ जाना नहीं था, क्या है इस के साथ गलत हो सकता है? [छात्र] मैं यह भिन्नता करने की जरूरत नहीं है? >> हाँ. याद रखें कि तीर एक अंतर्निहित भिन्नता है, और इसलिए जब हम सिर्फ एक struct के साथ काम कर रहे हैं, हम प्रयोग करना चाहते हैं. struct के एक क्षेत्र के अंदर में मिलता है. और केवल समय हम तीर का उपयोग है जब हम करना चाहते हैं - ठीक है, तीर के बराबर है - है कि यह क्या अगर मैं तीर का इस्तेमाल करने का मतलब होगा. सभी तीर का मतलब है, यह भिन्नता है, अब मैं एक struct में हूँ, और मैं इस क्षेत्र में प्राप्त कर सकते हैं. क्षेत्र या तो सीधे या भिन्नता पाने के लिए और क्षेत्र - मुझे लगता है कि इस मूल्य होना चाहिए. लेकिन यहाँ मैं सिर्फ एक, एक struct के लिए एक सूचक नहीं struct के साथ काम कर रहा हूँ, और इसलिए मैं तीर का उपयोग नहीं कर सकते हैं. लेकिन इस तरह की बात हम सभी नोड्स के लिए कर सकते हैं. हे भगवान. यह 6, 7, और 3 में से एक है. तो हम हमारे पेड़ में शाखाओं की स्थापना कर सकते हैं, हम कर सकते हैं 7 - हम, अपनी बाईं 3 से बात कर सकते हैं. तो हम कैसे करते हैं? [छात्रों, unintelligible] >> हाँ. node3 के पते, और अगर आप पता नहीं था, तो यह न सिर्फ संकलन होगा. लेकिन याद रखना कि इन अगले नोड के संकेत दिए गए हैं. सही 9 में बात करनी चाहिए, और 3 6 के लिए सही पर बात करनी चाहिए. मुझे लगता है कि यह सब सेट है. किसी भी टिप्पणी या प्रश्न? [छात्र, unintelligible] जड़ से 7 हो जा रहा है. हम सिर्फ नोड कह सकते हैं * ptr = या रूट =, और node7. 

हमारे प्रयोजनों के लिए, हम डालने के साथ काम करने जा रहे हैं, तो हम इस द्विआधारी पेड़ में सम्मिलित करने के लिए एक समारोह में लिखने के लिए चाहते करने जा रहे हैं और डालने के अनिवार्य रूप से malloc कॉल करने के लिए इस पेड़ के लिए एक नया नोड बनाने जा रहा है. तो चीजें इस तथ्य के साथ गंदा हो जा रहे हैं कि कुछ नोड्स ढेर पर वर्तमान में कर रहे हैं और अन्य नोड्स के लिए ढेर पर खत्म होता है जब हम उन्हें डालने के लिए जा रहे हैं. यह पूरी तरह से वैध है, लेकिन एक ही कारण हम ढेर पर ऐसा करने में सक्षम हैं क्योंकि यह एक ऐसी काल्पनिक उदाहरण है कि हम जानते हैं कि 7, 3, 6, 9 के रूप में निर्माण किया जा पेड़ माना जाता है. यदि हम ऐसा नहीं किया, तो हम पहली जगह में malloc नहीं करना होगा. जैसा कि हम थोड़ा बाद में देखेंगे, हम malloc'ing किया जाना चाहिए. अभी यह पूरी तरह से उचित है के ढेर पर डाल दिया है, लेकिन एक malloc कार्यान्वयन के लिए इस परिवर्तन. तो इनमें से प्रत्येक के लिए कुछ तरह होने जा रहा है नोड node9 * = malloc ((नोड) sizeof). और अब हम हमारे चेक करने के लिए जा रहे हैं. अगर (== Null node9) - मैं नहीं चाहता था कि - 1 लौटने के लिए, और फिर हम node9> नहीं है क्योंकि अब यह एक सूचक है, मूल्य = 6, node9> = रिक्त छोड़ दिया, node9 रिक्त> सही = और हम उन नोड्स में से प्रत्येक के लिए कि क्या करना है करने के लिए जा रहे हैं. तो बजाय, चलो यह एक अलग समारोह के अंदर रख दिया. चलो नोड build_node * कहते हैं, और यह कुछ APIs हम Huffman कोडिंग के लिए उपलब्ध कराने के लिए इसी तरह की है. हम आपको एक पेड़ के लिए initializer कार्यों दे और deconstructor उन पेड़ों और जंगलों के लिए एक ही के लिए "कार्य". 

तो यहाँ हम एक initializer समारोह के लिए जा रहे हैं सिर्फ हमारे लिए एक नोड का निर्माण. और यह वास्तव में इस तरह बहुत ज्यादा लग रहा है. और मैं भी आलसी हो जा रहा हूँ और चर का नाम बदलने के लिए नहीं, भले ही node9 अब और कोई मतलब नहीं बनाता है. ओह, मैं node9 मूल्य लगता है कि नहीं होना चाहिए 6. अब हम node9 लौट सकते हैं. और यहाँ हम अशक्त लौट जाना चाहिए. हर कोई है कि समारोह में निर्माण एक नोड पर सहमत हैं? तो अब हम सिर्फ फोन है कि किसी दिए गए मूल्य और अशक्त संकेत के साथ किसी भी नोड का निर्माण करने के लिए कर सकते हैं. अब हम कह सकते हैं, हम नोड node9 * = build_node (9) कर सकते हैं. और करना. . . 6, 3, 7, 6, 3, 7. और अब हम एक ही संकेत सेट करना चाहते हैं, अब के अलावा सब कुछ संकेत के मामले में पहले से ही है इसलिए नहीं के पते की आवश्यकता है. ठीक है. तो आखिरी बात मैं करना चाहता क्या है? वहाँ एक त्रुटि जाँच है कि मैं नहीं कर रहा हूँ. क्या नोड वापसी निर्माण करता है? [छात्र, unintelligible] >> हाँ. यदि malloc विफल रहा है, यह शून्य वापस कर देंगे. तो मैं lazily यहाँ प्रत्येक के लिए एक शर्त करने के बजाय इसे नीचे रख करने के लिए जा रहा हूँ. अगर (रिक्त node9 ==, या और भी आसान, इस node9 ही नहीं, अगर करने के लिए बराबर है. तो अगर node9 नहीं है, या नहीं node6, या नहीं node3, या नहीं node7, 1 लौटने के लिए. शायद हम प्रिंट चाहिए malloc विफल रहा है, या कुछ और. [छात्र] बराबर गलत के रूप में अच्छी तरह से अशक्त है? [Bowden] कोई शून्य मान गलत है. तो अशक्त एक शून्य मान है. शून्य एक शून्य मान है. झूठा एक शून्य मान है. कोई बहुत ज्यादा केवल 2 शून्य मान शून्य और शून्य हैं, झूठी सिर्फ शून्य के रूप में परिभाषित किया हैश है. यह भी लागू होता है अगर हम वैश्विक चर घोषणा करते हैं. अगर हम नोड * जड़ है यहाँ था, फिर वैश्विक चर के बारे में अच्छी बात यह है कि वे हमेशा एक प्रारंभिक मूल्य है. यह कार्यों का सच नहीं है, यहाँ के अंदर कैसे, अगर हम, जैसे, नोड * या नोड एक्स. हम पता नहीं क्या x.value, x.whatever है, या हम उन्हें प्रिंट और वे मनमाने ढंग से हो सकता सकता है. यह वैश्विक चर का सच नहीं है. तो नोड जड़ या नोड एक्स. डिफ़ॉल्ट रूप से, सब कुछ है कि वैश्विक है, नहीं तो कुछ मूल्य के लिए स्पष्ट रूप से पड़ेगा, अपने मूल्य के रूप में एक शून्य मान है. तो यहाँ, नोड * जड़, हम कुछ भी करने के लिए स्पष्ट रूप से यह नहीं इनिशियलाइज़ करते हैं, तो उसके डिफ़ॉल्ट मान शून्य हो सकता है, जो संकेत के शून्य मान है. एक्स के डिफ़ॉल्ट मान मतलब कि x.value शून्य है जा रहा है, x.left अशक्त है, है और x.right रिक्त है. इतने के बाद से यह एक struct है struct के क्षेत्रों के सभी शून्य मान होगा. कि हम यहाँ का उपयोग की जरूरत नहीं है, फिर भी. [छात्र] structs अन्य चर से अलग कर रहे हैं, और अन्य चर रहे हैं कचरा मूल्यों, इन शून्य हैं? [Bowden] भी मान. तो एक्स, एक्स शून्य हो जाएगा. यदि यह वैश्विक दायरे में है, यह एक प्रारंभिक मूल्य है. ठीक है. >> [Bowden] या तो प्रारंभिक मूल्य आप यह या शून्य दिया. मुझे लगता है कि इस सब का ख्याल रखता है. 

ठीक है. तो प्रश्न के अगले भाग पूछता है, "अब हमें बुलाया शामिल एक समारोह लिखने के लिए चाहते हैं bool के एक प्रोटोटाइप के साथ int मूल्य शामिल हैं. " हम bool int मूल्य शामिल करने के लिए नहीं जा रहे हैं. हमारे प्रोटोटाइप की तरह लग रहा है bool (int मूल्य शामिल हैं. और फिर हम भी यह पेड़ पारित करने के लिए जा रहे हैं कि यह देखने के लिए अगर यह है कि मूल्य है की जाँच की जानी चाहिए. तो नोड * पेड़). ठीक है. और फिर हम ऐसा कुछ के साथ कॉल कर सकते हैं, शायद हम printf या कुछ और करने के लिए चाहता हूँ. 6, हमारी जड़ में शामिल हैं. यह एक है, या सच लौट जाना चाहिए, जबकि 5 जड़ होता झूठी लौट जाना चाहिए. तो एक दूसरे से इस लागू करने. आप इसे या तो iteratively या बारी बारी से कर सकते हैं. जिस तरह से हम चीजों को स्थापित किया है के बारे में अच्छी बात यह है कि यह ही हमारे पुनरावर्ती बहुत आसान समाधान के लिए उधार देता है की तुलना में वैश्विक चर का रास्ता था. क्योंकि अगर हम सिर्फ int मूल्य होता है, तो हम नीचे subtrees recursing का कोई रास्ता नहीं है. हम एक अलग सहायक समारोह में कहा कि हमारे लिए subtrees recurses होता है. लेकिन जब से हम बदल दिया है यह एक तर्क के रूप में पेड़ लेने के लिए, जो यह हमेशा पहली जगह में होना चाहिए था, अब हम recurse और अधिक आसानी से कर सकते हैं. चलने का या तो पुनरावर्ती, हम दोनों पर जायेंगे, लेकिन हम काफी आसान किया जा रहा है कि पुनरावर्ती समाप्त होता देखेंगे. ठीक है. क्या किसी को कुछ हम साथ काम कर सकते है? 

[छात्र] मुझे मिल गया है एक समाधान के चलने का. >> ठीक है, चलने का. ठीक है, यह अच्छा लग रहा है. तो, हमें इसे माध्यम से चलना चाहते हैं? [छात्र] ज़रूर. तो मैं एक अस्थायी चर सेट करने के पेड़ की 1 नोड. और फिर मैं बस जबकि अस्थायी बराबर अशक्त नहीं करता है के माध्यम से looped, जबकि पेड़ में अभी भी था, मुझे लगता है. और अगर मान मूल्य के बराबर है कि अस्थायी इशारा कर रहा है, तो यह है कि मान देता है. अन्यथा, यह चेक अगर यह सही पक्ष या बाईं ओर है. अगर तुम कभी एक स्थिति पाने के लिए जहां वहाँ कोई और अधिक पेड़ है, तो यह देता है - यह बाहर निकलता है पाश और झूठे रिटर्न. [Bowden] ठीक है. तो यह है कि अच्छा लगता है. किसी को कुछ भी पर कोई टिप्पणी है? मैं सब पर कोई शुद्धता टिप्पणी है. एक बात हम क्या कर सकते हैं इस आदमी है. ओह, यह एक छोटे से दीर्घाकार जाना जा रहा है. मुझे लगता है कि इसे ठीक कर दूँगा. ठीक है. 

हर कोई याद रखना चाहिए कैसे त्रिगुट काम करता है. वहाँ निश्चित रूप से अतीत में quizzes किया गया है कि आप एक त्रिगुट ऑपरेटर के साथ एक समारोह दे, और कहते हैं, इस का अनुवाद करने के लिए, कुछ है कि त्रिगुट का उपयोग नहीं करता है. तो यह एक बहुत ही आम का मामला है जब मैं त्रिगुट का उपयोग करने के लिए लगता है कि होगा, जहां अगर कुछ हालत कुछ करने के लिए एक चर सेट, और कुछ और करने के लिए है कि एक ही चर सेट. यह कुछ है कि बहुत बार इस तरह की बात में तब्दील किया जा सकता है जहां यह है कि चर सेट - या, ठीक है, यह सच है? तो यह है, और इस. [छात्र] पहले एक यह है कि अगर यह सच है, है ना? [Bowden] हाँ. जिस तरह से मैं हमेशा इसे पढ़ा है, अस्थायी अस्थायी मूल्य से अधिक मूल्य के बराबर है, तो यह है, और इस. यह एक सवाल पूछ रहा है. यह अधिक से अधिक है? तो पहली बात करते हैं. वरना दूसरी बात करते हैं. मैं लगभग हमेशा बृहदान्त्र, मैं सिर्फ मेरे सिर में, मैं के रूप में और पढ़ें. 

क्या किसी को एक पुनरावर्ती समाधान है? ठीक है. यह एक हम करने के लिए जा रहे हैं - यह पहले से ही बहुत अच्छा हो सकता है, लेकिन हम इसे और भी बेहतर बनाने के लिए जा रहे हैं. यह बहुत ज्यादा एक ही सटीक विचार है. यह सिर्फ है, ठीक है, आप को समझाने चाहते हो? [छात्र] ज़रूर. तो हमें यकीन है कि पेड़ 1 अशक्त नहीं है के लिए कर रहे हैं, क्योंकि अगर पेड़ रिक्त है तो यह वापसी झूठी जा रहा है क्योंकि हम यह नहीं मिला है. और अगर वहाँ अभी भी एक पेड़ है, हम में जाने - हम पहले की जाँच करें अगर मूल्य वर्तमान नोड है. सच लौटें अगर यह है, और अगर हम नहीं छोड़ दिया है या सही पर recurse. कि ध्वनि करता है उचित है? >> मम - हम्म. (अनुबंध) तो सूचना है कि यह लगभग structurally बहुत समाधान चलने का समान. यह सिर्फ है कि recursing के बजाय, हम एक समय पाश था. और आधार यहाँ मामले में जहां पेड़ बराबर अशक्त नहीं करता शर्त है जिसके तहत हम जबकि पाश से बाहर तोड़ दिया था. वे बहुत ही इसी तरह की हैं. लेकिन हम यह एक कदम आगे ले जा रहे हैं. अब, हम यहाँ एक ही बात करते हैं. सूचना हम इन लाइनों के दोनों में एक ही बात लौट रहे हैं, के लिए छोड़कर एक तर्क अलग है. तो हम एक त्रिगुट में बनाने जा रहे हैं. मैं विकल्प कुछ हिट, और यह एक प्रतीक बना दिया. ठीक है. तो हम वापस जा रहे हैं कि शामिल हैं. इस के लिए कई लाइनों हो रही है, ठीक है, यह है में तेजी से बढ़ी है. आमतौर पर, एक शैलीगत बात के रूप में, मैं कई लोगों को लगता है तीर के बाद एक जगह रखा है, लेकिन मुझे लगता है कि अगर आप लगातार कर रहे हैं, यह ठीक है. यदि मान पेड़ मूल्य से भी कम है, हम पेड़ बाईं पर recurse चाहते हैं, और हम पेड़ सही पर recurse करने के लिए करना चाहते हैं. तो यह है कि यह देखो छोटे बनाने के एक कदम था. यह देखो छोटे बनाने के दो कदम - हम यह कई लाइनों को अलग नहीं कर सकते हैं. ठीक है. यह छोटे देखो बनाने के चरण दो यहाँ है, इतना वापसी मूल्य पेड़ मूल्य के बराबर होती है, या जो भी शामिल हैं. 

यह एक महत्वपूर्ण बात है. मुझे यकीन है कि अगर उन्होंने कहा कि यह वर्ग में स्पष्ट रूप से नहीं कर रहा हूँ, लेकिन यह शॉर्ट सर्किट मूल्यांकन कहा जाता है. यहाँ विचार मूल्य == पेड़ मूल्य. अगर यह सच है, तो यह सच है, और हम चाहते हैं 'या' उस के साथ जो कुछ भी यहाँ पर है. तो भी जो कुछ भी यहाँ पर है के बारे में सोच के बिना, पूरे करने के लिए वापस जा अभिव्यक्ति क्या है? [छात्र] यह सच है? >> हाँ, क्योंकि कुछ का सच कुछ के साथ or'd - या सच or'd जरूरी सच है. इसलिए जैसे ही हम वापसी मान = पेड़ मूल्य देखते हैं, हम सिर्फ सच वापसी करने के लिए जा रहे हैं. Recurse करने के लिए भी नहीं जा रहा है और आगे नीचे पंक्ति है. हम इस एक कदम आगे ले जा सकते हैं. वापसी बराबर अशक्त और इस सब के पेड़ नहीं है. यह यह एक समारोह में एक पंक्ति बनाया है. यह भी शॉर्ट सर्किट मूल्यांकन का एक उदाहरण है. लेकिन अब यह एक ही विचार है - के बजाय यदि ऐसा है तो पेड़ नहीं अशक्त बराबर करता है - या, ठीक है, अगर पेड़ बराबर अशक्त करता है, जो खराब मामला है, अगर पेड़ अशक्त के बराबर होती है, तो पहली शर्त के लिए झूठी होने जा रहा है. तो कुछ के साथ anded झूठी क्या होने जा रहा है? [छात्र] झूठा. >> हाँ. यह शॉर्ट सर्किट मूल्यांकन के अन्य आधा है, जहां अगर पेड़ बराबर अशक्त नहीं करता है तो हम जा रहे हैं के लिए भी जाना नहीं - या अगर पेड़ बराबर अशक्त करता है, तो हम == मूल्य पेड़ मूल्य नहीं जा रहे हैं. हम सिर्फ तुरंत झूठी वापसी करने के लिए जा रहे हैं. जो महत्वपूर्ण है, क्योंकि अगर यह मूल्यांकन शॉर्ट सर्किट नहीं किया, फिर अगर पेड़ बराबर अशक्त करता है, इस दूसरी शर्त seg गलती के लिए जा रहा है, क्योंकि पेड़ -> मूल्य अशक्त dereferencing है. तो वह है कि. यह कर सकते हैं - शिफ्ट करने के लिए एक बार से अधिक. यह एक बहुत ही आम बात है, इस के साथ इस एक लाइन नहीं है, लेकिन यह परिस्थितियों में एक आम बात है, यहीं शायद नहीं, लेकिन अगर (पेड़ = NULL!, और पेड़ -> मूल्य == मूल्य), जो कुछ भी करते हैं. यह एक बहुत ही सामान्य स्थिति है, जहां होने के बजाय दो ifs हैं में यह टूट गया है, जहां चाहें, पेड़ अशक्त है? ठीक है, यह शून्य नहीं है, तो अब पेड़ के मूल्य के बराबर मूल्य है? यह मत करो. इसके बजाय, इस हालत है, इस गलती कभी नहीं seg जाएगा क्योंकि यह बाहर तोड़ने के लिए अगर यह होता रिक्त हो जाएगा. खैर, मुझे लगता है कि यदि आपके पेड़ एक पूरी तरह से अमान्य सूचक है, यह अभी भी फॉल्ट कर सकते हैं, लेकिन यह गलती नहीं seg है अगर पेड़ रिक्त है कर सकते हैं. अगर यह शून्य थे, यह बाहर तोड़ने से पहले आप कभी पहली जगह में सूचक dereferenced होगा. [छात्र] इस आलसी मूल्यांकन बुलाया है? 

[Bowden] आलसी मूल्यांकन एक अलग बात है. आलसी मूल्यांकन है और अधिक की तरह आप एक मूल्य के लिए पूछना, आप के लिए एक मूल्य की तरह की गणना पूछना है, लेकिन आप इसे तुरंत की जरूरत नहीं है. तो जब तक आप वास्तव में इसे जरूरत है, यह मूल्यांकन नहीं किया जाता. यह वास्तव में एक ही बात नहीं है, लेकिन Huffman pset में, यह कहते हैं कि हम "lazily" लिखने. कारण है कि हम ऐसा कर है क्योंकि हम वास्तव में लिखने buffering रहे हैं - हम एक समय में अलग - अलग बिट्स लिखना नहीं चाहता, या एक समय में अलग - अलग बाइट्स, हम बजाय बाइट्स का एक हिस्सा प्राप्त करना चाहते हैं. फिर एक बार हम बाइट्स का एक हिस्सा है, तो हम इसे लिखने के बाहर हूँ. हालांकि आप यह पूछना लिखने और fwrite और fread बात की ही तरह है. वे अपने पढ़ता और लिखता बफर. भले ही आप यह पूछने के लिए तुरंत लिखना है, यह शायद नहीं होगी. और आप यकीन है कि चीजें करने के लिए लिखा जा रहा है नहीं किया जा सकता है जब तक आप hfclose कॉल या जो भी है, जो कहते हैं, तो ठीक है, मैं मेरी फाइल को बंद कर रहा हूँ, इसका मतलब है कि मैं बेहतर सब कुछ लिखना चाहते हैं मैं अभी तक नहीं लिखा है. यह कोई सब कुछ लिखने के लिए बाहर की जरूरत है जब तक आप फाइल बंद कर रहे हैं, और फिर यह करने की जरूरत है. तो यह है कि आलसी अभी क्या है - यह इंतजार कर रहा है जब तक यह होता है. यह 51 ले और आप इसे में और अधिक विस्तार में जाना होगा, क्योंकि OCaml और 51 में सब कुछ है, सब कुछ recursion है. कोई समाधान चलने मूल रूप से. सब कुछ recursion, और आलसी मूल्यांकन परिस्थितियों का एक बहुत कुछ करने के लिए महत्वपूर्ण होने जा रहा है , जहां अगर आप lazily मूल्यांकन नहीं किया, इसका मतलब है - उदाहरण धाराओं, जो असीम रूप से लंबे होते हैं. सिद्धांत रूप में, आप 1-2-3-4-5-6-7 की एक धारा के रूप में प्राकृतिक संख्या के बारे में सोच सकते हैं, तो lazily मूल्यांकन चीजों को ठीक कर रहे हैं. अगर मैं कहूँ कि मैं 10 संख्या चाहते हैं, तो मैं 10 नंबर करने के लिए मूल्यांकन कर सकते हैं. यदि मैं सौवां संख्या चाहते हैं, तो मैं सौवां संख्या का मूल्यांकन कर सकते हैं. आलसी मूल्यांकन के बिना, तो यह करने के लिए सभी नंबरों को तुरंत मूल्यांकन करने की कोशिश करने जा रहा है. आप कई infinitely संख्या का मूल्यांकन कर रहे हैं, और कहा कि अभी संभव नहीं है. तो परिस्थितियों का एक बहुत कुछ कर रहे हैं, जहां आलसी मूल्यांकन बस चीजों को काम करने के लिए हो रही करने के लिए आवश्यक है. 

अब हम डालने लिखने के लिए जहां डालने के लिए होने जा रहा है इसी तरह अपनी परिभाषा में बदल रहा है. इसलिए अभी यह bool डालने (int मूल्य) है. हम bool डालने (int मूल्य, नोड * पेड़) बदलने के लिए जा रहे हैं. हम वास्तव में एक बिट में है कि फिर से बदलने के लिए जा रहे हैं, हम क्यों देखेंगे. और चलो build_node बस की बिल्ली के लिए ले जाने के लिए, ऊपर डालें तो हम एक समारोह प्रोटोटाइप लिखना नहीं है. जो एक संकेत है कि आप डालने में build_node का उपयोग किया जा रहे हैं. ठीक है. उस के लिए एक मिनट ले लो. मुझे लगता है कि मैं संशोधन बचाया अगर आप उस से खींच चाहते हैं, या कम से कम, मैं अब किया. मैं एक मामूली डालने के तर्क के बारे में सोचने के लिए तोड़ना चाहता था, अगर आप इसके बारे में नहीं सोच सकते हैं. असल में, आप केवल कभी पत्तियों में डालने जाएगा. की तरह, अगर मैं 1 डालने, तो मैं निश्चित रूप से 1 डालने जा रहा हूँ - मैं काला करने के लिए बदल देंगे - I'll यहाँ पर 1 डालने. या अगर मैं 4 सम्मिलित करते हैं, मैं यहाँ पर 4 डालने होना चाहता हूँ. तो कोई फर्क नहीं पड़ता कि तुम क्या करते हो, आप एक पत्ता में सम्मिलित होने जा रहे हैं. सब तुम्हें क्या करना है है नीचे पेड़ पुनरावृति जब तक आप नोड के लिए मिलता है कि नोड के माता पिता, नए नोड के माता पिता होना चाहिए, और फिर छोड़ दिया है या सही सूचक बदलने के लिए, इस बात पर निर्भर करता है यह से अधिक है या कम से कम वर्तमान नोड है. अपने नए नोड को इंगित करने के लिए कि सूचक बदलो. तो नीचे पेड़ पुनरावृति, नए नोड पत्ती बिंदु बनाते हैं. इसके अलावा, क्यों कि इससे पहले कि स्थिति के प्रकार मनाही के बारे में सोचते हैं, जहां मैं द्विआधारी पेड़ का निर्माण जहां यह सही था अगर आप केवल एक नोड को देखा, लेकिन 9 7 की बाईं करने के लिए किया गया था यदि आप नीचे सभी तरह दोहराया. इसलिए कि इस परिदृश्य में असंभव है क्योंकि, लगता है के बारे में 9 या कुछ डालने, बहुत पहले नोड पर, मैं 7 देखने के लिए जा रहा हूँ और मैं सिर्फ सही करने के लिए जा रहा हूँ. तो कोई फर्क नहीं पड़ता कि मुझे क्या करना है, अगर मैं एक पत्ता जाकर सम्मिलित कर रहा हूँ, और एक उपयुक्त एल्गोरिथ्म का उपयोग कर पत्ती, यह करने के लिए असंभव हो सकता है मेरे लिए 9 7 की बाईं डालने के लिए जा रहा है क्योंकि जैसे ही के रूप में मैं 7 मारा मैं सही करने के लिए जा रहा हूँ. किसी को भी करता है के साथ शुरू करने के लिए कुछ है? [छात्र] मुझे क्या करना है. ज़रूर. >> [छात्र, unintelligible] [अन्य छात्र, unintelligible] [Bowden] यह सराहना की है. ठीक है. समझाना चाहते हैं? 

[छात्र] के बाद से हम जानते हैं कि हम डालने थे पेड़ के अंत में नई नोड्स, मैं पेड़ के माध्यम से iteratively looped जब तक मैं एक नोड कि अशक्त ओर इशारा करने के लिए मिला है. और फिर मैं यह दाईं ओर या बाईं ओर भी डाल करने का फैसला किया यह सही चर का उपयोग कर रहा है, यह मुझे बताया यह डाल दिया, जहां. और फिर, अनिवार्य रूप से, मैं सिर्फ कि पिछले बनाया - नए नोड का निर्माण किया गया है कि यह है कि अस्थायी नोड बिंदु, या तो बाईं ओर या दाईं ओर, मूल्य क्या सही था पर निर्भर करता है. अंत में, मैं नए नोड अपने परीक्षण के मूल्य के लिए मूल्य निर्धारित किया है. [Bowden] ठीक है, तो मैं एक मुद्दा यहाँ देखें. यह वहाँ रास्ते से 95% की तरह है. एक मुद्दा यह है कि मैं देख रहा हूँ, ठीक है, किसी और को एक मुद्दा देख नहीं है? परिस्थिति है जिसके तहत वे पाश से बाहर तोड़ने के क्या है? [छात्र] यदि अस्थायी अशक्त है? >> हाँ. तो कैसे आप लूप के बाहर तोड़ अगर अस्थायी अशक्त है. लेकिन मैं सही यहाँ क्या करते हो? मैं भिन्नता अस्थायी है, जो अनिवार्य रूप से अशक्त है. तो अन्य बात तुम क्या करने की जरूरत नहीं है सिर्फ ट्रैक रखने जब तक अस्थायी अशक्त है, आप करने के लिए माता पिता के सभी समय पर नज़र रखना चाहते हैं. हम भी नोड * माता - पिता चाहते हैं, मुझे लगता है कि हम पहली बार में अशक्त पर रख सकते हैं. इस पेड़ की जड़ के लिए अजीब व्यवहार किया जा रहा है, लेकिन हम है कि मिल जाएगा. यदि मूल्य जो भी अधिक है, तो अस्थायी अस्थायी = सही. लेकिन इससे पहले कि हम जानते हैं कि माता - पिता = अस्थायी. या माता - पिता को हमेशा बराबर अस्थायी जा रहे हैं? मामला है कि? यदि अस्थायी रिक्त नहीं है, तो मैं करने के लिए नीचे ले जाने के लिए, कोई बात नहीं क्या करने के लिए जा रहा हूँ, एक नोड है जिसके लिए अस्थायी माता पिता है. तो माता पिता के लिए अस्थायी हो जा रहा है, और फिर मैं अस्थायी नीचे स्थानांतरित करने के लिए. अब अस्थायी रिक्त है, लेकिन बात यह है कि अशक्त है के माता पिता के लिए माता - पिता बताते हैं. तो यहाँ नीचे, मैं सही बराबरहै 1 सेट नहीं करना चाहती. तो मैं सही करने के लिए ले जाया गया है, यदि ऐसा है तो सही = 1, और मुझे लगता है कि आप भी करना चाहते हैं - यदि आप बाईं करने के लिए ले जाने के लिए, आप सही 0 के बराबर सेट करना चाहते हैं. वरना अगर तुम कभी सही करने के लिए कदम. तो सही = 0. यदि सही = 1, अब हम माता पिता सही सूचक newnode बनाना चाहते हैं, और हम माता - पिता छोड़ दिया सूचक newnode बनाना चाहते. उस पर सवाल? ठीक है. तो इस तरह से हम है - ठीक है, वास्तव में, इस कर के बजाय, हम आधा आप build_node का उपयोग करने के लिए उम्मीद है. और फिर अगर newnode अशक्त के बराबर होती है, झूठी वापसी. वह है कि. अब, यह है कि हम क्या तुम क्या करने की उम्मीद है. 

यह है कि स्टाफ समाधान क्या करना है. मैं इसके बारे में जाने के "" सही तरीका के रूप में इस से असहमत लेकिन यह पूरी तरह से ठीक है और यह काम करेगा. एक बात है कि एक छोटे से अजीब अब ठीक है अगर पेड़ अशक्त रूप में शुरू होता है, तो हम एक अशक्त पेड़ में गुजरती हैं. मुझे लगता है कि यह कैसे आप एक अशक्त पेड़ में पारित करने के व्यवहार को परिभाषित करने पर निर्भर करता है. मुझे लगता है कि अगर आप एक अशक्त पेड़ में पारित तो एक अशक्त पेड़ में मूल्य डालने सिर्फ एक पेड़ लौट जाना चाहिए जहां केवल मूल्य कि एक नोड है. क्या लोगों के साथ सहमत हैं? तुम्हें पता है, अगर तुम चाहते थे सकता है, अगर तुम एक अशक्त पेड़ में पारित और आप इसे में एक मान सम्मिलित करना चाहते हैं, तो वापसी झूठी. यह आप पर निर्भर है कि को परिभाषित. पहली बात मैं कहा और फिर करने के लिए - ठीक है, तुम कर रही है कि मुसीबत के लिए जा रहे हैं, क्योंकि यह आसान हो सकता है अगर हम बात करने के लिए एक वैश्विक सूचक होता था, लेकिन हम ऐसा नहीं अगर पेड़ अशक्त है, वहाँ कुछ भी नहीं है हम उस बारे में क्या कर सकते हैं. हम सिर्फ झूठी लौट सकते हैं. तो मैं डालने बदलने के लिए जा रहा हूँ. हम तकनीकी रूप से यह सही यहाँ बदल सकता है, यह बातों पर कैसे iterating है, लेकिन मैं डालने को बदलने के लिए एक नोड ** पेड़ ले जा रहा हूँ. डबल संकेत दिए. इसका क्या मतलब है? नोड्स के लिए संकेत के साथ काम करने के बजाय, बात मैं जोड़ तोड़ करने जा रहा हूँ यह सूचक है. मैं यह सूचक से छेड़छाड़ करने जा रहा हूँ. मैं संकेत जोड़ तोड़ सीधे जा रहा हूँ. यह समझ में आता है के बाद से, नीचे के बारे में सोचते हैं - ठीक है, ठीक है अब इस अंक को अशक्त करने के लिए. मैं क्या करना चाहते है इस सूचक में हेरफेर करने के लिए अशक्त करने के लिए बात नहीं है. मैं यह मेरी नई नोड के लिए बात करने के लिए करना चाहते हैं. अगर मैं सिर्फ संकेत के ट्रैक मेरे संकेत के लिए रखने के लिए, तो मैं एक माता पिता सूचक का ट्रैक रखने की जरूरत नहीं है. मैं सिर्फ ट्रैक रखने के लिए देखने के लिए अगर सूचक को अशक्त इशारा कर रहा है, और अशक्त करने के लिए अगर सूचक इशारा कर रहा है, इसे बदलने के लिए मैं चाहता हूँ नोड को इंगित करने के लिए. और मैं इसे बदल के बाद से मैं संकेतक के लिए एक सूचक हो सकता है. यह अभी देखते हैं. आप वास्तव में इसे बारी बारी से बहुत आसानी से कर सकते हैं. क्या हम ऐसा करने के लिए करना चाहते हैं? हाँ, हम करते हैं. 

चलो यह recursively देख. सबसे पहले, हमारे आधार के मामले में क्या होने जा रहा है? लगभग हमेशा हमारे आधार मामला है, लेकिन वास्तव में, यह मुश्किल की तरह है. सबसे पहली बात, अगर पेड़ (== रिक्त) मुझे लगता है कि हम सिर्फ झूठी वापसी करने जा रहे हैं. यह अपने पेड़ बातिल से अलग है. यह अपने रूट अशक्त जा रहा है सूचक सूचक है जिसका अर्थ है कि अपने रूट सूचक मौजूद नहीं है. तो यहाँ नीचे, अगर मैं नोड * - हम सिर्फ इस पुनः प्रयोग. नोड * जड़ = रिक्त, और फिर मैं जैसे कुछ करके डालने फोन करने के लिए जा रहा हूँ, रूट में 4 सम्मिलित करें. तो और जड़, अगर एक जड़ नोड * और फिर जड़ एक नोड ** होने जा रहा है. यह वैध है. इस मामले में, पेड़, यहाँ, या डालने पेड़ रिक्त नहीं है. यहाँ. ट्री रिक्त नहीं है, पेड़ * अशक्त है, जो ठीक है क्योंकि अगर * पेड़ रिक्त है, तो मैं इसे में हेरफेर कर सकते हैं अब मैं क्या यह करने के लिए बात करने के लिए करना चाहते हैं इंगित. लेकिन अगर पेड़ अशक्त है, इसका मतलब है कि मैं बस यहाँ आए थे और अशक्त कहा. यह समझ में नहीं पड़ता है. मैं उस के साथ कुछ भी नहीं कर सकते. यदि पेड़ अशक्त है, झूठी वापसी. तो मैं मूल रूप से पहले से ही ने कहा कि हमारी असली आधार मामला क्या है. और कहा कि क्या होने जा रहा है? [छात्र, unintelligible] [Bowden] हाँ. तो अगर (* पेड़ == रिक्त). यह यहाँ पर मामले से संबंधित है जहां अगर मेरे लाल सूचक सूचक है कि मैं पर ध्यान केंद्रित कर रहा हूँ, तो जैसे मैं इस सूचक पर ध्यान केंद्रित कर रहा हूँ, अब मैं इस सूचक पर ध्यान केंद्रित कर रहा हूँ. अब मैं इस सूचक पर ध्यान केंद्रित कर रहा हूँ. तो अगर मेरे लाल सूचक है, जो मेरे नोड ** है, कभी - * अगर मेरे लाल सूचक, कभी अशक्त है, इसका मतलब है कि मैं मामले में जहां मैं एक सूचक है कि अंक पर ध्यान केंद्रित कर रहा हूँ - यह एक सूचक है कि एक पत्ती के अंतर्गत आता है. मैं इस सूचक को बदलने के लिए अपने नए नोड करने के लिए बात करना चाहते हैं. यहाँ पर वापस आ जाओ. मेरा newnode सिर्फ नोड * n = build_node (मान) हो जाएगा तो n, n = रिक्त यदि वापसी झूठी. वरना हम बदल सूचक वर्तमान में क्या इशारा कर रहा है अब हमारे नव निर्मित नोड को इंगित. हम वास्तव में है कि यहाँ कर सकते हैं. N कह के बजाय, हम कहते हैं कि पेड़ * = * पेड़ अगर. हर कोई है कि समझ में आया? यह संकेत करने के लिए संकेत के साथ काम करके, हम अशक्त संकेत बदलने के लिए बातें हम उन पर बात करने के लिए करना चाहते हैं के लिए बात कर सकते हैं. कि हमारे आधार मामला है. 

अब हमारे पुनरावृत्ति, या हमारे recursion बहुत अन्य सभी recursions हम कर दिया गया है के लिए इसी तरह की होने जा रहा है. हम करने के लिए मान सम्मिलित करना चाहते करने के लिए जा रहे हैं, और अब मैं त्रिगुट फिर से उपयोग के लिए जा रहा हूँ, लेकिन हमारी हालत क्या होने जा रहा है? क्या यह हम तय करना होगा कि हम करने के लिए छोड़ दिया है या सही जाना चाहते हैं के लिए देख रहे है? चलो यह अलग - अलग चरणों में करते हैं. यदि (मूल्य) क्या है? [छात्र] पेड़ मूल्य? [Bowden] इतना याद है कि मैं वर्तमान में हूँ - [छात्रों, unintelligible] [Bowden] हाँ, तो ठीक है यहाँ, चलो का कहना है कि इस हरी तीर पेड़ क्या वर्तमान का एक उदाहरण है, इस सूचक के लिए एक सूचक है. तो इसका मतलब है कि मैं 3 करने के लिए एक संकेतक के लिए एक सूचक हूँ. भिन्नता दो बार अच्छा लग रहा था. मैं क्या - मैं कैसे है कि क्या करते हो? [छात्र] एक बार भिन्नता है, और फिर करना तीर तरीका है कि? तो [Bowden] (* पेड़) भिन्नता है, एक बार मूल्य> मुझे कि मैं परोक्ष रूप से इशारा कर रहा हूँ नोड के मूल्य देने के लिए जा रहा है. तो मैं भी इसे लिखने tree.value ** अगर आपको लगता है कि पसंद करते हैं कर सकते हैं. या तो काम करता है. यदि यह मामला है, तो मैं मूल्य के साथ डालने कॉल करने के लिए करना चाहते हैं. और मेरे अद्यतन नोड ** होने जा रहा है? मैं बाईं करने के लिए जाना चाहते हैं, तो ** tree.left मेरे बाएँ होने जा रहा है. और मुझे लगता है कि बात करने के लिए सूचक चाहते इतना है कि अगर छोड़ दिया शून्य सूचक की जा रही समाप्त होता है, मैं इसे संशोधित करने के लिए अपने नए नोड के लिए बात कर सकते हैं. 

और अन्य मामले बहुत ही इसी तरह की हो सकती है. चलो वास्तव में सही है कि अब मेरी त्रिगुट. यदि मान <(** पेड़). मूल्य मूल्य डालें. तो फिर हम करने के लिए छोड़ दिया करने के लिए हमारे ** अद्यतन करना चाहते हैं, और हम सही करने के लिए हमारे ** अद्यतन करना चाहते हैं. [छात्र] कि सूचक सूचक के लिए क्या मिलता है? [Bowden] याद रखें कि - ** tree.right एक नोड सितारा है. [छात्र, unintelligible] >> हाँ. ** Tree.right इस सूचक या कुछ और की तरह है. इसलिए कि एक सूचक लेने के द्वारा, कि मुझे देता है मैं क्या चाहता हूँ उस आदमी के लिए सूचक की. [छात्र] हम पर फिर से जा सकते हैं इसलिए हम दो संकेत का उपयोग कर रहे हैं? [Bowden] हाँ. - तो नहीं, आप, और है कि समाधान कर सकते हैं पहले यह दो संकेत कर के बिना करने का एक तरीका था. आप दो संकेत का उपयोग को समझने में सक्षम होने की जरूरत है, और यह एक स्वच्छ समाधान है. इसके अलावा, सूचना है कि, क्या होता है अगर मेरी पेड़ - क्या होता है अगर मेरी जड़ अशक्त था? क्या होता है अगर मैं इस मामले को सही यहाँ करते हैं? तो नोड जड़ * = रिक्त, 4 रूट में सम्मिलित करें. जड़ क्या इस के बाद होने जा रहा है? [छात्र, unintelligible] >> हाँ. रूट मूल्य 4 होने जा रहा है. जड़ बाईं अशक्त होने जा रहा है, जड़ सही अशक्त होने जा रहा है. मामले में हम जड़ जहां पते द्वारा पारित नहीं किया था, हम जड़ को संशोधित नहीं कर सकता है. मामले में जहां पेड़ - जहां जड़ अशक्त था, हम सिर्फ झूठी लौटना पड़ा. हम कुछ नहीं कर सकता है. हम एक खाली पेड़ में एक नोड नहीं डाल सकते. लेकिन अब हम कर सकते हैं, हम सिर्फ एक नोड एक पेड़ में एक खाली पेड़ बना. जो आम तौर पर उम्मीद की तरह है कि यह काम करने वाला है. 

इसके अलावा, इस तुलना में काफी कम है माता पिता का ट्रैक रखने, और तो आप नीचे सभी तरह पुनरावृति. अब मैं अपने माता पिता है, और मैं सिर्फ अपने माता - पिता सही जो कुछ भी करने के लिए सूचक है. इसके बजाय, अगर हम इस iteratively किया, यह एक समय पाश के साथ एक ही विचार होना चाहते हैं. लेकिन मेरे माता पिता सूचक के साथ सौदा करने के बजाय, बजाय मेरे वर्तमान सूचक बात होगी कि मैं सीधे अपने नए नोड को इंगित करने के लिए संशोधित कर रहा हूँ. मैं चाहे वह बाईं ओर इशारा करते है के साथ सौदा नहीं है. मैं क्या यह सही है की ओर इशारा करते है के साथ सौदा नहीं है. यह बस है जो कुछ भी यह सूचक, मैं इसे स्थापित करने के अपने नए नोड करने के लिए बात कर रहा हूँ जा रहा है. हर कोई समझ है कि यह कैसे काम करता है? यदि नहीं तो हम इसे इस तरह से क्यों करना चाहते हो, लेकिन कम से कम है कि एक समाधान के रूप में यह काम करता है? [छात्र] हम सच कहां लौटा? [Bowden] कि शायद यहीं पर है. अगर हम सही ढंग से इसे डालने, सच वापसी. वरना, नीचे यहाँ हम करने के लिए जो कुछ भी डालने रिटर्न वापसी करना चाहते जा रहे हैं. 

और इस पुनरावर्ती समारोह के बारे में क्या खास है? यह पुनरावर्ती पूंछ है, इसलिए जब तक हम कुछ अनुकूलन के साथ संकलन, यह है कि पहचान और आप इस से एक ढेर अतिप्रवाह कभी नहीं मिल जाएगा, भले ही हमारे पेड़ 10,000 या 10 लाख की एक ऊंचाई है. [छात्र, unintelligible] [Bowden] मुझे लगता है कि यह डैश में करता है - या क्या अनुकूलन स्तर एक पूंछ recursion के लिए मान्यता प्राप्त होना आवश्यक है. मुझे लगता है कि इसे पहचानता - जीसीसी और बजना भी उनके अनुकूलन स्तर के लिए अलग अलग अर्थ है. मैं कहना है कि यह यकीन है कि यह पूंछ recursion पहचान के लिए 2, DashO चाहते हैं. लेकिन हम - आप एक Fibonocci उदाहरण या कुछ तरह का निर्माण कर सकता है. यह इस के साथ परीक्षण करने के लिए आसान नहीं है, क्योंकि यह मुश्किल है निर्माण करने के लिए एक द्विआधारी पेड़ है कि इतनी बड़ी है. लेकिन हाँ, मुझे लगता है कि यह 2 DashO, कि अगर आप 2 DashO के साथ संकलन, यह पूंछ recursion लिए देखो और अनुकूलन है कि बाहर. वापस करने के लिए जाने - डालें सचमुच आखिरी बात यह की जरूरत है. चलो यहाँ पर डालने के लिए वापस जाना जहां हम एक ही विचार करने के लिए जा रहे हैं. यह अभी भी पूरी तरह से संभाल करने में सक्षम नहीं किया जा रहा है की दोष होगा जब जड़ ही रिक्त है, या पिछले प्रविष्टि शून्य है, लेकिन बजाय एक माता पिता सूचक के साथ निपटने की, चलो संकेत संकेत रखने का एक ही तर्क लागू. यहाँ अगर हम हमारे नोड ** चालू रखने के लिए, और हम का ट्रैक रखने के सही अब जरूरत नहीं है, लेकिन नोड चालू ** = पेड़ और. और अब हमारे जबकि पाश जबकि * चालू बराबर रिक्त नहीं करता जा रहा है. माता पिता का ट्रैक अब रखने की ज़रूरत नहीं है. छोड़ दिया और सही का ट्रैक रखने की जरूरत नहीं है. और मैं इसे अस्थायी फोन है, क्योंकि हम पहले से ही अस्थायी का उपयोग कर रहे हैं. ठीक है. तो अगर (मूल्य> * अस्थायी), और फिर (* अस्थायी) - ठीक है> अन्यथा अस्थायी = & (* अस्थायी) -> छोड़ दिया. और अब, इस बिंदु पर, इस जबकि पाश के बाद, मैं केवल यह नहीं है क्योंकि शायद यह आसान है के बारे में iteratively recursively की तुलना में लगता है, लेकिन इस जबकि पाश के बाद, * अस्थायी सूचक हम बदलना चाहते है. 

इससे पहले कि हम माता पिता था, और हम या तो माता - पिता छोड़ दिया है या सही माता पिता को बदलना चाहते थे, लेकिन अगर हम करने के लिए माता पिता सही बदलना चाहते हैं, फिर * अस्थायी माता पिता का अधिकार है, और हम इसे सीधे बदल सकते हैं. तो यहाँ नीचे, हम * अस्थायी = newnode करते हैं, कर सकते हैं और यह बात है. सूचना के तो, हम इस में किया था कोड की लाइनों लेने के लिए गया था. आदेश में सभी में अपने माता पिता की है कि अतिरिक्त प्रयास का ट्रैक रखने के. यहाँ, अगर हम सिर्फ सूचक सूचक का ट्रैक रखने के लिए, और यहां तक ​​कि अगर हम इन सभी घुंघराले ब्रेसिज़ से छुटकारा पाने के लिए अब चाहता था, यह कम लग रही है. अब यह सटीक एक ही समाधान है, लेकिन कोड के कम लाइनों. एक बार जब आप एक मान्य हल के रूप में यह पहचानने शुरू, यह भी कारण के बारे में तरह से आसान है, ठीक है, मैं क्यों int सही पर इस ध्वज है? इसका क्या मतलब है? ओह, यह वाचक है कि हर समय मैं सही जाओ, मैं इसे स्थापित करने की आवश्यकता है, और अगर मैं जाना छोड़ दिया है मैं इसे शून्य करने के लिए सेट की जरूरत है. यहाँ, मैं उस के बारे में कारण नहीं है, यह सिर्फ आसान है के बारे में सोचते हैं. प्रश्न? [छात्र, unintelligible] >> हाँ. ठीक है, तो पिछले बिट में - मुझे लगता है कि एक त्वरित और आसान समारोह हम क्या कर सकते है, let's - साथ मुझे लगता है, कोशिश करते हैं और लिखने के एक समारोह शामिल हैं जो परवाह नहीं है कि क्या यह एक द्विआधारी खोज वृक्ष है. यह शामिल समारोह सच लौट जाना चाहिए अगर यह सामान्य द्विआधारी पेड़ में कहीं भी मूल्य के लिए हम देख रहे हैं. तो चलो पहले यह recursively करते हैं और फिर हम यह iteratively करूँगा. हम वास्तव में सिर्फ यह कर सकते हैं एक साथ, क्योंकि यह वास्तव में कम होने जा रहा है. 

मेरे आधार मामला क्या करने जा रहे हो? [छात्र, unintelligible] [Bowden] तो अगर (पेड़ == रिक्त) तो, क्या? [छात्र] झूठी वापसी. Bowden [] वरना, ठीक है, मैं और नहीं की जरूरत नहीं है. अगर मेरे अन्य आधार मामला था. [छात्र] पेड़ के मूल्य है? >> हाँ. (पेड़ -> मूल्य == मूल्य. सूचना हम नोड * वापस आ गए हैं नोड है ** नहीं? शामिल करने के लिए एक नोड ** का उपयोग करने की जरूरत नहीं होगी, जब से हम संकेत नहीं संशोधित कर रहे हैं. हम सिर्फ उन्हें traversing कर रहे हैं. अगर ऐसा होता है, तो हम सच वापसी करना चाहते हैं. वरना हम बच्चों को पार करना चाहते हैं. तो हम क्या छोड़ दिया करने के लिए सब कुछ कम है, के बारे में नहीं कर सकते और सही करने के लिए सब कुछ अधिक है. तो हमारी हालत क्या यहाँ होने जा रहा है - या, हम क्या करने जा रहे हैं? [छात्र, unintelligible] >> हाँ. वापसी शामिल है (मूल्य, पेड़ -> बाईं) या (मूल्य, पेड़ -> सही). और यह बात है. नोटिस और वहाँ कुछ शॉर्ट सर्किट मूल्यांकन है, जहां अगर हम छोड़ दिया पेड़ में मूल्य मिल होगा, हम कभी सही पेड़ को देखने की जरूरत है. कि पूरे समारोह है. अब यह iteratively करते हैं, जो कम अच्छा होने जा रहा है. हम नोड * चालू = पेड़ की सामान्य शुरुआत ले जाऊँगा. जबकि (चालू = रिक्त). जल्दी से एक समस्या को देखने के लिए जा रहा है. यदि चालू - यहाँ, अगर हम कभी भी इस से बाहर तोड़ने, तो हम बाहर की बातें चला है के लिए देखो, तो वापसी झूठी. यदि (चालू> मूल्य == मूल्य), सच वापसी. तो अब, हम एक जगह पर कर रहे हैं - हम नहीं जानते कि क्या हम छोड़ दिया है या सही जाना चाहते हैं. तो मनमाने ढंग से, चलो बस जाने के लिए छोड़ दिया. मैं स्पष्ट रूप से एक मुद्दा है जहाँ मैं पूरी तरह से सब कुछ त्याग दिया है में भाग लिया - मैं सिर्फ कभी एक पेड़ के बाईं ओर की जाँच करेगा. मैं कुछ भी है कि कुछ भी की एक सही बच्चा है कभी नहीं की जाँच करेगा. मैं यह कैसे तय करते हैं? [छात्र] आप एक ढेर में छोड़ दिया और सही का ट्रैक रखने के लिए किया है. [Bowden] हाँ. तो चलो इसे बनाने संरचना सूची, नोड * n, और फिर नोड अगले? ** मुझे लगता है कि ठीक काम करता है. ऊपर यहाँ हम पर छोड़ दिया है, या let's जाना चाहते. Struct सूची सूची =, यह शुरू करेंगे बाहर इस struct सूची पर. सूची * = रिक्त. तो यह है कि हमारे लिंक्ड सूची होने जा रहा है subtrees कि हम पर छोड़ दिया है. हम अब छोड़ दिया Traverse जा रहे हैं, लेकिन जब से हम निश्चित रूप से सही करने के लिए वापस आने की जरूरत है, हम हमारे struct सूची के अंदर सही पक्ष रखने के लिए जा रहे हैं. फिर हम new_list या struct होगा, संरचना सूची *, new_list = malloc ((सूची) sizeof). मैं कि त्रुटि जाँच अनदेखा करने जा रहा हूँ, लेकिन आप अगर यह अशक्त देखने की जाँच करनी चाहिए. New_list नोड को इंगित करने के लिए जा रहा है - ओह, यही कारण है कि मैं यह करना चाहता था यहाँ. यह एक दूसरे struct सूची को इंगित करने के लिए जा रहा है. इसका सिर्फ कैसे सूचियों काम से जुड़े हैं. यह एक int लिंक सूची के रूप में एक ही है को छोड़कर हम सिर्फ नोड * के साथ कर रहे हैं int की जगह. यह बिल्कुल वैसा ही है. तो new_list, हमारे new_list नोड के मूल्य, चालू> सही होने जा रहा है. हमारे मूल्य की new_list> अगले करने के लिए हमारी मूल सूची होने जा रहा है, और फिर हम हमारी सूची को अद्यतन करने के लिए new_list को इंगित करने के लिए जा रहे हैं. 

अब हम खींच चीजों में से एक रास्ते के कुछ प्रकार की जरूरत है, जैसे हम पूरे छोड़ दिया subtree तय किया. अब हम सामान से बाहर निकलने की जरूरत है, तरह चालू रिक्त है, हम सिर्फ झूठी वापसी नहीं करना चाहती. हम अब हमारी नई सूची में बाहर खींच करना चाहते हैं. ऐसा करने का एक सुविधाजनक तरीका है - ठीक है, वास्तव में, वहाँ ऐसा करने के कई तरीके है. किसी को भी एक सुझाव है? जहाँ मैं इस या कैसे मैं यह करना चाहिए करना चाहिए? हम केवल कुछ मिनट है, लेकिन किसी भी सुझाव? के बजाय एक ही रास्ता है, बजाय हमारी हालत की जा रही है, जबकि हम वर्तमान में क्या देख रहे हैं रिक्त नहीं है, बजाय हम करने के लिए जाने के लिए जारी जब तक हमारी सूची में ही रिक्त है करने के लिए जा रहे हैं. तो अगर हमारी सूची समाप्त होता है अशक्त जा रहा है, तो हम बाहर की बातें चलाने के लिए के लिए देखो, पर खोज. लेकिन इसका मतलब है कि हमारी सूची में पहली बात सिर्फ 1 नोड होने जा रहा है. बहुत पहले की बात है - हम नहीं रह गया है कि देखने की जरूरत है. तो सूची n> हमारे पेड़ हो जाएगा. सूची> अगले अशक्त होने जा रहा है. और अब जबकि सूची बराबर अशक्त नहीं करता है. Cur हमारी सूची से कुछ खींचने के लिए जा रहा है. तो बराबर सूची n> चालू करने जा रहा है. और फिर सूची बराबर सूची n> जा रहा है, या सूची -> अगले. तो अगर चालू मूल्य मूल्य के बराबर होती है. अब हम दोनों हमारे सही सूचक जोड़ सकते हैं और हमारे वाम संकेतक के रूप में लंबे समय के रूप में वे रिक्त नहीं हैं. यहाँ नीचे, मुझे लगता है कि हम किया जाना चाहिए कि पहली जगह में. यदि (चालू> सही = रिक्त) तो हम हमारी सूची में है कि नोड सम्मिलित करने के लिए जा रहे हैं. यदि (चालू> बाएं), इस अतिरिक्त काम का एक छोटा सा है, लेकिन यह ठीक है. अगर, (चालू> बाईं = रिक्त) और हम हमारे लिंक सूची में छोड़ दिया डालने के लिए जा रहे हैं, और कि यह होना चाहिए. हम पुनरावृति - के रूप में लंबे समय के रूप में हम अपनी सूची में कुछ है, हम दूसरे को देखने के नोड है. तो हम उस नोड पर देखो, हम अगले एक करने के लिए हमारी सूची अग्रिम. यदि उस नोड मूल्य के लिए हम देख रहे हैं, हम सच्चे लौट सकते हैं. वरना हमारे दोनों बाएँ और दाएँ subtrees डालने, के रूप में लंबे समय के रूप में वे अशक्त नहीं कर रहे हैं, हमारी सूची में इतना है कि हम निश्चित रूप से उन पर जाना. तो अगर वे अशक्त नहीं थे, अगर हमारी जड़ सूचक दो चीजों के लिए ओर इशारा किया, तो पहली बार में हम कुछ बाहर खींच लिया तो हमारी सूची समाप्त होता है अशक्त जा रहा है. और फिर हम दो चीजों में वापस डाल दिया है, इसलिए अब हमारी सूची 2 आकार की है. तो फिर हम पाश करने के लिए जा रहे हैं वापस ऊपर और हम सिर्फ खींचने के लिए जा रहे हैं, हम कहते हैं, हमारे रूट नोड के बाईं सूचक. और कहा कि अभी हो रहा रख देती हूँ, हम अंत में सब कुछ खत्म पाशन. 

सूचना है कि यह काफी अधिक जटिल था पुनरावर्ती समाधान में. और मैं कई बार कहा है कि पुनरावर्ती समाधान आमतौर पर आम में ज्यादा चलने का समाधान के साथ है. यहाँ यह है कि क्या वास्तव में पुनरावर्ती समाधान कर रही है. केवल परिवर्तन है कि उलझाव से ढेर का उपयोग करने के बजाय, इस कार्यक्रम के ढेर, नोड्स क्या आप अभी भी यात्रा करने के लिए की जरूरत का ट्रैक रखने के अपने रास्ते के रूप में, अब आप स्पष्ट रूप से एक लिंक की गई सूची का उपयोग करने के लिए किया है. दोनों ही मामलों में आप ट्रैक रखने के नोड क्या अभी भी दौरा किया जाना चाहिए. पुनरावर्ती मामले में यह सिर्फ आसान है क्योंकि एक ढेर कार्यक्रम ढेर के रूप में आप के लिए लागू है. सूचना है कि इस लिंक सूची, यह एक ढेर है. जो कुछ भी हम सिर्फ ढेर पर डाल दिया तुरंत है कि हम क्या ढेर खींचने के लिए अगली यात्रा के लिए रवाना करने के लिए जा रहे हैं. हम समय से बाहर कर रहे हैं, लेकिन किसी भी सवाल? [छात्र, unintelligible] [Bowden] हाँ. तो अगर हम हमारे लिंक सूची है, वर्तमान के इस आदमी को इंगित करने के लिए जा रहा है, और अब हम सिर्फ हमारे लिंक की गई सूची को आगे कर रहे हैं इस आदमी पर ध्यान केंद्रित. हम उस पंक्ति में लिंक की गई सूची पर traversing रहे हैं. और फिर मुझे लगता है कि हम हमारे लिंक्ड सूची और सामान मुक्त करना चाहिए एक बार सही है या गलत लौटने से पहले, हमें जरूरत है हमारे लिंक सूची पर पुनरावृति और हमेशा यहाँ नीचे, मुझे लगता है, अगर हम चालू सही के बराबर नहीं है, यह जोड़ने के लिए, तो अब हम मुक्त करने के लिए करना चाहते हैं चालू क्योंकि, ठीक है, हम पूरी तरह से सूची के बारे में भूल जाते हैं? हाँ. तो है कि क्या हम यहाँ क्या करना चाहते. सूचक कहाँ है? चालू तो था - हम चाहते हैं एक struct सूची 10 * सूची अगले बराबर होती है. नि: शुल्क सूची, सूची = अस्थायी. और मामले में जहां हम वापसी सच, हम पुनरावृति की क्या ज़रूरत है हमारे लिंक्ड चीजों को मुक्त कराने सूची के शेष पर. पुनरावर्ती समाधान के बारे में अच्छी बात यह बातें मुक्त है ढेर है जो आप के लिए होगा बंद popping factorings मतलब है. इसलिए हम कुछ है कि मुश्किल से लगता है कि के बारे में कोड की 3 लाइनों की तरह से चले गए कुछ उल्लेखनीय है कि कई और अधिक के लिए कड़ी मेहनत करने के लिए लगता है कि के बारे में कोड की लाइनों. अधिक कोई सवाल? सही सभी. हम अच्छा कर रहे हैं. अलविदा! [CS50.TV]