बाइनरी ट्री

Question

के लिए कुशल ऐरे संग्रहण एक फ़ाइल में एक बाइनरी पेड़ के नोड्स लिखना है। बाइनरी पेड़ लिखने का सबसे अधिक सुविधाजनक तरीका क्या है। हम इसे पेरिस में स्थिति i और उसके बच्चों को 2i, 2i+1 में सरणी प्रारूप में संग्रहीत कर सकते हैं। लेकिन यह दुर्लभ बाइनरी पेड़ों के मामले में बहुत सी जगह बर्बाद कर देगा।

Answer 1

एक विधि जो मुझे पसंद है वह प्रीऑर्डर ट्रैवर्सल को स्टोर करना है, लेकिन वहां 'नल' नोड्स भी शामिल है। 'नल' नोड्स को संग्रहीत करना पेड़ के अंदरूनी हिस्से को भी स्टोर करने की आवश्यकता को हटा देता है।

इस विधि के कुछ लाभ

• बेहतर होगा कि तुम भंडारण कर सकते हैं पूर्व/पोस्ट से + सबसे व्यावहारिक मामलों में विधि inorder।
• सीरियलाइजेशन सिर्फ एक ट्रैवर्सल
• एक पास में deserialization किया जा सकता है।
• इनऑर्डर ट्रैवर्सल पेड़ के निर्माण के बिना एक पास में प्राप्त किया जा सकता है, जो स्थिति के लिए कॉल करने पर उपयोगी हो सकता है।

उदाहरण के लिए मान लीजिए कि आप था 64 बिट पूर्णांकों का एक द्विआधारी पेड़, आप के बाद प्रत्येक नोड कह अगले एक अशक्त नोड है या नहीं एक अतिरिक्त बिट स्टोर कर सकते हैं (प्रथम नोड हमेशा जड़ है)। नल नोड्स, आप एक बिट द्वारा प्रतिनिधित्व कर सकते हैं।

तो यदि एन नोड्स हैं, तो स्पेस उपयोग 8 एन बाइट्स + एन -1 सूचक संकेतक + एन + 1 बिट्स नल नोड्स = 66 * एन बिट्स के लिए होगा।

प्री/पोस्ट + इनऑर्डर में आप 16n बाइट्स = 128 * एन बिट्स का उपयोग कर समाप्त कर देंगे।

तो आप इस पूर्व/पोस्ट + इनऑर्डर विधि पर 62 * एन बिट्स की एक जगह सहेजते हैं।

पेड़ पर विचार करें

 100 
    / \ 
    / \ 
    /  \ 
    10  200 
/\  /\ 
. .  150 300 
     /\ /\ 
     . . . . 

जहां '।' नल नोड्स हैं।

आप के रूप 100 10 . . 200 150 . . 300 . .

अब यह क्रमानुसार प्रत्येक (subtrees सहित) 'अशक्त साथ अग्रिम-आदेश ट्रावर्सल' संपत्ति है कि रिक्त नोड्स की संख्या = नोड्स की संख्या + 1.

यह आपको बनाने की अनुमति देता है पेड़, एक पास में धारावाहिक संस्करण दिया, क्योंकि पहला नोड पेड़ की जड़ है।

100 (10 . .) (200 (150 . .) (300 . .)) 

inorder ट्रावर्सल बनाने के लिए, आप एक सूची पर एक ढेर का उपयोग करें और धक्का जब आप एक नोड और पॉप देखते हैं (: नोड्स का पालन करें कि बाईं सबट्री सही द्वारा पीछा किया है, जो इस तरह बनना देखी जा सकती है कर रहे हैं) जब आप एक शून्य देखते हैं। परिणामस्वरूप सूची इनऑर्डर ट्रैवर्सल है (इसके लिए एक विस्तृत स्पष्टीकरण यहां पाया जा सकता है: C++/C/Java: Anagrams - from original string to target;)।

Answer 2

आप in-order और pre/post-order फ़ाइल में बाइनरी पेड़ के ट्रैवर्सल को सहेज सकते हैं और इन ट्रैवर्सल से पेड़ का पुनर्निर्माण कर सकते हैं।

Answer 3

2i, 2i + 1 (बाइनरी हीप) विधि वास्तव में सबसे अच्छा तरीका है यदि आपके पास (लगभग) पूरा पेड़ है।

अन्यथा आप प्रत्येक नोड के साथ एक अभिभावक (मूल सूचकांक) को संग्रहित नहीं करेंगे।

Answer 4

एक्सएमएल के बारे में सोचें। यह एक प्रकार का पेड़ क्रमबद्धता है। उदाहरण के लिए:

<node id="1"> 
    <node id="2">         1 
    </node>          / \ 
    <node id="3">        2  3 
     <node id="4">        /\ 
     </node>          4 5 
     <node id="5"> 
     </node> 
    </node> 
</node> 

फिर, रिक्त स्थान और टैग क्यों? हम कदम से, उन्हें छोड़ सकते हैं कदम:

<1> 
    <2></> 
    <3> 
    <4></> 
    <5></> 
    </> 
</> 

रिक्त स्थान निकालें: <1><2></2><3><4></><5></></></>।

निकालें कोण कोष्ठक: 12/34/5///

अब समस्या है: एक नोड एक खाली छोड़ दिया सबट्री और गैर खाली सही सबट्री है क्या है? फिर हम एक खाली बाएं उप-पेड़ का प्रतिनिधित्व करने के लिए एक और विशेष गुणक, '#' का उपयोग कर सकते हैं।

उदाहरण के लिए: 1#23///:

1 
/ \ 
     2 
    /\ 
    3 

इस पेड़ के रूप में श्रृंखलाबद्ध जा सकता है।