Jumlah Rentang
Pelajaran 13 dari 16 dalam kursus Pohon AVL, Seri Struktur Data #10 di Coddy.
Karena tree menyimpan setiap nilai secara berurutan, kamu tidak perlu memeriksa setiap node untuk menjumlahkan rentang: setiap kali nilai sebuah node berada di bawah low, seluruh subtree kirinya juga berada di bawah low dan bisa dilewati, dan logika yang sama berlaku untuk subtree kanan ketika nilai sebuah node berada di atas high.
Penelusuran in-order sederhana yang hanya melakukan rekursi ke subtree yang mungkin berisi nilai dalam rentang sudah cukup, meskipun untuk tantangan ini, traversal penuh dengan filter juga bisa digunakan.
Tantangan
MudahTulis fungsi rangeSum(tree, low, high) yang mengembalikan jumlah semua nilai dalam pohon yang berada di antara low dan high, secara inklusif.
Coba sendiri
#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;
}
Semua pelajaran di Pohon AVL, Seri Struktur Data #10
3Tantangan Latihan
Elemen Terkecil ke-KJumlah RentangLeluhur Bersama TerendahPenelusuran Berdasarkan Urutan LevelPenerus Suatu NilaiLatihan sendiri: Compiler C online