में आदेश द्विआधारी पेड़

Question

के लिए इटरेटर मैं एक जावा इटरेटर कैसे लिख सकते हैं (यानी जरूरत next और hasNext विधि) कि फैशन में-आदेश में द्विआधारी पेड़ के नोड्स के माध्यम से एक द्विआधारी पेड़ और दोहराता की जड़ लेता है ?

visit_node(node) 
    if node.left: visit_node(node.left) 
    // visit the root node 
    if node.right: visit_node(node.right) 

आरेख:

 a 
/ \  (in-order traversal would give bac) 
    b  c 

Answer 1

उपट्री का पहला तत्व हमेशा बाईं ओर होता है। तत्व के बाद अगला तत्व इसके दाएं उपट्री का पहला तत्व है। यदि तत्व का सही बच्चा नहीं है, तो अगला तत्व तत्व का पहला दायां पूर्वज है। यदि तत्व में न तो सही बच्चा है और न ही सही पूर्वज है, तो यह सही तत्व है और यह पुनरावृत्ति में आखिरी है।

मुझे आशा है कि मेरा कोड मानव पठनीय है और सभी मामलों को शामिल करता है।

public class TreeIterator { 
    private Node next; 

    public TreeIterator(Node root) { 
     next = root; 
     if(next == null) 
      return; 

     while (next.left != null) 
      next = next.left; 
    } 

    public boolean hasNext(){ 
     return next != null; 
    } 

    public Node next(){ 
     if(!hasNext()) throw new NoSuchElementException(); 
     Node r = next; 

     // If you can walk right, walk right, then fully left. 
     // otherwise, walk up until you come from left. 
     if(next.right != null) { 
      next = next.right; 
      while (next.left != null) 
       next = next.left; 
      return r; 
     } 

     while(true) { 
      if(next.parent == null) { 
       next = null; 
       return r; 
      } 
      if(next.parent.left == next) { 
       next = next.parent; 
       return r; 
      } 
      next = next.parent; 
     } 
    } 
} 

निम्नलिखित पेड़ पर विचार करें:

 d 
/ \ 
    b  f 
/\ /\ 
a c e g 

• पहला तत्व
• a एक सही बच्चे नहीं है "पूरी तरह से जड़ से छोड़ दिया" है, इसलिए अगले तत्व "ऊपर है जब तक आप बाएं से नहीं आते हैं "
• b का सही बच्चा है, इसलिए b का दायां उपट्री
• c में कोई सही बच्चा नहीं है। यह माता-पिता b है, जिसे पार किया गया है। अगला माता-पिता d है, जिसे पार नहीं किया गया है, इसलिए यहां रुकें।
• d का एक अधिकार उप-अधिकार है। इसका बायां तत्व e है।
• ...
• g का कोई अधिकार उप-नियम नहीं है, इसलिए चलें। f का दौरा किया गया है, क्योंकि हम सही से आए हैं। d का दौरा किया गया है। d में कोई अभिभावक नहीं है, इसलिए हम आगे बढ़ नहीं सकते हैं। हम सही नोड से आए हैं और हम फिर से काम कर रहे हैं।

Answer 2

यह आप बाईं बच्चे की यात्रा करता है, तो वहाँ एक है, तो रूट नोड है, तो सही बच्चे में से आदेश ट्रावर्सल के लिए बहुत सीधे आगे है, अगली प्रविष्टि प्राप्त करने के लिए, इटरेटर के लिए 'nextEntry()', मैंने नीचे चिपकाए java.util.TreeMap से स्निपेट को देखा। सादे अंग्रेजी में, मैं कहूंगा कि आप सुनिश्चित करते हैं कि रूट नोड शून्य नहीं है और फिर शून्य वापस आ जाए। यदि यह नहीं है, तो सही नोड को झुकाएं यदि यह शून्य नहीं है। फिर बाईं ओर जाएं (यदि शून्य नहीं है) और शून्य के मारने तक थोड़ी देर में उस समय के बाईं ओर जाएं। यदि मूल दाएं नोड शून्य है तो उसके बजाय, माता-पिता नोड पर जाएं यदि यह शून्य नहीं है। अब थोड़ी देर लूप दर्ज करें जहां आप माता-पिता को तब तक झुकाएं जब तक कि यह नल या नोड जो आप वर्तमान में देख रहे हों, उसके पास आपकी अंतिम स्थिति के बराबर सही (बच्चा) नोड है। अब जो भी प्रविष्टि आप बैठ रहे हैं उसे वापस करें। उन सभी विकल्पों को विफल करना, मूल (मूल) रूट नोड वापस करें। 'हैसनेक्स्ट()' केवल जांचता है कि क्या यह "अगली प्रविष्टि" आप वापस लौट रहे हैं या नहीं।

public final boolean hasNext() { 
    return next != null; 
} 

final TreeMap.Entry<K,V> nextEntry() { 
    TreeMap.Entry<K,V> e = next; 
    if (e == null || e.key == fenceKey) 
     throw new NoSuchElementException(); 
    if (m.modCount != expectedModCount) 
     throw new ConcurrentModificationException(); 
    next = successor(e); 
    lastReturned = e; 
    return e; 
} 

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) { 
    if (t == null) 
     return null; 
    else if (t.right != null) { 
     Entry<K,V> p = t.right; 
     while (p.left != null) 
      p = p.left; 
     return p; 
    } else { 
     Entry<K,V> p = t.parent; 
     Entry<K,V> ch = t; 
     while (p != null && ch == p.right) { 
      ch = p; 
      p = p.parent; 
     } 
     return p; 
    } 
} 

Answer 3