दिलचस्प पोस्ट
आर में टाइमस्टैंप के साथ व्यवहार करना मैं यूनिकोड एसेक अनुक्रमों को एक .net स्ट्रिंग में यूनिकोड वर्णों में कैसे परिवर्तित कर सकता हूं? जेएसएफ पेज में ग्राफ़िक छवि के रूप में छवि को बाइट के रूप में चित्र दिखाएं रीयलएम ऑब्जेक्ट से फील्ड वैल्यू पुनर्प्राप्त नहीं की जा सकती, मान डीबगर में शून्य हैं किसी भी एंड्रॉइड डिज़ाइन समर्थन पुस्तकालय तत्वों का उपयोग करते समय त्रुटि क्या मैं XmlSerializer को deserialization पर नामस्थान को अनदेखा कर सकता हूं? पायथन के अंदर "पीआईपी स्थापित" क्यों एक सिंटेक्स एरर उठाती है? जावा में एक प्रक्रिया शुरू कर रहा है? IE 11 के लिए एक सीएसएस हैक कैसे लिखूँ? ओपनएमपी, परमाणु बनाम महत्वपूर्ण? मैं बंटवारे स्ट्रिंग्स के बिना सूची को कैसे समतल कर सकता हूं? जेवीएम के लुकअप स्विच और टेबलस्विच के बीच का अंतर? DIV को 100% शरीर की ऊँचाई, शून्य से तय-ऊँचाई शीर्षलेख और पादलेख लेना क्या मैं MySQL में एक डिफ़ॉल्ट मान के लिए फ़ंक्शन का उपयोग कर सकता हूं? मेरी स्थिर फाइलों को एक्सेस करने के लिए मुझे http। StripPrefix का उपयोग करने की आवश्यकता क्यों है?

स्टेक्स या रिकर्सन का उपयोग किए बिना मॉरिस इनरडर ट्री ट्रवर्सल को बताएं

क्या कोई कृपया मुझे निम्नलिखित मॉरिस इनडर ट्री ट्रवर्सल एल्गोरिदम को ढेर या पुनर्रचना का उपयोग किए बिना समझने में सहायता करता है? मैं यह समझने की कोशिश कर रहा था कि यह कैसे काम करता है, लेकिन यह सिर्फ मुझे बचाना

1. Initialize current as root 2. While current is not NULL If current does not have left child a. Print current's data b. Go to the right, ie, current = current->right Else a. In current's left subtree, make current the right child of the rightmost node b. Go to this left child, ie, current = current->left 

मैं समझता हूं कि पेड़ को इस तरह संशोधित किया गया है कि current node max node को right subtreeright subtree में max node का right child बनाया गया है और इस संपत्ति का उपयोग इनरड्रा ट्रसर्सल के लिए किया गया है। लेकिन उससे परे, मैं खो गया हूं

संपादित करें: इस साथ सी ++ कोड मिला मुझे समझने में मुश्किल हो रही थी कि इसे संशोधित करने के बाद पेड़ को कैसे बहाल किया जाए। जादू else खंड में है, जो सही पट्टी को संशोधित होने के बाद मारा जाता है। विवरण के लिए कोड देखें:

 /* Function to traverse binary tree without recursion and without stack */ void MorrisTraversal(struct tNode *root) { struct tNode *current,*pre; if(root == NULL) return; current = root; while(current != NULL) { if(current->left == NULL) { printf(" %d ", current->data); current = current->right; } else { /* Find the inorder predecessor of current */ pre = current->left; while(pre->right != NULL && pre->right != current) pre = pre->right; /* Make current as right child of its inorder predecessor */ if(pre->right == NULL) { pre->right = current; current = current->left; } // MAGIC OF RESTORING the Tree happens here: /* Revert the changes made in if part to restore the original tree ie, fix the right child of predecssor */ else { pre->right = NULL; printf(" %d ",current->data); current = current->right; } /* End of if condition pre->right == NULL */ } /* End of if condition current->left == NULL*/ } /* End of while */ } 

वेब के समाधान से एकत्रित समाधान "स्टेक्स या रिकर्सन का उपयोग किए बिना मॉरिस इनरडर ट्री ट्रवर्सल को बताएं"

अगर मैं एल्गोरिदम सही पढ़ रहा हूं, तो यह एक उदाहरण होगा कि यह कैसे काम करता है:

  X / \ YZ / \ / \ ABCD 

सबसे पहले, X रूट है, इसलिए इसे current रूप में आरंभ किया गया है। X पास एक बाएं बच्चा है, इसलिए X को X के बाएं उप-प्रक्षेपण का सबसे सही सही बच्चा बनाया गया है – एक आवक ट्रवर्सल में X के तत्काल पूर्ववर्ती। तो X को B का सही बच्चा बनाया जाता है, फिर current Y सेट होता है। पेड़ अब इस तरह दिखता है:

  Y / \ AB \ X / \ (Y) Z / \ CD 

(Y) ऊपर Y और उसके सभी बच्चों को संदर्भित करता है, जो पुनरावर्ती मुद्दों के लिए छोड़े गए हैं। महत्वपूर्ण हिस्सा वैसे भी सूचीबद्ध है। अब जब पे पे एक्स को एक लिंक है, ट्रवर्सल जारी है …

  A \ Y / \ (A) B \ X / \ (Y) Z / \ CD 

फिर A आउटपुट हो गया है, क्योंकि इसमें कोई छोड़ा बच्चा नहीं है, और current Y में वापस आ जाता है, जो कि A के सही बच्चे को पिछले यात्रा में बनाया गया था। अगले पुनरावृत्ति पर, वाई के दोनों बच्चे हैं हालांकि, लूप की दोहरी स्थिति यह रोकती है जब वह स्वयं तक पहुंच जाती है, जो यह संकेत है कि इसे छोड़ दिया गया है, पहले से ही ट्रावर्स हो गया है। इसलिए, यह स्वयं छापता है, और इसके सही उप-प्रक्षेपण के साथ जारी है, जो B

B खुद को छापता है, और फिर X बन जाता है, जो वही जांच प्रक्रिया के माध्यम से चला जाता है जैसे Y था, यह भी यह महसूस करता है कि इसके बाएं उप-प्रक्षेपण को पारित किया गया है, Z साथ जारी है। बाकी का पेड़ एक ही पैटर्न का अनुसरण करता है।

कोई रिकर्सन आवश्यक नहीं है, क्योंकि स्टैक के माध्यम से बैक-ट्रैक्लिंग पर निर्भर होने के बजाय, (उप) पेड़ की जड़ में एक लिंक को उस स्थान पर ले जाया जाता है, जिस पर इसे फिर से रिकॉर्वर वृक्ष पेड़ एल्गोरिथ्म में प्रवेश किया जाएगा – उसके बाद छोड़ा सबट्री समाप्त हो गया है

 public static void morrisInOrder(Node root) { Node cur = root; Node pre; while (cur!=null){ if (cur.left==null){ System.out.println(cur.value); cur = cur.right; // move to next right node } else { // has a left subtree pre = cur.left; while (pre.right!=null){ // find rightmost pre = pre.right; } pre.right = cur; // put cur after the pre node Node temp = cur; // store cur node cur = cur.left; // move cur to the top of the new tree temp.left = null; // original cur left be null, avoid infinite loops } } } 

मुझे लगता है कि यह कोड समझने में बेहतर होगा, सिर्फ असीमित छोरों से बचने के लिए नल का उपयोग करें, जादू और अन्य का उपयोग करने की आवश्यकता नहीं है यह आसानी से preorder के लिए संशोधित किया जा सकता है।

मुझे आशा है कि छद्म कोड नीचे अधिक खुलासा है:

 node = root while node != null if node.left == null visit the node node = node.right else let pred_node be the inorder predecessor of node if pred_node.right == null /* create threading in the binary tree */ pred_node.right = node node = node.left else /* remove threading from the binary tree */ pred_node.right = null visit the node node = node.right 

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

रिकर्सिव इन-ऑर्डर ट्रवर्सल है: (in-order(left)->key->in-order(right)) (यह डीएफएस के समान है)

जब हम डीएफएस करते हैं, तो हमें यह जानने की जरूरत है कि हम किस तरह से बैकग्राउंड करते हैं (इसीलिए हम आम तौर पर एक स्टैक रखते हैं)।

जैसा कि हम एक अभिभावक नोड के माध्यम से जाते हैं, जिसके लिए हमें पीछे की तरफ -> हमें नोड मिल सकता है जिसे हमें पीछे से और माता-पिता नोड के लिंक को अपडेट करने की आवश्यकता होगी।

जब हम पीछे? जब हम आगे नहीं जा सकते जब हम आगे नहीं जा सकते हैं? जब कोई छोड़ा बच्चा मौजूद नहीं है

जहां हम पीछे हैं? सूचना: सफलता के लिए!

इसलिए, जैसा कि हम बाएं-बच्चा पथ के नोड्स का पालन करते हैं, वर्तमान नोड को इंगित करने के लिए प्रत्येक चरण में पूर्ववर्ती सेट करें। इस तरह, पूर्ववर्तियों के उत्तराधिकारियों के लिए लिंक (बैक ट्रैकिंग के लिए एक लिंक) होगा।

हम पीछे छोड़ते हैं, जब तक कि हम पीछे की जरूरत नहीं कर सकते। जब हमें पीछे की आवश्यकता होती है, तो हम वर्तमान नोड को प्रिंट करते हैं और उत्तराधिकारी के लिए सही लिंक का पालन करते हैं।

अगर हम अभी पीछे हैं -> हमें सही बच्चे का पालन करने की आवश्यकता है (हम बायीं बच्चे के साथ किए गए हैं)

यह कैसे बताने के लिए कि हम अभी पीछे हैं? वर्तमान नोड के पूर्ववर्ती प्राप्त करें और जांचें कि क्या इसमें एक नयी लिंक है (इस नोड के लिए)। यदि इसके पास है – इसके बाद हमने इसका अनुसरण किया था पेड़ को बहाल करने के लिए लिंक को हटा दें

अगर कोई बाएं लिंक नहीं था तो = हमने वापस नहीं छोड़ा और बाएं बच्चों के पीछे आगे बढ़ना चाहिए।

यहां मेरा जावा कोड है (क्षमा करें, यह सी ++ नहीं है)

 public static <T> List<T> traverse(Node<T> bstRoot) { Node<T> current = bstRoot; List<T> result = new ArrayList<>(); Node<T> prev = null; while (current != null) { // 1. we backtracked here. follow the right link as we are done with left sub-tree (we do left, then right) if (weBacktrackedTo(current)) { assert prev != null; // 1.1 clean the backtracking link we created before prev.right = null; // 1.2 output this node's key (we backtrack from left -> we are finished with left sub-tree. we need to print this node and go to right sub-tree: inOrder(left)->key->inOrder(right) result.add(current.key); // 1.15 move to the right sub-tree (as we are done with left sub-tree). prev = current; current = current.right; } // 2. we are still tracking -> going deep in the left else { // 15. reached sink (the leftmost element in current subtree) and need to backtrack if (needToBacktrack(current)) { // 15.1 return the leftmost element as it's the current min result.add(current.key); // 15.2 backtrack: prev = current; current = current.right; } // 4. can go deeper -> go as deep as we can (this is like dfs!) else { // 4.1 set backtracking link for future use (this is one of parents) setBacktrackLinkTo(current); // 4.2 go deeper prev = current; current = current.left; } } } return result; } private static <T> void setBacktrackLinkTo(Node<T> current) { Node<T> predecessor = getPredecessor(current); if (predecessor == null) return; predecessor.right = current; } private static boolean needToBacktrack(Node current) { return current.left == null; } private static <T> boolean weBacktrackedTo(Node<T> current) { Node<T> predecessor = getPredecessor(current); if (predecessor == null) return false; return predecessor.right == current; } private static <T> Node<T> getPredecessor(Node<T> current) { // predecessor of current is the rightmost element in left sub-tree Node<T> result = current.left; if (result == null) return null; while(result.right != null // this check is for the case when we have already found the predecessor and set the successor of it to point to current (through right link) && result.right != current) { result = result.right; } return result; }