يتم استخدام وظيفة الحذف لحذف العقدة المحددة من شجرة البحث الثنائية. ومع ذلك، يجب علينا حذف عقدة من شجرة البحث الثنائية بطريقة لا تنتهك خاصية شجرة البحث الثنائية. هناك ثلاث حالات لحذف عقدة من شجرة البحث الثنائية.
العقدة المراد حذفها هي عقدة طرفية
إنها أبسط حالة، في هذه الحالة، استبدل العقدة الطرفية بـ NULL وقم ببساطة بتحرير المساحة المخصصة.
في الصورة التالية، نقوم بحذف العقدة 85، نظرًا لأن العقدة عبارة عن عقدة طرفية، وبالتالي سيتم استبدال العقدة بـ NULL وسيتم تحرير المساحة المخصصة.
أوامر لينكس التي
العقدة المراد حذفها لها طفل واحد فقط.
في هذه الحالة، استبدل العقدة بالعقدة التابعة لها واحذف العقدة الفرعية، التي تحتوي الآن على القيمة التي سيتم حذفها. ما عليك سوى استبداله بالقيمة NULL وتحرير المساحة المخصصة.
طريقة توسترينغ
في الصورة التالية، سيتم حذف العقدة 12. لديها طفل واحد فقط. سيتم استبدال العقدة بالعقدة الفرعية الخاصة بها وسيتم ببساطة حذف العقدة المستبدلة 12 (والتي أصبحت الآن العقدة الطرفية).
العقدة المراد حذفها لها طفلان.
إنها حالة معقدة بعض الشيء مقارنة بالحالتين الأخريين. ومع ذلك، يتم استبدال العقدة التي سيتم حذفها بالترتيب التالي أو السابق بشكل متكرر حتى يتم وضع قيمة العقدة (المراد حذفها) على ورقة الشجرة. بعد هذا الإجراء، استبدل العقدة بـ NULL وقم بتحرير المساحة المخصصة.
في الصورة التالية، سيتم حذف العقدة 50 وهي العقدة الجذرية للشجرة. اجتياز الشجرة بالترتيب الموضح أدناه.
كيفية فتح التطبيقات المخفية على الاندرويد
6، 25، 30، 50، 52، 60، 70، 75.
استبدل 50 بالرقم 52 الذي يليه بالترتيب. الآن، سيتم نقل 50 إلى ورقة الشجرة، والتي سيتم حذفها ببساطة.
خوارزمية
حذف (شجرة، عنصر)
اكتب 'العنصر غير موجود في الشجرة' إذا كانت بيانات العنصر
حذف (شجرة->يسار، عنصر)
آخر إذا كان العنصر> الشجرة -> البيانات
حذف (شجرة -> يمين، عنصر)
آخر إذا كانت الشجرة -> اليسار والشجرة -> اليمين
SET TEMP = findLargestNode(TREE -> LEFT)
شجرة التعيين -> البيانات = درجة الحرارة -> البيانات
حذف (شجرة -> يسار، درجة الحرارة -> بيانات)
آخر
ضبط درجة الحرارة = شجرة
إذا كانت الشجرة -> اليسار = فارغة والشجرة -> اليمين = فارغة
شجرة المجموعة = فارغة
آخر إذا كانت شجرة -> يسار! = NULL
تعيين الشجرة = الشجرة -> اليسار
آخر
تعيين الشجرة = شجرة -> يمين
[نهاية إذا]
درجة حرارة مجانية
[نهاية إذا]
وظيفة:
void deletion(Node*& root, int item) { Node* parent = NULL; Node* cur = root; search(cur, item, parent); if (cur == NULL) return; if (cur->left == NULL && cur->right == NULL) { if (cur != root) { if (parent->left == cur) parent->left = NULL; else parent->right = NULL; } else root = NULL; free(cur); } else if (cur->left && cur->right) { Node* succ = findMinimum(cur- >right); int val = succ->data; deletion(root, succ->data); cur->data = val; } else { Node* child = (cur->left)? Cur- >left: cur->right; if (cur != root) { if (cur == parent->left) parent->left = child; else parent->right = child; } else root = child; free(cur); } } Node* findMinimum(Node* cur) { while(cur->left != NULL) { cur = cur->left; } return cur; }