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