बाइनरी ट्री ट्रैवर्सल: माता-पिता को पुनरावृत्ति, पुनरावृत्ति और सूचक

बाइनरी पेड़ों के बारे में मूल बातें यहां प्रस्तुत की गई हैं । मैं अपने "5 kopecks" जोड़ूंगा और इस पोस्ट में मैं द्विआधारी पेड़ों की कटाई से संबंधित सामग्रियों को व्यवस्थित करूँगा, अर्थात् पुनरावर्तन और पुनरावृत्ति क्षमताओं की तुलना करने के साथ-साथ मूल नोड के लिए पॉइंटर का उपयोग करने की संभावनाओं पर चर्चा करना।

तो ... जावा भाषा, नोड वर्ग में निम्न रूप है:

public class Node { Node left; Node right; Node parent; String value; public Node(Node p, String v){ parent=p; value=v; } … } 

नोट : मूल माता-पिता को इंगित करना - एक नियम के रूप में, इससे बहुत अधिक मतलब नहीं है, हालांकि, जैसा कि शीर्षक दिखाएगा, यह कई मामलों में उपयोगी हो सकता है।

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

प्रक्षेपवक्र के आधार पर, दो प्रकार के बाईपास प्रतिष्ठित हैं:
- क्षैतिज (चौड़ा); और
- ऊर्ध्वाधर (गहराई में)।

क्षैतिज ट्रैवर्सल का तात्पर्य है पेड़ को स्तरों (स्तर-क्रम) द्वारा ट्रेस करना - वर्तमान स्तर के पहले सभी नोड्स को संसाधित किया जाता है, जिसके बाद निचले स्तर पर संक्रमण किया जाता है।


एक ऊर्ध्वाधर ट्रैवर्सल के साथ, वर्तमान नोड के प्रसंस्करण क्रम और इसके दाएं और बाएं उपप्रकारों के नोड्स भिन्न होते हैं, और इस मानदंड के अनुसार ऊर्ध्वाधर ट्रैवर्सल के लिए तीन विकल्प हैं:
- प्रत्यक्ष (उपसर्ग, पूर्व-आदेशित): वर्टेक्स - बायाँ सबट्री - राइट सबट्री;
- रिवर्स (इन्फिक्स, इन-ऑर्डर): बाएं सबट्री - वर्टेक्स - राइट सबट्री; और
- अंत (पोस्टफिक्स, पोस्ट-ऑर्डर किया गया): बाएं सबट्री - राइट सबट्री - वर्टेक्स।

सभी मामलों में स्वयं बाईपास मूल रूप से समान है, प्रसंस्करण क्रम अलग है। यह दर्शाने के लिए कि ट्री नोड्स का प्रसंस्करण किस क्रम में होगा, "ट्रैवर्सल पाथ" का पालन करना सुविधाजनक है। एक प्रत्यक्ष बायपास के साथ, नोड नोड के नीचे से और अंत में, नोड के दाईं ओर के साथ, नोड के बाईं ओर एक बिंदु पर संसाधित किया जाएगा।
दूसरे शब्दों में, "एक निश्चित नोड में" होने के नाते, हमें यह जानना होगा कि क्या इसे संसाधित करने की आवश्यकता है और कहां चलना है।

प्रत्यावर्तन

वर्टिकल ट्रैवर्सल के सभी तीन वेरिएंट को पुनरावर्ती कार्यों द्वारा प्राथमिक रूप से लागू किया जाता है।

  void recPreOrder(){ treatment(); if (left!=null) left.recPreOrder(); if (right!=null) right.recPreOrder(); } void recInOrder(){ if (left!=null) left.recInOrder(); treatment(); if (right!=null) right.recInOrder(); } void recPostOrder(){ if (left!=null) left.recPostOrder(); if (right!=null) right.recPostOrder(); treatment(); } 

पुनरावृत्ति न केवल रेंगते समय, बल्कि एक पेड़ का निर्माण करते समय, एक पेड़ में खोज करते हुए, और संतुलन में भी बेहद सुविधाजनक है। हालाँकि, पुनरावर्तन क्षैतिज ट्री ट्रैवर्सल की अनुमति नहीं देता है। इस मामले में, साथ ही सॉफ़्टवेयर स्टैक को ओवरलोड करने के बारे में चिंताओं के साथ, एक पुनरावृत्त दृष्टिकोण का उपयोग किया जाना चाहिए।

कंटेनर

पुनरावृत्तियों का उपयोग करने के मामले में, विज़िट किए गए लेकिन संसाधित नोड्स के बारे में जानकारी संग्रहीत करना आवश्यक है। स्टैक कंटेनरों का उपयोग (ऊर्ध्वाधर ट्रैवर्सल के लिए) और कतार (क्षैतिज ट्रैवर्सल के लिए) किया जाता है।

क्षैतिज बाईपास:

हम कतार में पहले नोड को संसाधित करते हैं, अगर बच्चे के नोड होते हैं, तो हम उन्हें कतार के अंत में डालते हैं। हम अगले पुनरावृत्ति में पास होते हैं।

  static void contLevelOrder(Node top){ Queue<Node> queue=new LinkedList<> (); do{ top.treatment(); if (top.left!=null) queue.add(top.left); if (top.right!=null) queue.add(top.right); if (!queue.isEmpty()) top=queue.poll(); }while (!queue.isEmpty()); } 

ऊर्ध्वाधर प्रत्यक्ष बाईपास:

हम वर्तमान नोड को संसाधित करते हैं, अगर कोई सही सबट्री है, तो इसे आगे की प्रक्रिया के लिए स्टैक में जोड़ें। हम बाईं सबट्री के नोड को पास करते हैं। यदि कोई शेष नोड नहीं है, तो स्टैक से शीर्ष नोड पर जाएं।

  static void contPreOrder(Node top){ Stack<Node> stack = new Stack<> (); while (top!=null || !stack.empty()){ if (!stack.empty()){ top=stack.pop(); } while (top!=null){ top.treatment(); if (top.right!=null) stack.push(top.right); top=top.left; } } } 

कार्यक्षेत्र बैकट्रेस:

वर्तमान नोड से हम सबसे निचले बाएं नोड में "नीचे" जाते हैं, स्टैक को जोड़कर सभी विज़िट किए गए नोड्स। हम स्टैक से शीर्ष नोड को संसाधित करते हैं। यदि वर्तमान नोड में एक सही सबट्री है, तो अगले नोड को राइट नोड से शुरू करें। यदि कोई सही नोड नहीं है, तो हम डिसेंट स्टेप को छोड़ देते हैं और स्टैक से अगले नोड को संसाधित करने के लिए आगे बढ़ते हैं।

  static void contInOrder(Node top){ Stack<Node> stack = new Stack<> (); while (top!=null || !stack.empty()){ if (!stack.empty()){ top=stack.pop(); top.treatment(); if (top.right!=null) top=top.right; else top=null; } while (top!=null){ stack.push(top); top=top.left; } } } 

कार्यक्षेत्र अंत बायपास:

यहां स्थिति जटिल है - राउंड ट्रिप के विपरीत, वंश क्रम के अलावा, आपको यह जानना होगा कि क्या सही सबट्री पहले ही संसाधित हो चुकी है। एक समाधान नोड के प्रत्येक उदाहरण में एक ध्वज शामिल करना है जो प्रासंगिक जानकारी (विचार नहीं) को संग्रहीत करता है। एक अन्य दृष्टिकोण स्टैक ऑर्डर में सीधे "कोडिंग" है - वंश के दौरान, यदि अगले नोड को बाद में सही सबट्री प्रक्रिया करने की आवश्यकता होती है, तो अनुक्रम "पैरेंट, राइट नोड, पैरेंट" को स्टैक पर धकेल दिया जाता है। इस प्रकार, जब स्टैक से नोड्स को संसाधित करते हैं, तो हम यह निर्धारित कर सकते हैं कि क्या हमें सही सबट्री को संसाधित करने की आवश्यकता है।

  static void contPostOrder(Node top){ Stack<Node> stack = new Stack<> (); while (top!=null || !stack.empty()){ if (!stack.empty()){ top=stack.pop(); if (!stack.empty() && top.right==stack.lastElement()){ top=stack.pop(); }else{ top.treatment(); top=null; } } while (top!=null){ stack.push(top); if (top.right!=null){ stack.push(top.right); stack.push(top); } top=top.left; } } } 

जनक सूचक के बारे में

कक्षा के उदाहरण में माता-पिता को एक सूचक की उपस्थिति पेड़ों के निर्माण और संतुलन में कुछ परेशानियां लाती है। हालाँकि, पेड़ के किसी भी नोड से उसके किसी भी नोड तक "पहुँचने" की क्षमता काम आ सकती है। ऊपरी स्तर पर "वृद्धि" के दौरान उन सभी पर नजर रखने की आवश्यकता है - चाहे वह दाएं वंश से आया हो या बाएं से।
इसलिए, पेरेंट पॉइंटर्स का उपयोग करते हुए, वर्टिकल एंड ट्रैवर्सल के लिए कोड दिखेगा।

  static void parentPostOrder(Node top){ boolean fromright=false; Node shuttle=top, holder; while(true){ while (fromright){ shuttle.treatment(); if (shuttle==top) return; holder=shuttle; shuttle=shuttle.parent; fromright=shuttle.right==holder; if (!fromright && shuttle.right!=null) shuttle=shuttle.right; else fromright=true; } while (shuttle.left!=null) shuttle=shuttle.left; if (shuttle.right!=null) shuttle=shuttle.right; else fromright=true; } } 

कार्यों का एक और वर्ग जो माता-पिता सूचक को हल करने की अनुमति देता है, जैसा कि पहले ही उल्लेख किया गया है, पेड़ के अंदर चल रहा है।
तो, वर्तमान नोड से n- वें नोड पर जाने के लिए, "ट्री में ओरिएंटेशन" के बिना, आपको पेड़ के चारों ओर बहुत शुरुआत से, ज्ञात नोड तक, और फिर एक और एन-नोड पर जाना होगा। पैरेंट पॉइंटर का उपयोग करते समय, पेड़ को ट्रेस करते समय, नोड्स के चरणों को वर्तमान नोड (प्रारंभ) से स्थानांतरित करने के बाद निम्न रूप होगा।

  public static Node walkTheTree(Node start, int steps){ boolean fromright=true; Node shuttle=start, holder; if (shuttle.right!=null){ shuttle=shuttle.right; while (shuttle.left!=null) shuttle=shuttle.left; fromright=false; } int counter=0; do{ while (true){ if (!fromright && ++counter==steps) return shuttle; if (!fromright && shuttle.right!=null){ shuttle=shuttle.right; break; } holder=shuttle; shuttle=shuttle.parent; fromright=(holder==shuttle.right); } while (shuttle.left!=null) shuttle=shuttle.left; }while (true); } 

नोट : सामान्य स्थिति में, पेड़ से परे जाने (रूट नोड से ऊपर उठने) की कोशिश करने की संभावना को रोकने के लिए भी आवश्यक है।