Cần trợ giúp để trở về từ phương thức đệ quy

Question

Tôi đang cố gắng theo dõi đường dẫn của một nút trong cây nhị phân (không phải cây tìm kiếm nhị phân). Cho một nút, tôi đang cố gắng in các giá trị của đường dẫn từ gốc.

Tôi đã viết chương trình sau đây.

package dsa.tree; 

import java.util.Stack; 

public class TracePath { 
    private Node n1; 

    public static void main(String args[]){ 
     TracePath nodeFinder = new TracePath(); 
     nodeFinder.find(); 
    } 

    public void find(){ 
     Tree t = getSampleTree(); 
     tracePath(t,n1); 
    } 

    private Tree getSampleTree() { 
     Tree bsTree = new BinarySearchTree(); 
     int randomData[] = {43,887,11,3,8,33,6,0,46,32,78,76,334,45}; 
     for(int i=0;i<randomData.length;i++){ 
      bsTree.add(randomData[i]); 
     } 
     n1 = bsTree.search(76); 
     return bsTree; 
    } 

    public void tracePath(Tree t, Node node){ 
     trace(t,node); 
    } 

    Stack<Node> mainStack = new Stack<Node>(); 

    public void trace(Tree t, Node node){ 
     trace(t.getRoot(),node); 
    } 

    private void trace(Node parent, Node node){ 
     mainStack.push(parent); 
     if(node.data == parent.data){ 
      for(Node iNode:mainStack){ 
       System.out.println(iNode.data); 
      } 
      return; 
     } 
     if(parent.left != null){ 
      trace(parent.left, node); 
     } 
     if(parent.right!=null){ 
      trace(parent.right, node); 
     } 
     mainStack.pop(); 
    } 
} 

Tôi nhận được kết quả đầu ra đúng cách. Nhưng loại lộn xộn của nó. Nếu bạn thấy dấu vết phương thức (Node, Node), tôi đang in các giá trị mà tôi không nên làm. Tôi muốn phương pháp theo dõi hoàn thành chính xác. Ít nhất, tôi nên giết cấu trúc đệ quy ở giai đoạn tôi gặp phải điều kiện nếu.

Vui lòng thông báo.

Answer 1

Được rồi, bạn cần phải hủy bỏ đệ quy khi bạn tìm thấy nút của mình. Đủ đơn giản. Thay đổi phương thức theo dõi của bạn để trả về một boolean cho chúng ta biết nếu nút đã được tìm thấy. Bằng cách đó, chúng ta sẽ quay trở lại ngay lập tức lên cây ngay sau khi tìm thấy nút.

private boolean trace(Node parent, Node node){ 
    mainStack.push(parent); 
    if(node.data == parent.data){ 
     for(Node iNode:mainStack){ 
      System.out.println(iNode.data); 
     } 
     return true; 
    } 
    if(parent.left != null){ 
     if (trace(parent.left, node)) return true; 
    } 
    if(parent.right!=null){ 
     if (trace(parent.right, node)) return true; 
    } 
    mainStack.pop(); 
    return false; 
} 

Answer 2

Tôi giả định đây là bài tập về nhà, vì vậy tôi sẽ cung cấp cho một số con trỏ thay vì một số mã.

• phương pháp dấu vết của bạn một gốc đệ quy, do đó ngăn xếp là không cần thiết - bạn có thể xây dựng các cấu trúc đường dẫn khi trở về từ một nút tìm thấy
• nếu phương pháp của bạn sử dụng một giá trị trả về boolean hoặc List, bạn có thể in con đường khi trở về, hoặc xây dựng một danh sách với các nút để in sau khi các phương pháp tìm kiếm trả về

Sửa: Nếu nút đường dẫn đến thư mục gốc đang bị truy nã, một trở về boolean đơn giản cũng đủ:

0.123.

private boolean trace(Node parent, Node node) { 
    boolean found = (node.data == parent.data) 

    if (!found && parent.left != null) { 
     found = trace(parent.left, node); 
    } 
    if (!found && parent.right != null){ 
     found = trace(parent.right, node); 
    } 

    if (found) { 
     System.out.println(parent.data); 
    } 

    return found; 
} 

Nếu bạn cần các đường đi từ gốc đến nút, bạn có thể vượt qua một danh sách để nhận được các nút theo thứ tự:

private boolean trace(Node parent, Node node, List path) { 
    boolean found = (node.data == parent.data) 

    if (!found && parent.left != null) { 
     found = trace(parent.left, node); 
    } 
    if (!found && parent.right != null){ 
     found = trace(parent.right, node); 
    } 

    if (found) { 
     path.add(0, parent); 
    } 

    return found; 
} 

cách khác bạn có thể xây dựng các con đường trên con đường của bạn trở lại và trở lại như một danh sách.

private List trace(Node parent, Node node) { 
    List path = null; 

    if (null != node) { 
     if (node.data == parent.data) { 

      path = new ArrayList(); 
     } else { 
      path = trace(parent.left, node); 

      if (null == path) { 
       path = trace(parent.right, node); 
      } 
     } 
     if (null != path) { 
      path.add(0, parent); 
     } 
    } 
    return path; 
} 

Answer 3

Trả về dấu hai chấm và quyết định có tiếp tục tìm kiếm dựa trên giá trị được trả về từ cuộc gọi đệ quy hay không.

Answer 4

Một cái gì đó như thế này?

public Stack<Node> findPath(Node src, Node dest, Stack<Node> alreadyCollected) { 
    if (src == dest) 
     return alreadyCollected; 
    if (src.left == null && src.right == null) 
     return null; 
    if (src.left != null) { 
     Stack<Node> toTheLeft = new Stack<Node>(alreadyCollected); 
     toTheLeft.push(src.left); 
     Stack<Node> result = findPath(src.left, dest, toTheLeft); 
     if (result != null) 
      return result; 
    } 
    List<Node> toTheRight = new Stack<Node>(alreadyCollected); 
    return findPath(src.right, dest, toTheRight); 
} 

Answer 5

Đây là chức năng đệ quy mà không cần sử dụng ngăn xếp. Một đệ quy tương đương với stack techincally và bạn không cần phải stack khi thực hiện recusrion.

PS: Tôi đang viết mã giả. Tự viết lại để biên soạn nó :)

bool trace(Node curr, Node n, Path path){ 
    if(curr == null) 
     return; 
    if(n == curr){ 
     path.insertAtEnd(curr); 
     return true; 
    } 

    if(trace(curr.left, n, path)){ 
     path.insertAtEnd(curr); 
     return true; 
    } 
    if(trace(curr.right, n, path)){ 
     path.insertAtEnd(curr); 
     return true; 
    } 
    return false 
}