Tìm kiếm nhị phân đệ quy Cây x = thay đổi (x)

Question

Đây là hình ảnh về mã của tôi cần làm.

Before Call: 
      +----+ 
      | -9 | 
      +----+ 
     / \ 
     /  \ 
     +----+  +----+ 
     | 3 |  | 15 | 
     +----+  +----+ 
    /  / \ 
    /  /  \ 
+----+  +----+  +----+ 
| 0 |  | 12 |  | 24 | 
+----+  +----+  +----+ 
     / \ 
     /  \ 
     +----+  +----+ 
     | 6 |  | -3 | 
     +----+  +----+ 

After Call: 
      +----+ 
      | -9 | 
      +----+ 
     / \ 
     /  \ 
     +----+  +----+ 
     | 6 |  | 30 | 
     +----+  +----+ 
    /  / \ 
    /  /  \ 
+----+  +----+  +----+ 
| 0 |  | 24 |  | 48 | 
+----+  +----+  +----+ 
     / \ 
     /  \ 
     +----+  +----+ 
     | 12 |  | -3 | 
     +----+  +----+ 

Về cơ bản, vấn đề này yêu cầu tôi tăng gấp đôi tất cả giá trị dữ liệu lớn hơn 0 trong cây nhị phân của số nguyên. Mã của tôi dưới đây thực hiện điều này cho một vài giá trị nhưng dừng sớm. Tôi không chắc cách sửa lỗi này một cách đệ quy. Đây là những gì đầu ra của tôi trông giống như cho cây được đưa ra ở trên.

 overallRoot 
     _[-9]_______________ 
     /     \ 
    _[6]     _____[30] 
/    /  \ 
[0]    _[12]   [24] 
       / \ 
       [6]  [-3] 
public void doublePositives() { 
    doublePositives(overallRoot); 
} 

private IntTreeNode doublePositives(IntTreeNode root) { 
    if(root != null) { 
     if(root.data > 0) { 
      root.data = 2* root.data; 
     }else { 
      root.left = doublePositives(root.left); 
      root.right= doublePositives(root.right); 
     } 
    } 
    return root; 
} 

Answer 1

Bạn vẫn cần duyệt qua cây nếu bạn đang nhân đôi nút. Thả else để bạn luôn lướt qua. Ngoài ra, tôi đã gỡ bỏ các bài tập vì bạn không thay đổi cơ cấu cây:

if(root != null) { 
    if(root.data > 0) { 
     root.data = 2 * root.data; 
    } 
    doublePositives(root.left); 
    doublePositives(root.right); 
} 

Answer 2

Bạn không thực hiện cuộc gọi đệ quy khi gốc là dương.

Bạn chỉ thực hiện các cuộc gọi đệ quy khi gốc bị âm. Để khắc phục điều này, chỉ cần xóa người khác.

private IntTreeNode doublePositives(IntTreeNode root) { 
    if(root != null) { 
     if(root.data > 0) { 
      root.data = 2* root.data; 
     } 
     root.left = doublePositives(root.left); 
     root.right= doublePositives(root.right); 
    } 
    return root; 
} 

Answer 3

Trông giống như một vấn đề logic - bạn sẽ giá trị chỉ tăng gấp đôi trẻ em của các nút tiêu cực:

if(root.data > 0) { 
     root.data = 2* root.data; 
    }else { 
     root.left = doublePositives(root.left); 
     root.right= doublePositives(root.right); 
    } 

Nếu giá trị gốc là tích cực - bạn không bao giờ truy cập root.left & root.right. Một cái gì đó như thế này sẽ tốt hơn:

if(root.data > 0) { 
     root.data = 2* root.data; 
    } 
    root.left = doublePositives(root.left); 
    root.right= doublePositives(root.right); 

Answer 4

Hãy thử điều này: Bạn đã làm sai lầm trong bản Tuyên Bố có điều kiện. Điều này nên được viết như thế này. Nếu root có dữ liệu là dương - làm cho nó tăng gấp đôi, roger đó! và ra ngoài! Trong bước tiếp theo, tiến hành các nút con trái và phải.

Ngoài ra lưu ý điều này, bạn không cần phải trả lại bất kỳ điều gì (không phải là void) trong hàm đệ quy doublePositives().

public void iWillDoit() { 
     doublePositives(Root); 
    } 

    private void doublePositives(IntTreeNode root) { 
     if(root != null) { 
      if(root.data > 0) 
      { 
       root.data = 2* root.data; 
      } 
      doublePositives(root.left); 
      doublePositives(root.right);  
     } 
    }