العنصر الأصغر رقم K
الدرس 12 من 16 في دورة شجرة AVL - سلسلة هياكل البيانات #10 على Coddy.
تستخدم التحديات التالية فئة AVLTree المكتملة التي قمت ببنائها للتو، والمقدمة لك كملف مغلق. يأتي كل تحدٍ بملف solution جديد حيث تكتب دالة تستخدم الشجرة.
إن المرور بالترتيب (in-order traversal) لأي شجرة بحث ثنائية (عمليات التدوير لا تغير هذا) يزور القيم بـ ترتيب فرز. لذا فإن القيمة الصغرى رقم k هي ببساطة العنصر الموجود في الفهرس k - 1 لهذا المرور.
التحدي
سهلاكتب دالة kthSmallest(tree, k) تُرجع القيمة الصغرى رقم k في الشجرة (بفهرسة تبدأ من 1). يمكنك افتراض أن k صالحة.
جرّب بنفسك
#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 result = kthSmallest(tree, p0);
printf("%d\n", result);
return 0;
}
جميع دروس شجرة AVL - سلسلة هياكل البيانات #10
3تحديات تدريبية
العنصر الأصغر رقم Kمجموع النطاقالسلف المشترك الأدنىالمرور بترتيب المستوياتالقيمة التالية لقيمة ما