पेड़ की गहराई और ऊंचाई के बीच क्या अंतर है?

Question

यह एल्गोरिदम सिद्धांत से एक साधारण सवाल है। उनके बीच का अंतर यह है कि एक मामले में आप नोड्स की संख्या और रूट और कंक्रीट नोड के बीच सबसे कम पथ पर किनारों की संख्या की गणना करते हैं। कौन सा क्या है?

Answer 1

मुझे पता चला कि गहराई और ऊंचाई एक नोड के गुण हैं:

• गहराई एक नोड के पेड़ की जड़ नोड के लिए नोड से किनारों की संख्या है।
  एक रूट नोड 0.

• ऊंचाई एक नोड के की गहराई होगा एक पत्ते को नोड से सबसे लंबे समय तक पथ पर किनारों की संख्या है।
  एक पत्ता नोड एक पेड़ की 0.

गुण की ऊंचाई होगा:, एक पेड़ की

• ऊंचाई अपने रूट नोड की ऊंचाई होगा
  या इसके समतुल्य, इसकी गहरी नोड की गहराई।

• व्यास (या चौड़ाई) एक पेड़ के नोड्स किसी भी दो पत्ती नोड्स के बीच सबसे लंबे समय तक मार्ग पर की संख्या है। नीचे का पेड़ 6 नोड्स का व्यास है।

Answer 2

Cormen एट अल के अनुसार। एल्गोरिदम का परिचय (परिशिष्ट बी .5.3), एक पेड़ टी में नोड एक्स की गहराई को टी से एक्स के रूट नोड से सरल पथ (किनारों की संख्या) की लंबाई के रूप में परिभाषित किया जाता है। नोड वाई की ऊंचाई पर सबसे लंबे समय तक किनारों की संख्या को वाई से एक पत्ते तक नीचे की ओर जाने की किनारों की संख्या। एक पेड़ की ऊंचाई को इसके रूट नोड की ऊंचाई के रूप में परिभाषित किया जाता है।

ध्यान दें कि एक साधारण पथ दोहराए गए शिखर के बिना पथ है।

पेड़ की ऊंचाई पेड़ की अधिकतम गहराई के बराबर है। नोड की गहराई और नोड की ऊंचाई आवश्यक नहीं है। कॉर्मन एट अल के तीसरे संस्करण के चित्र बी 6 देखें। इन अवधारणाओं के एक उदाहरण के लिए।

मैंने कभी-कभी किनारों की बजाय नोड्स (कोर्बिस) गिनने के लिए पूछने में समस्याएं देखी हैं, इसलिए यदि आप सुनिश्चित नहीं हैं कि आपको परीक्षा या नौकरी साक्षात्कार के दौरान नोड्स या किनारों की गणना करनी चाहिए तो स्पष्टीकरण मांगें।

Answer 3

सरल उत्तर:
गहराई:
1. ट्री: किनारों की संख्या/पेड़ की पत्ती नोड के लिए रूट नोड से चाप पेड़ की गहराई के रूप में कहा जाता है।
2।नोड: रूट नोड से उस नोड तक किनारों/आर्क की संख्या को उस नोड की गहराई कहा जाता है।

Answer 4

ऊंचाई और एक पेड़ की गहराई के बराबर है ...

लेकिन ऊंचाई एक नोड की गहराई के बराबर नहीं है क्योंकि ...

ऊंचाई दी नोड से गहरी करने के लिए traversing करके की जाती है संभव पत्ता

गहराई जड़ से दिए गए नोड के लिए ट्रेवर्सल से की जाती है .....

Answer 5

उन अवधारणा को समझने की एक और तरीका है इस प्रकार है: गहराई: जड़ स्थान पर एक क्षैतिज रेखा खींचें और के रूप में इस लाइन का इलाज जमीन। तो रूट की गहराई 0 है, और उसके सभी बच्चे नीचे की ओर बढ़ रहे हैं इसलिए प्रत्येक स्तर के नोड्स की वर्तमान गहराई है + 1.

ऊंचाई: समान क्षैतिज रेखा लेकिन इस बार जमीन की स्थिति बाहरी नोड्स है, जो कि है पेड़ का पत्ता और ऊपर की गिनती।

Answer 6

मैं इस पोस्ट को बनाना चाहता था क्योंकि मैं एक अंडरग्रेड सीएस छात्र हूं और अधिक से अधिक हम ओपनडीएसए और अन्य ओपन सोर्स पाठ्यपुस्तकों का उपयोग करते हैं। यह शीर्ष मूल्यांकन वाले उत्तर की तरह लगता है कि जिस तरह से ऊंचाई और गहराई सिखाई जा रही है, वह एक पीढ़ी से अगले पीढ़ी में बदल गई है, और मैं इसे पोस्ट कर रहा हूं इसलिए सभी को पता है कि यह विसंगति अब मौजूद है और उम्मीद है कि किसी भी में बग का कारण नहीं होगा कार्यक्रमों! धन्यवाद।

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 है।