Cây nhị phân thành mảng Python

Tôi nghĩ rằng giải pháp bạn có có khả năng tối ưu [hoặc đủ gần] về mặt thời gian chạy và tôi nghĩ cách tiếp cận tính tổng trên lát cắt của bạn tốt hơn nhiều so với thực hiện vòng lặp for

Nhược điểm duy nhất của cách tiếp cận này là hơi khó mò mẫm và do đó khó mở rộng hoặc duy trì, bởi vì cách tiếp cận bạn đang thực hiện quá cụ thể đối với việc triển khai cây và nhiệm vụ cụ thể mà bạn đang thực hiện. Nói cách khác, mã này có thể sẽ không được sử dụng lại cho một tác vụ khác liên quan đến việc duyệt qua cùng một cây hoặc để áp dụng cùng một tác vụ cho một biểu diễn cây khác

Nếu hiệu quả là điều tối quan trọng, thì sẽ có chỗ dành cho mã được tối ưu hóa chặt chẽ, nhưng trong trường hợp đó, tôi khuyên bạn nên có một số nhận xét giải thích để tăng tốc độ hiểu của người đọc. Một cái gì đó với một sơ đồ bố trí cây, nói

# Our tree:
#                      arr[0]                       Optional[Node]:
        return make_node[node * 2 + 1]

    def right_child[node: Node] -> Optional[Node]:
        return make_node[node * 2 + 2]

    def root_node[] -> Optional[Node]:
        return make_node[0]

    def value[node: Node] -> int:
        return arr[node]

    # Recursive function to sum the subtree under a node.
    def sum_subtree[node: Optional[Node]] -> int:
        if node is None:
            return 0
        return [
            value[node] 
            + sum_subtree[left_child[node]] 
            + sum_subtree[right_child[node]]
        ]

    # Get sums of left and right subtrees.
    root = root_node[]
    if root is None:
        return ''
    left_sum = sum_subtree[left_child[root]]
    right_sum = sum_subtree[right_child[root]]

    if right_sum > left_sum:
        return 'Right'
    elif left_sum > right_sum:
        return 'Left'
    else:
        return ''

Cách tiếp cận này chia logic thành các lớp. Lớp nền tảng là năm chức năng xác định sự trừu tượng của Node, cho chúng ta cách đọc cây hoàn toàn tách rời khỏi mảng. Các chi tiết về cách cây được lưu trữ trong mảng [e. g. logic 2 * index + 1 kỳ diệu] được chứa hoàn toàn bên trong các chức năng này. Bạn cũng có thể triển khai tập hợp các hàm này dưới dạng một lớp [lưu trữ tham chiếu đến mảng dưới dạng thuộc tính thể hiện], điều này sẽ giúp dễ dàng sử dụng bên ngoài hàm này và tự kiểm tra đơn vị;

Sự trừu tượng hóa cây này cho phép chúng tôi xây dựng một trình trợ giúp sum_subtree tổng hợp đệ quy mọi thứ dưới một nút. Ngay cả khi người đọc không hiểu cách cây được sắp xếp thành một mảng [hoặc không quan tâm], họ có thể đọc hàm này và hiểu cách nó điều hướng cây để tính tổng và nếu họ muốn viết một hàm tương tự

Cuối cùng, chúng ta có logic cấp cao nhất lấy hai cây con cấp cao nhất, so sánh tổng của chúng và trả về kết quả ở định dạng dự kiến

Giải pháp này kém hiệu quả hơn giải pháp của bạn một chút [cuộc gọi đệ quy sẽ sử dụng không gian nhật ký [N] và thực tế là chúng tôi đang lặp lại từng nút một sẽ thêm một vài chu kỳ đồng hồ nữa], nhưng trong nhiều thực tế . . ]

Làm cách nào để chuyển đổi Cây tìm kiếm nhị phân thành mảng?

Một cây có thể được lưu trữ trong một mảng?

Một cây nhị phân không hoàn chỉnh có thể được biểu diễn trong một mảng không?

Có thể triển khai cây nhị phân bằng cách sử dụng mảng không?