सभी पत्तियों को खोजने के लिए बाइनरी सर्च पेड़ के माध्यम से Iterate

Question

मैं पेड़ों के लिए काफी नया हूं, और मैं एक "पत्ता इटरेटर" बनाने की कोशिश कर रहा हूं। मुझे लगता है कि यह उन सभी नोड्स को रखना चाहिए जिनके पास .left और .right वैल्यू पर मूल्य नहीं है, लेकिन मुझे यकीन नहीं है कि यह करने के लिए सही काम कैसे है या नहीं। मैंने इसके लिए खोज करने की कोशिश की है, लेकिन मेरे द्वारा आने वाले प्रत्येक उदाहरण को बाएं पत्ते पर जाने के साथ शुरू होता है, और p = node.parent पर जा रहा है, और मैं नोड के माता-पिता से जुड़ने से परहेज कर रहा हूं।

मुझे समझ में नहीं आता कि मैं रूट से बार-बार कैसे शुरू कर सकता हूं और उसी दाखलताओं के बिना दाखलताओं के माध्यम से जा सकता हूं।

संपादित

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

Answer 1

उपयोग प्रत्यावर्तन: आदेश में एक Iterator<Node> में इस अनुवाद करने के लिए आप पाश को प्रत्यावर्तन का अनुवाद करना होगा में

visitNode(root); 

और उसके बाद राज्य के साथ Traversal रहे हैं:

public void visitNode(Node node) { 
    if(node.left != null) { 
     visitNode(node.left); 
    } 
    if(node.right != null) { 
     visitNode(node.right); 
    } 
    if(node.left == null && node.right == null) { 
     //OMG! leaf! 
    } 
} 

root की आपूर्ति करके इसे शुरू

। गैर-तुच्छ, लेकिन आपको बहुत मज़ा देना चाहिए।

Answer 2

class Node { 
    public Node left = null; 
    public Node right = null; 
    // data and other goodies 
} 
class Tree { 
    public Node root = null; 
    // add and remove methods, etc. 
    public void visitAllLeaves(Node root) { 
     // visit all leaves starting at the root 
     java.util.Stack<Node> stack = new java.util.Stack<Node>(); 
     if (root == null) return; // check to make sure we're given a good node 
     stack.push(root); 
     while (!stack.empty()) { 
      root = stack.pop(); 
      if (root.left == null && root.right == null) { 
       // this is a leaf 
       // do stuff here 
      } 
      if (root.left != null) { 
       stack.push(root.left); 
      } 
      if (root.right != null) { 
       stack.push(root.right); 
      } 
     } 
    } 
} 

मुझे यकीन है कि अगर इसके बाद के संस्करण कोड काम करता है नहीं कर रहा हूँ, लेकिन यह है कि क्या किया जाना चाहिए की तर्ज पर कहीं है। एक और विकल्प javax.swing.TreeModel (आधा मजाक) है।

Answer 3

यहां बताया गया है कि कोई एक इटरेटर कैसे कार्यान्वित कर सकता है जो केवल पत्ती नोड्स, यानी नोड्स को बाएं या दाएं उपट्री के बिना वापस कर देगा।

इटेटरेटर गहराई से पहली खोज करके पेड़ में पत्ती नोड्स की खोज करता है, एक स्टैक में खोज की वर्तमान स्थिति को याद करता है और जब इसे पत्ती नोड मिला है तो "रोकना" (fetchNext() विधि देखें)।

जब ग्राहक अगले() को कॉल करके पत्ती नोड "उपभोग" करता है तो खोज फिर से शुरू हो जाती है।

class Node { 
    public Node left; 
    public Node right; 
} 

class LeaveIterator implements Iterator<Node> { 
    private final Stack<Node> stack = new Stack<>(); 
    private Node nextNode = null; 

    public LeaveIterator(Node root) { 
    if (root != null) { 
     stack.push(root); 
     nextNode = fetchNext(); 
    } 
    } 

    private void fetchNext() { 
    Node next = null; 
    while (!stack.isEmpty() && next == null) { 
     Node node = stack.pop(); 
     if (node.left == null && node.right == null) { 
     next = node; 
     } 
     if (node.right != null) { 
     stack.push(node.right); 
     } 
     if (node.left != null) { 
     stack.push(node.left); 
     } 
    } 
    return next; 
    } 

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

    public Node next() { 
    if (!hasNext()) { 
     throw new NoSuchElementException(); 
    } 
    Node n = nextNode; 
    nextNode = fetchNext(); 
    return n; 
    } 

    public void remove() { 
    throw new UnsupportedOperationException(); 
    } 
}