Lặp đi lặp lại qua cây để tìm kích thước

Question

Tôi cần phải tìm số phần tử trong cây bằng thuật toán lặp, nhưng tôi đang tìm mã rất khó viết.

Cách tiếp cận của tôi là bắt đầu tại nút gốc và truy cập các nút con, sau đó là con của các nút con này, v.v.

Đây là mã tôi đã viết mà làm việc cho một cây nhỏ, nhưng không phải là một giải pháp thực tế bởi vì tôi cần phải thêm khối bổ sung đối với từng mức độ sâu:

// Start the counter at 1 because the root node counts 
int size = 1; 

for(ITree child1 : root) { 
    size++; 
    for(ITree child2 : child1) { 
     size++; 
     for(ITree child3 : child2) { 
      size++; 
      for(ITree child4 : child3) { 
       size++; 
       for(ITree child5 : child4) { 
        size++; 
       } 
      } 
     } 
    } 
} 
return size; 

Answer 1

Về mặt lý thuyết , giữ một ngăn xếp (LinkedList, vv). Đối với mỗi đứa trẻ (bây giờ, con của bạn vòng), thêm vào ngăn xếp. Tiếp tục lặp qua ngăn xếp cho đến khi nó cuối cùng trống.

Điều này không được kiểm tra, nhưng điều này sẽ làm chính xác những gì bạn đang tìm kiếm. Tôi chỉ sử dụng java.io.File thay vì "ITree" của bạn, vì nó là một cái gì đó tôi có thể biên dịch chống lại:

int sizeOfTree(File root){ 
    // Start the counter at 1 because the root node counts 

    int size = 1; 

    LinkedList<File> stack = new LinkedList<File>(); 
    stack.add(root); 

    while(!stack.isEmpty()){ 
     File f = stack.remove(); 
     for(File child : f.listFiles()){ 
      size++; 
      stack.add(child); 
     } 
    } 

    return size; 
} 

Answer 2

Sử dụng một cấu trúc dữ liệu đệ quy

Nó không phải là thực tế có thể lặp đi lặp lại đi qua một dữ liệu đệ quy cấu trúc, giống như một cây có con trỏ - điều này là do thực tế là các đối tượng "ẩn" các phần tử dữ liệu cơ bản của chúng.

Sử dụng một cấu trúc dữ liệu khác nhau

Tất cả các cây có thể được lưu trữ/thực hiện như để tuyến tính, mảng cấu trúc dữ liệu, nơi mà chỉ số có thể được tính bằng toán học hàm mũ:

Ví dụ, một cây [0 , 1, 2, 3, null, 4, null] sẽ mô tả một cây có 0 ở gốc, trong đó 0 có con trực tiếp 1 và 2. Và sau đó 1 đã để lại con "3", và 2 đã để lại con "4" .

Vì vậy, nếu bạn lưu trữ cây theo cách này, số lượng phần tử, một cách tự nhiên, số lượng phần tử không null trong mảng.

Đặt đơn giản hơn: Lưu trữ cây theo cấu trúc tuyến tính và bạn có thể biết độ dài tại bất kỳ thời điểm nào mà không phải thực hiện bất kỳ loại thuật toán ưa thích nào.

Answer 3

Từ khóa cho nhiệm vụ của bạn là đệ quy. Cây là một cấu trúc đệ quy cổ điển, vì vậy bạn nên viết phương thức đệ quy chấp nhận các nút gốc, đếm kích thước của nút này và sau đó gọi chính nó cho tất cả trẻ em. Đây là mã giả:

public int getSize(ITree root) { 
    return getSize(root, 0); 
} 

private int getSize(ITree node, int size) { 
    size++; 
    for(ITree child : node.children()) { 
     size += getSize(child, size) 
    } 
    return size; 
}