Traversing một cây nhị phân đệ quy

Question

Tôi vô vọng bị mất khi nói đến chức năng đệ quy. Tôi bắt buộc phải tạo một hàm đệ quy để đi qua một cây nhị phân và chèn một nút mới vào giữa các giá trị cụ thể. Tôi có cần phải recopy chức năng đi qua của tôi và sửa đổi nó trong mọi chức năng khác mà tôi sử dụng nó trong? Có ai đó vui lòng đánh giá chức năng đi qua không?

Tôi nghĩ mã duyệt ngang của mình là không sao.

Node traverse (Node currentNode){ 
    if (!currentNode.left.equals(null)){ 
     traverse (currentNode.left); 
     return currentNode.left; 
    } 
    if (!currentNode.right.equals(null)){ 
     traverse (currentNode.right); 
     return currentNode.right; 
    } 
    return currentNode; 
} 

Answer 1

Khi nói đến cây nhị phân, có một số loại traversals khác nhau có thể được thực hiện đệ quy. Chúng được viết theo thứ tự chúng được tham chiếu sau đó được truy cập (L = Left child, V = truy cập nút đó, R = right child).

• In-trật tự traversal (LVR)
• Xếp theo thứ tự traversal (RVL)
• Preorder traversal (VLR)
• Postorder traversal (LRV)

Mã của bạn dường như được thực hiện phương thức truyền tải postorder, nhưng bạn đang nhận được một vài điều hỗn hợp. Đầu tiên, nút là những gì bạn muốn đi qua; dữ liệu là những gì bạn muốn truy cập. Thứ hai, bạn không có lý do gì để trả lại chính nút đó, theo cách thực hiện điều này. Mã của bạn không cho phép một điều kiện để nói, 'Tôi đang tìm kiếm này dữ liệu cụ thể, bạn có nó ông Node @ 0xdeadbeef?', Mà sẽ được tìm thấy với một số loại tham số tìm kiếm thêm.

Trình duyệt BST học tập chỉ in chính các nút. Nếu bạn muốn thêm chức năng tìm kiếm, nó chỉ thêm một tham số nữa, cũng như kiểm tra bổ sung cho nút bên phải.

Dưới đây là một đoạn:

// Academic 

public void traverse (Node root){ // Each child of a tree is a root of its subtree. 
    if (root.left != null){ 
     traverse (root.left); 
    } 
    System.out.println(root.data); 
    if (root.right != null){ 
     traverse (root.right); 
    } 
} 

// Search with a valid node returned, assuming int 

public Node traverse (Node root, int data){ // What data are you looking for again? 
    if(root.data == data) { 
     return root; 
    } 
    if (root.left != null){ 
     return traverse (root.left, data); 
    } 
    if (root.right != null){ 
     return traverse (root.right, data); 
    } 
    return null; 
} 

Answer 2

Hàm đệ quy trả về giá trị của chính nó với thông số được sửa đổi hoặc điều kiện kết thúc (thoát). ví dụ, thừa:

int factorial(int param) { 
    if (param > 1) { 
     return param * factorial(param -1); 
    } else { 
     return 1; 
    } 
} 

Trong code của bạn, bạn gọi một 'traverse' nhưng sau đó không làm gì với kết quả ... Khi hàm đệ quy của bạn kết thúc, trở lại cuối cùng của bạn sẽ là con trái đầu tiên nếu nó tồn tại, khác con đầu tiên nếu nó tồn tại, khác nút gốc. Vui lòng cung cấp thêm chi tiết về lý do tại sao bạn cần phải đi qua cây (ngoài ra, không chắc chắn ý bạn là gì "sao chép hàm và sửa đổi nó trong mọi chức năng khác", toàn bộ ý tưởng của hàm là mã một lần -call-nhiều)

Answer 3

Nó có vẻ như bạn đang đi qua trong phương pháp đặt hàng trước, nhưng tôi là một chút hoài nghi về những gì chính xác bạn muốn thực hiện mà không thực sự so sánh nút hiện tại của bạn với một số giá trị cơ sở đó xác định u đã đạt ur Nơi Đến. Tôi sẽ đề nghị vẽ ra một cái cây đơn giản và hình dung các bước. Sau đó cố gắng đưa mã đó vào mã.