यह एल्गोरिदम सिद्धांत से एक साधारण सवाल है। उनके बीच का अंतर यह है कि एक मामले में आप नोड्स की संख्या और रूट और कंक्रीट नोड के बीच सबसे कम पथ पर किनारों की संख्या की गणना करते हैं। कौन सा क्या है?पेड़ की गहराई और ऊंचाई के बीच क्या अंतर है?
उत्तर
मुझे पता चला कि गहराई और ऊंचाई एक नोड के गुण हैं:
गहराई एक नोड के पेड़ की जड़ नोड के लिए नोड से किनारों की संख्या है।
एक रूट नोड 0.ऊंचाई एक नोड के की गहराई होगा एक पत्ते को नोड से सबसे लंबे समय तक पथ पर किनारों की संख्या है।
एक पत्ता नोड एक पेड़ की 0.
गुण की ऊंचाई होगा:, एक पेड़ की
ऊंचाई अपने रूट नोड की ऊंचाई होगा
या इसके समतुल्य, इसकी गहरी नोड की गहराई।व्यास (या चौड़ाई) एक पेड़ के नोड्स किसी भी दो पत्ती नोड्स के बीच सबसे लंबे समय तक मार्ग पर की संख्या है। नीचे का पेड़ 6 नोड्स का व्यास है।
+1 यहां से उसी सामग्री के साथ उद्धरण जोड़ने वाला था: http://en.wikipedia.org/wiki/Tree_%28data_structure%29 –
हम्म मैंने सोचा कि शब्दावली संदिग्ध नहीं है, हालांकि लिंक के लिए धन्यवाद। –
इसका मतलब है ऊंचाई == अधिकतम गहराई – roottraveller
Cormen एट अल के अनुसार। एल्गोरिदम का परिचय (परिशिष्ट बी .5.3), एक पेड़ टी में नोड एक्स की गहराई को टी से एक्स के रूट नोड से सरल पथ (किनारों की संख्या) की लंबाई के रूप में परिभाषित किया जाता है। नोड वाई की ऊंचाई पर सबसे लंबे समय तक किनारों की संख्या को वाई से एक पत्ते तक नीचे की ओर जाने की किनारों की संख्या। एक पेड़ की ऊंचाई को इसके रूट नोड की ऊंचाई के रूप में परिभाषित किया जाता है।
ध्यान दें कि एक साधारण पथ दोहराए गए शिखर के बिना पथ है।
पेड़ की ऊंचाई पेड़ की अधिकतम गहराई के बराबर है। नोड की गहराई और नोड की ऊंचाई आवश्यक नहीं है। कॉर्मन एट अल के तीसरे संस्करण के चित्र बी 6 देखें। इन अवधारणाओं के एक उदाहरण के लिए।
मैंने कभी-कभी किनारों की बजाय नोड्स (कोर्बिस) गिनने के लिए पूछने में समस्याएं देखी हैं, इसलिए यदि आप सुनिश्चित नहीं हैं कि आपको परीक्षा या नौकरी साक्षात्कार के दौरान नोड्स या किनारों की गणना करनी चाहिए तो स्पष्टीकरण मांगें।
क्या नोड्स और किनारों की गिनती में कोई अंतर है। ऐसा लगता है कि दोनों एक ही परिणाम देंगे। अगर मैं ग़लत हूं तो मेरी गलती सुझाएं। –
वे अलग हैं, उदाहरण के लिए, यदि आपके पास बाइनरी पेड़ है, तो रूट-> बाएं = बी, रूट-> दाएं = शून्य, यदि आप किनारे पर गिनते हैं, तो रूट की गहराई 1 है, यदि आप नोड्स गिनते हैं, तो रूट की गहराई 2. – jdhao
सरल उत्तर:
गहराई:
1. ट्री: किनारों की संख्या/पेड़ की पत्ती नोड के लिए रूट नोड से चाप पेड़ की गहराई के रूप में कहा जाता है।
2।नोड: रूट नोड से उस नोड तक किनारों/आर्क की संख्या को उस नोड की गहराई कहा जाता है।
ऊंचाई और एक पेड़ की गहराई के बराबर है ...
लेकिन ऊंचाई एक नोड की गहराई के बराबर नहीं है क्योंकि ...
ऊंचाई दी नोड से गहरी करने के लिए traversing करके की जाती है संभव पत्ता
गहराई जड़ से दिए गए नोड के लिए ट्रेवर्सल से की जाती है .....
"ऊंचाई की गणना पत्ती से दिए गए नोड से ट्रैवर्सिंग द्वारा की जाती है" यह सही नहीं है, पत्ती वह होनी चाहिए जो दिए गए नोड की सभी पत्तियों में गहरी हो। – mightyWOZ
उन अवधारणा को समझने की एक और तरीका है इस प्रकार है: गहराई: जड़ स्थान पर एक क्षैतिज रेखा खींचें और के रूप में इस लाइन का इलाज जमीन। तो रूट की गहराई 0 है, और उसके सभी बच्चे नीचे की ओर बढ़ रहे हैं इसलिए प्रत्येक स्तर के नोड्स की वर्तमान गहराई है + 1.
ऊंचाई: समान क्षैतिज रेखा लेकिन इस बार जमीन की स्थिति बाहरी नोड्स है, जो कि है पेड़ का पत्ता और ऊपर की गिनती।
मैं इस पोस्ट को बनाना चाहता था क्योंकि मैं एक अंडरग्रेड सीएस छात्र हूं और अधिक से अधिक हम ओपनडीएसए और अन्य ओपन सोर्स पाठ्यपुस्तकों का उपयोग करते हैं। यह शीर्ष मूल्यांकन वाले उत्तर की तरह लगता है कि जिस तरह से ऊंचाई और गहराई सिखाई जा रही है, वह एक पीढ़ी से अगले पीढ़ी में बदल गई है, और मैं इसे पोस्ट कर रहा हूं इसलिए सभी को पता है कि यह विसंगति अब मौजूद है और उम्मीद है कि किसी भी में बग का कारण नहीं होगा कार्यक्रमों! धन्यवाद।
OpenDSA Data Structures & Algos book से:
यदि n , एन , ..., n कश्मीर पेड़ में नोड्स के एक दृश्य है इस तरह के कि n मैं है n की मूल मैं +1 1 < = मैं < कश्मीर के लिए, तो इस क्रम n करने के लिए कश्मीर 0 एन से एक पथ कहा जाता है। पथ की लंबाई के -1 है। यदि नोड आर से नोड एम तक कोई पथ है, तो आर एम का पूर्वज है, और एम आर का वंशज है। इस प्रकार, पेड़ के सभी नोड पेड़ की जड़ के वंशज हैं, जबकि रूट सभी नोड्स का पूर्वज है। पेड़ में नोड एम की गहराई पेड़ की जड़ से पथ की लंबाई है। पेड़ की ऊंचाई पेड़ की गहरी नोड की गहराई की तुलना में एक पेड़ की ऊंचाई एक और है। गहराई के सभी नोड्स डी पेड़ में स्तर डी पर हैं। रूट स्तर 0 पर केवल नोड है, और इसकी गहराई 0.
चित्रा 7.2.1 है: एक द्विआधारी पेड़। नोड ए रूट है। नोड्स बी और सी ए के बच्चे हैं। नोड्स बी और डी एक साथ एक subtree बनाते हैं। नोड बी में दो बच्चे हैं: इसका बायां बच्चा खाली पेड़ है और इसका दायां बच्चा डी नोड्स ए, सी, और ई जी नोड्स डी, ई, और एफ के पूर्वजों के पेड़ के स्तर 2 बनाते हैं; नोड ए 0 स्तर पर है। से सी से ई तक जी के किनारे लंबाई का मार्ग बनाते हैं 3. नोड्स डी, जी, एच, और मैं पत्तियां हैं। नोड्स ए, बी, सी, ई, और एफ आंतरिक नोड्स हैं। मैं की गहराई 3 है। इस पेड़ की ऊंचाई 4 है।
- 1. बी-पेड़ और 2-3-4 पेड़ के बीच अंतर
- 2. छवि गहराई और चैनलों के बीच अंतर
- 3. पेड़ की अधिकतम गहराई
- 4. पेड़ और निर्देशिका के बीच क्या अंतर है?
- 5. क्वाड्री और केडी-पेड़ के बीच अंतर
- 6. ट्रे और पेड़ के बीच अंतर?
- 7. रिग्रेशन पेड़ और मॉडल पेड़ के बीच अंतर
- 8. पेड़ की ऊंचाई के लिए परिभाषा क्या है?
- 9. प्रत्यय पेड़ और कोशिशें। अंतर क्या है?
- 10. भिन्नता और '-' के बीच क्या अंतर है?
- 11. के बीच क्या अंतर है:। और: आर !?
- 12. एवीएल पेड़ और स्प्ले पेड़ों के बीच अंतर
- 13. आदेशित और अनियंत्रित (रूट) पेड़ के बीच अंतर
- 14. पार्स पेड़ और व्युत्पन्न पेड़ों के बीच कोई अंतर?
- 15. # {} $ {} और% {} के बीच क्या अंतर है?
- 16. [अपरिभाषित] और [,] के बीच क्या अंतर है?
- 17. $ और $$ के बीच क्या अंतर है?
- 18. "$^एन" और "$ +" के बीच क्या अंतर है?
- 19. नोड और वर्टेक्स के बीच क्या अंतर है?
- 20. डेटा संरचना वृक्ष और ग्राफ के बीच क्या अंतर है?
- 21. गहराई में एक अभिव्यक्ति पेड़
- 22. एंड्रॉइड के बीच क्या अंतर है: लेआउट_विड्थ और एंड्रॉइड: चौड़ाई
- 23. के बीच क्या अंतर है?
- 24. ग्रिड कॉलम के लिए चौड़ाई/ऊंचाई सेट करते समय 'ऑटो' और '*' के बीच क्या अंतर है?
- 25. अंतर और कहां के बीच क्या अंतर है?
- 26. एक बाइनरी खोज पेड़ की औसत ऊंचाई
- 27. दक्षता में ऐरे और बाइनरी खोज पेड़ के बीच क्या अंतर है?
- 28. file_get_contents और fread बीच क्या अंतर है
- 29. क्या बीच का अंतर है :: और ::: स्काला
- 30. "। +" और "। +?" के बीच अंतर
युक्ति: शब्दावली के बीच भ्रम से बचने के लिए: 1. ऊंचाई: किसी व्यक्ति की ऊंचाई को मापने की कल्पना करें, हम इसे पैर से पैर (रूट तक रूट) करते हैं। 2. गहराई: कल्पना करें कि समुद्र की गहराई को मापने के लिए, हम इसे पृथ्वी की सतह से सागर बिस्तर (पत्ती तक जड़) तक करते हैं। – Yesh
@Yesh यह एक महान सादृश्य है। –