जावा या सी ++ में रिकर्सिव चौड़ाई-पहला यात्रा फ़ंक्शन?

Question

यहां चौड़ाई के लिए एक जावा कोड है- पहली यात्रा:

void breadthFirstNonRecursive(){ 
    Queue<Node> queue = new java.util.LinkedList<Node>(); 
    queue.offer(root); 
    while(!queue.isEmpty()){ 
     Node node = queue.poll(); 
     visit(node); 
     if (node.left != null) 
      queue.offer(node.left); 
     if (node.right != null) 
      queue.offer(node.right); 
    } 
} 

क्या ऐसा करने के लिए एक रिकर्सिव फ़ंक्शन लिखना संभव है?

पहले, मैंने सोचा कि यह आसान होगा, इसलिए मैं इसके साथ बाहर आया:

void breadthFirstRecursive(){ 
    Queue<Node> q = new LinkedList<Node>(); 
    breadthFirst(root, q); 
} 

void breadthFirst(Node node, Queue<Node> q){ 
    if (node == null) return; 
    q.offer(node); 
    Node n = q.poll(); 
    visit(n); 
    if (n.left != null) 
     breadthFirst(n.left, q); 
    if (n.right != null) 
     breadthFirst(n.right, q); 
} 

तब मैंने पाया कि यह काम नहीं करता है। यह वास्तव में वही काम करता है:

void preOrder(Node node) { 
    if (node == null) return; 
    visit(node); 
    preOrder(node.left); 
    preOrder(node.right); 
} 

क्या किसी ने इससे पहले इस बारे में सोचा है?

Answer 1

मैं कल्पना नहीं कर सकते क्यों आप करना चाहते हैं, तो आप एक पूरी तरह से अच्छा पुनरावृत्ति समाधान है, लेकिन यहाँ तुम जाओ जब;)

void breadth_first(Node root): 
    Queue q; 
    q.push(root); 
    breadth_first_recursive(q) 

void breadth_first_recursive(Queue q): 
    if q.empty() return; 

    Node n = q.pop() 
    print "Node: ", n 
    if (n.left) q.push(n.left) 
    if (n.right) q.push(n.right) 
    breadth_first_recursive(q) 

मैं जोड़ने चाहिए कि तुम सच में पार करने के लिए चाहते हैं, तो पेड़ के नोड्स रिकर्सिवली, फिर आप level पैरामीटर के साथ एक डीएफएस कर सकते हैं, और आउटपुट नोड्स केवल level पर, फिर रिकर्स कर सकते हैं। लेकिन यह सिर्फ पागल बात है, क्योंकि आप नोड्स को कई बार फिर से देख सकते हैं ... बस स्वीकार करें कि बीएफएस एक पुनरावृत्त एल्गोरिदम है। :)

Answer 2

बीएफएस एल्गोरिदम एक रिकर्सिव एल्गोरिदम नहीं है (डीएफएस के विपरीत)।

एक एल्गोरिदम को अनुकरण करने वाले एक पुनरावर्ती कार्य को लिखने का प्रयास करें, लेकिन यह काफी परेशान होगा। ऐसा करने में क्या बात होगी?

Answer 3

आप iterative deepening depth-first search का उपयोग कर सकते हैं, जो प्रभावी रूप से एक चौड़ाई वाला पहला एल्गोरिदम है जो रिकर्सन का उपयोग करता है। यदि आपके पास उच्च ब्रांचिंग कारक है, तो यह बीएफएस से भी बेहतर है, क्योंकि यह ज्यादा मेमोरी का उपयोग नहीं करता है।

Answer 4

यह हर किसी को संतुष्ट नहीं होने वाला है - मुझे यकीन है। सभी के साथ सभी सम्मान के साथ। उन लोगों को जो पूछते हैं कि बिंदु क्या है? मुद्दा यह है कि हम मानते हैं कि प्रत्येक पुनरावृत्त एल्गोरिदम में भी एक (आसान?) रिकर्सिव समाधान होता है। यहां स्टैक ओवरफ्लो से "साइइसिस" का समाधान है।

BFS(Q) 

{ 

    if (|Q| > 0) 

    v < - Dequeue(Q) 

    Traverse(v) 
    foreach w in children(v) 
     Enqueue(Q, w)  

    BFS(Q) 
} 

यह उस में funninest की निश्चित मात्रा है, लेकिन यह स्पष्ट नहीं है कि यह किसी भी पुनरावर्ती के नियमों का उल्लंघन है। यदि यह किसी भी पुनरावर्ती नियमों का उल्लंघन नहीं करता है, तो इसे स्वीकार किया जाना चाहिए। IMHO।

Answer 5

एक सरल बीएफएस और डीएफएस रिकर्सन: बस स्टैक/कतार में पेड़ के रूट नोड को दबाएं/पेश करें और इन कार्यों को कॉल करें!

public void breadthFirstSearch(Queue queue) { 
if (queue.isEmpty()) 
    return; 

Node node = (Node) queue.poll(); 

System.out.println(node + " "); 

if (node.right != null) 
    queue.offer(node.right); 

if (node.left != null) 
    queue.offer(node.left); 

breadthFirstSearch(queue); 

}

public void depthFirstSearch(Stack stack) { 
if (stack.isEmpty()) 
    return; 

Node node = (Node) stack.pop(); 

System.out.println(node + " "); 

if (node.right != null) 
    stack.push(node.right); 

if (node.left != null) 
    stack.push(node.left); 

depthFirstSearch(stack); 

}