रिकर्सन या स्टैक के बिना बीएसटी के इन-ऑर्डर ट्रैवर्सल को कैसे करें लेकिन पैरेंट पॉइंटर्स का उपयोग कैसे करें?

Question

क्या बीएसटी पर एक पुनरावर्तक इन-ऑर्डर-ट्रैवर्सल करना संभव है, जिसके पास visited ध्वज या stack का उपयोग किए बिना किसी नोड के माता-पिता पॉइंटर (रूट का पैरेंट null) है।

मैं googled और एक जवाब नहीं मिला। मुद्दा यह है कि, मुझे कैसे पता चलेगा - एक निश्चित नोड पर - कि मैं बस इसके पास आया हूं, लेकिन मैंने इसके नीचे सबकुछ खत्म कर लिया है?

Answer 1

आप ऐसा कर सकते हैं, आपको वर्तमान नोड के साथ अंतिम बार देखा गया नोड याद रखना होगा। ऐसा करने से यह समस्या बयान से अस्वीकृत नहीं है: प्रत्येक नोड पर दोनों visited ध्वज और stack (सबसे खराब स्थिति) हे ( n) कर रहे हैं, पिछले नोड याद सिर्फ हे है (1)।

सी # में, एल्गोरिथ्म ऐसा दिखाई दे सकता:

static void Walk(Node node) 
{ 
    Node lastNode = null; 
    while (node != null) 
    { 
     if (lastNode == node.Parent) 
     { 
      if (node.Left != null) 
      { 
       lastNode = node; 
       node = node.Left; 
       continue; 
      } 
      else 
       lastNode = null; 
     } 
     if (lastNode == node.Left) 
     { 
      Output(node); 

      if (node.Right != null) 
      { 
       lastNode = node; 
       node = node.Right; 
       continue; 
      } 
      else 
       lastNode = null; 
     } 
     if (lastNode == node.Right) 
     { 
      lastNode = node; 
      node = node.Parent; 
     } 
    } 
} 

Answer 2

कुंजी माता पिता संकेत (या पेड़ उत्परिवर्तित करने की क्षमता) है, लेकिन आप अतिरिक्त राज्य के एक निरंतर राशि की जरूरत है (जैसे, निम्नलिखित coroutine के कार्यक्रम काउंटर)।

1. रूट पर सेट v।
2. जबकि वी में एक बायां बच्चा है, तो अपने बाएं बच्चे को सेट करें।
3. यील्ड बनाम
4. यदि वी रूट है, तो वापस आएं।
5. पी को वी के माता-पिता को सेट करें।
6. यदि पी का सही बच्चा वी है, तो पी को सेट करें और चरण 4 पर जाएं।
7. यील्ड पी।
8. पी एक सही बच्चा है, तो पी के सही बच्चे को वी सेट और पी कदम 2.
9. सेट वी और चरण 4.

Answer 3

यहाँ एक और तरीका यह करने के लिए है जाने के लिए जाना। मुझे लगता है कि यह अनिवार्य रूप से svick के उत्तर के बराबर है, लेकिन अतिरिक्त चर से बचाता है। इस संस्करण में अजगर में कार्यान्वित किया जाता:

node=root 
if node is not None: 
    while node.left is not None: 
    node=node.left 
    while node is not None: 
    output(node) 
    if node.right is not None: 
     node=node.right 
     while node.left is not None: 
     node=node.left 
    else: 
     while node.parent is not None and node.parent.right is node: 
     node=node.parent 
     node=node.parent 

जो भी नोड आप पिछली बार देखे अगले नोड आप यात्रा करने के लिए की जरूरत है कि निर्धारित करता है। यदि आपने अभी नोड एक्स का दौरा किया है, तो आपको एक्स के दाईं ओर बाएं सबसे नोड पर जाना होगा। यदि एक्स का कोई सही बच्चा नहीं है, तो अगला नोड पहला पूर्वज है जहां नोड एक्स दाएं से नहीं आया था पक्ष।

Answer 4

svick का सही विचार (उसका answer देखें) का उपयोग करके, यह कोड C++ में परीक्षण किया गया है। ध्यान दें कि मैंने अपने कोड का परीक्षण नहीं किया है या यहां तक ​​कि इसे भी नहीं देखा है, मैंने अभी अपना विचार लिया और अपना खुद का कार्य लागू किया।

void in_order_traversal_iterative_with_parent(node* root) { 
node* current = root; 
node* previous = NULL; 

while (current) { 
    if (previous == current->parent) { // Traversing down the tree. 
     previous = current; 
     if (current->left) { 
      current = current->left; 
     } else { 
      cout << ' ' << current->data; 
      if (current->right) 
       current = current->right; 
      else 
       current = current->parent; 
     } 
    } else if (previous == current->left) { // Traversing up the tree from the left. 
     previous = current; 
     cout << ' ' << current->data; 
     if (current->right) 
      current = current->right; 
     else 
      current = current->parent; 
    } else if (previous == current->right) { // Traversing up the tree from the right. 
     previous = current; 
     current = current->parent; 
    } 
} 

cout << endl; 
} 

Answer 5

यह सी में है ++:

void InOrder(Node *r) 
{ 
    if(r==NULL) 
     return; 

    Node *t=r; 

    while(t!=NULL) 
     t=t->left; 

    while(t!=r) 
    { 
    if(t==(t->parent->left)) 
    { 
     cout<<t->parent->data; 
     t=t->parent->right; 
     if(t!=NULL) 
     { 
     while(t!=NULL) 
      t=t->left; 
     } 
     if(t==NULL) 
      t=t->parent; 
    } 
    if(t==t->parent->right) 
    { 
     t=t->parent; 
    } 
    } 
} 

Answer 6

public void inorderNoStack() { 
    if (root == null) { 
     return; 
    } 

    // use the previous to always track the last visited node 
    // helps in deciding if we are going down/up 
    Node prev = null; 

    Node curr = root; 

    while (curr != null) { 
     // going down 
     if (prev == null || prev.left == curr || prev.right == curr) { 
      if (curr.left != null) { 
       prev = curr; 
       curr = curr.left; 
       continue; 
      } else { 

       visitn(curr); 

       if (curr.right != null) { 
        prev = curr; 
        curr = curr.right; 
        continue; 
       } else { 
        // swap states 
        prev = curr; 
        curr = prev.parent; 
       } 
      } 
     } 

     // going up after left traversal 
     if (curr != null && prev == curr.left) { 

      visitn(curr); 

      if (curr.right != null) { 
       prev = curr; 
       curr = curr.right; 
       continue; 
      } else { 
       // swap states 
       prev = curr; 
       curr = prev.parent; 
      } 
     } 

     // going up after right traversal 
     if (curr != null && prev == curr.right) { 
      // swap states 
      prev = curr; 
      curr = prev.parent; 
     } 
    } 
} 

Answer 7

मेरे जावा मौजूदा पेड़ पर किसी भी ध्वज को शुरू करने के बिना समाधान। और कोई माता पिता भी नहीं। यह दृष्टिकोण पेड़ की ऊंचाई तक नोड्स रखेगा। कृपया एक नज़र डालें।

https://github.com/skanagavelu/Algorithams/blob/master/src/tree/InOrderTraversalIterative.java

Answer 8

चरण 1: एक समारोह जो रिटर्न बारे में आदेश उत्तराधिकारी

चरण 2: वाम-पंथी नोड के साथ शुरू, इन-आदेश उत्तराधिकारी खोजने के लिए जब तक कोई भी

public class TreeNode { 
     int data; 
     TreeNode left; 
     TreeNode right; 
     TreeNode parent; 
    } 

    public class TreeUtility { 
     public void inorderNoRecursion(TreeNode root) { 
     TreeNode current = leftmostNode(root); 
     while(current != null) { 
      System.out.println(current.data); 
      current = inorderSuccessor(current); 
     } 
     } 

     public TreeNode inorderSuccessor(TreeNode node) { 
     if (node.right!=null) { 
      return leftmostNode(node.right); 
     } 

     TreeNode p = node.parent; 
     TreeNode c = node; 
     while(p!=null && c != p.left) { 
      c = p; 
      p = p.parent; 
     } 
     return p; 
     } 

     private TreeNode leftmostNode(TreeNode node) { 
     while (node.left != null) { 
      node = node.left; 
     } 
     return node; 
     } 
    } 

है