Menu
CoddyTech

Tổng trong phạm vi

Bài học 13 trên 16 trong khóa học Cây AVL, chuỗi cấu trúc dữ liệu #10 của Coddy.

Vì cây giữ mọi giá trị theo thứ tự, bạn không cần kiểm tra từng nút để tính tổng một khoảng: khi giá trị của một nút nhỏ hơn low, toàn bộ cây con bên trái của nó cũng nhỏ hơn low và có thể bỏ qua; logic tương tự áp dụng cho cây con bên phải khi giá trị của một nút lớn hơn high.

Chỉ cần duyệt cây theo thứ tự giữa một cách đơn giản, chỉ đệ quy vào những cây con có thể chứa các giá trị trong khoảng, dù với thử thách này, duyệt toàn bộ rồi lọc cũng được.

challenge icon

Thử thách

Dễ

Viết một hàm rangeSum(tree, low, high) trả về tổng của mọi giá trị trong cây nằm trong khoảng từ low đến high, bao gồm cả hai giá trị.

Tự làm thử

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "avltree.h"
#include "solution.h"

int main(void) {
    AVLTree* tree = AVLTree_create();
    char line1[4096];
    fgets(line1, sizeof(line1), stdin);
    char* tok = strtok(line1, " \n");
    while (tok != NULL) {
        AVLTree_insert(tree, atoi(tok));
        tok = strtok(NULL, " \n");
    }
    char line2[256];
    fgets(line2, sizeof(line2), stdin);
    int p0 = atoi(strtok(line2, " \n"));
    int p1 = atoi(strtok(NULL, " \n"));
    int result = rangeSum(tree, p0, p1);
    printf("%d\n", result);
    return 0;
}

Tất cả bài học trong Cây AVL, chuỗi cấu trúc dữ liệu #10

Tự luyện tập: Trình biên dịch C online