Binary Search Tree

الBinary Search Tree او الBST هو بناء على شكل شجرة يتكون من جذر رئيسي (root) وجذور فرعية (subRoots) واوراق (leaves) ,, تتم الإضافة إليه إعتماداً على قيمة العنصر الممثل لجذر الشجرة ثم اعتماداً على قيم العناصر الممثلة للجذور الفرعية ,, فالعناصر ذات القيم الأكبر من قيمة العنصر الممثل للجذر تكون على يمين الجذر ,, اما العناصر ذات القيم الأقل من قيمة العنصر الممثل للجذر تكون على يسار الجذر ,, وهكذا الأمر بالنسبة للجذور الفرعية.

يحتاج هذا البناء الى مؤشر واحد بحيث يشير الى العنصر الذي يمثل جذر الشجرة وعادةً يسمى root ,,, ويحتاج ايضاً الى متغير يُعبر عن عدد العناصر المخزنة في الشجرة ويسمى count.

تتميز العناصر في الBST بأن لكل عنصر مؤشرين هما الleft والright ,, ويمتلك كل عنصر ايضاً متغير يعبر عن القيمة المخزنة في العنصر وعادةً يُسمى الdata.

لتحديد ما اذا كان العنصر يمثل ورقة او يمثل جذراً فرعياً ,, اذا كان احد مؤشري العنصر لا يشير الى الNULL أو كليهما, إذاً هذا العنصر لا يُمثل ورقة ,, اما اذا كان كلا المؤشرين يشيران الى الNULL, اذاً هذا العنصر يُمثل ورقة.

SubRoot

Leaf

هناك ثلاثة حالات للحذف من الشجرة وهي ...

أولاً - حذف الورقة ,, بحيث يتم حذفها دون التأثير على بقية العناصر في الشجرة.

ثانياً - حذف جذر متصل بورقة واحدة ,, بحيث يتم استبدال قيمة الجذر بقيمة الورقة ثم حذف الورقة.

ثالثاً - حذف جذر متصل بورقتين أو حذف جذر متصل بجذرين فرعيين ,, وهنا اما ان يتم استبدال قيمة الجذر بقيمة العنصر الذي يسبقه مباشرة بترتيب الIn-Order وحذف العنصر الذي تم التبادل معه ,, او ان يتم استبدال قيمة الجذر بقيمة العنصر الذي يليه مباشرة بترتيب الIn-Order وحذف العنصر الذي تم التبادل معه.

هناك ثلاثة طرق لزيارة العناصر في الشجرة وهي ...
In-Order (In-Fix) Traversal ,, Pre-Order (Pre-Fix) Traversal ,, Post-Order (Post-Fix) Traversal ...

بحيث تتم زيارة العناصر في كل من الطرق الثلاث كالتالي ...

In-Order (In-Fix) Traversal ... left ,, root ,, right

Pre-Order (Pre-Fix) Traversal ... root ,, left ,, right

Post-Order (Post-Fix) Traversal ... left ,, right ,, root

لشرح كيفية طباعة العناصر بطرق الزيارة الثلاث وكيفية الإضافة والحذف .. تأمل المثال التالي ,, وهو عبارة عن برنامج يقوم بإنشاء BST بإسم test ومن ثم يضيف إليها 7 عناصر بالقيم 5, 3, 7, 2, 9, 4, 6 ,, وثم يقوم بطباعة عدد العناصر وقيمها بطرق الزيارة الثلاث ,, ويحذف العناصر ذات القيم 2, 7, 5 ,, ثم يطبع عدد العناصر المتبقية وقيمها مرة أخرى بإستخدام الطرق الثلاث.

ناتج البرنامج اعلاه هو ..

للحصول على نسخة نصية من البرنامج اعلاه .. تحميل

سيتم تتبع التعليمات المكتوبة في الmain وذلك لأن أي تعليمات مكتوبة خارج الmain عبارة عن تعليمات لا فائدة منها لطالما لم يتم إستدعاؤها من داخل الmain.

**************************************************

تعمل هذه التعليمة على الإعلان عن object جديد من الBST بإسم test وتعوض int مكان كل T موجودة في الtest ... تقوم هذه التعليمة ايضاً باستدعاء الconstructor الإفتراضي والذي يقوم بدوره بتخزين القيمة صفر في المتغير count وجعل المؤشر root يشير الى NULL ... الconstructor الإفتراضي ..

*تذكر انه عند الإعلان عن object من class يستخدم الtemplate فإنه لا داعي لكتابة الأقواس الفارغة في تعليمة الإعلان عندما يكون المطلوب استدعاء الconstructor الإفتراضي ... الصيغة العامة للإعلان عن object من class يستخدم الtemplate ..

**************************************************

تعمل هذه التعليمة على استدعاء الإقتران insertItem الموجود في test وتمرير القيمة 5 اليه ... الإقتران insertItem ..

ليقوم الإقتران insertItem بدوره بإستدعاء اقتران اخر وهو insert كما تظهر الصورة اعلاه وتمرير مؤشر الroot والقيمة 5 اليه ... الإقتران insert ..

بما ان شرط جملة الif صحيح وهو ان جذر الشجرة يشير الى NULL (الشجرة خالية) ,, يعمل الإقتران insert على انشاء عنصر جديد في المكان الذي يؤشر اليه الroot (تم استبدال الإسم root باسم Tree داخل الإقتران) ,, ويجعل مؤشري الleft والright الخاصين بالعنصر الجديد يشيران الى NULL ,, ثم يخزن القيمة 5 في العنصر الجديد ... هذا هو الجزء المنفذ من التعليمات الموجودة في الإقتران insert ..

**************************************************

تعمل هذه التعليمة على استدعاء الإقتران insertItem الموجود في test وتمرير القيمة 3 اليه ... الإقتران insertItem ..

ليقوم الإقتران insertItem بدوره بإستدعاء اقتران اخر وهو insert كما تظهر الصورة اعلاه وتمرير مؤشر الroot والقيمة 5 اليه ... الإقتران insert ..

يحاول الإقتران insert تنفيذ تعليمات جملة الif ولكن شرط الif غير صحيح اذ ان جذر الشجرة لا يشير الى NULL ,, لذلك ينتقل الى else if بحيث يكون الشرط صحيح ,, اذ ان قيمة العنصر المراد اضافته اقل من قيمة العنصر الموجود في الجذر (3 اقل من 5) ... الجزء المنفذ من التعليمات الموجودة في الإقتران insert ..

تعمل التعليمة الموجودة داخل جملة الelse if على اعادة استدعاء الإقتران insert بحيث تمرر اليه ما يشير اليه الleft الخاص بالجذر (أي NULL) ,, كما تمرر اليه قيمة العنصر المراد انشاؤه وهي ال3 ... الإقتران insert ..

بما ان شرط جملة الif صحيح وهو ان ما يشير اليه الTree هو NULL (الleft الخاص بالجذر يشير الى NULL) ,, يعمل الإقتران insert على انشاء عنصر جديد في المكان الذي يؤشر اليه الleft الخاص بالجذر (تم تسمية الleft الخاص بالجذر باسم Tree داخل الإقتران) ,, ويجعل مؤشري الleft والright الخاصين بالعنصر الجديد يشيران الى NULL ,, ثم يخزن القيمة 3 في العنصر الجديد ... هذا هو الجزء المنفذ من التعليمات الموجودة في الإقتران insert ..

**************************************************

تعمل هذه التعليمة على استدعاء الإقتران insertItem الموجود في test وتمرير القيمة 7 اليه ... الإقتران insertItem ..

ليقوم الإقتران insertItem بدوره بإستدعاء اقتران اخر وهو insert كما تظهر الصورة اعلاه وتمرير مؤشر الroot والقيمة 7 اليه ... الإقتران insert ..

يحاول الإقتران insert تنفيذ تعليمات جملة الif ولكن شرط الif غير صحيح اذ ان جذر الشجرة لا يشير الى NULL ,, لذلك ينتقل الى else if وأيضاً لا يكون الشرط صحيح ,, اذ أن قيمة العنصر المراد اضافته ليست اقل من قيمة العنصر الموجود في الجذر (7 اكبر من 5) ,, لذلك ينتقل الى جملة الelse حيث لا يوجد شرط ... الجزء المنفذ من التعليمات الموجودة في الإقتران insert ..

تعمل التعليمة الموجودة داخل جملة الelse على اعادة استدعاء الإقتران insert بحيث تمرر اليه ما يشير اليه الright الخاص بالجذر (أي NULL) ,, كما تمرر اليه قيمة العنصر المراد انشاؤه وهي ال7 ... الإقتران insert ..

بما ان شرط جملة الif صحيح وهو ان ما يشير اليه الTree هو NULL (الright الخاص بالجذر يشير الى NULL) ,, يعمل الإقتران insert على انشاء عنصر جديد في المكان الذي يؤشر اليه الright الخاص بالجذر (تم تسمية الright الخاص بالجذر باسم Tree داخل الإقتران) ,, ويجعل مؤشري الleft والright الخاصين بالعنصر الجديد يشيران الى NULL ,, ثم يخزن القيمة 7 في العنصر الجديد ... هذا هو الجزء المنفذ من التعليمات الموجودة في الإقتران insert ..

**************************************************

تعمل هذه التعليمة على استدعاء الإقتران insertItem الموجود في test وتمرير القيمة 2 اليه ... الإقتران insertItem ..

ليقوم الإقتران insertItem بدوره بإستدعاء اقتران اخر وهو insert كما تظهر الصورة اعلاه وتمرير مؤشر الroot والقيمة 2 اليه ... الإقتران insert ..

يحاول الإقتران insert تنفيذ تعليمات جملة الif ولكن شرط الif غير صحيح اذ ان جذر الشجرة لا يشير الى NULL ,, لذلك ينتقل الى else if بحيث يكون الشرط صحيح ,, اذ ان قيمة العنصر المراد اضافته اقل من قيمة العنصر الموجود في الجذر (2 اقل من 5) ... الجزء المنفذ من التعليمات الموجودة في الإقتران insert ..

تعمل التعليمة الموجودة داخل جملة الelse if على اعادة استدعاء الإقتران insert بحيث تمرر اليه ما يشير اليه الleft الخاص بالجذر (أي العنصر ذو القيمة 3) ,, كما تمرر اليه قيمة العنصر المراد انشاؤه وهي ال2 ... الإقتران insert ..

يحاول الإقتران insert تنفيذ تعليمات جملة الif ولكن شرط الif غير صحيح اذ ان Tree يشير الى العنصر ذو القيمة 3 ولا يشير الى NULL ,, لذلك ينتقل الى else if بحيث يكون الشرط صحيح ,, اذ ان قيمة العنصر المراد اضافته اقل من قيمة العنصر الذي يشير اليه الTree اي انه (2 اقل من 3) ... الجزء المنفذ من التعليمات الموجودة في الإقتران insert ..

تعمل التعليمة الموجودة داخل جملة الelse if على اعادة استدعاء الإقتران insert بحيث تمرر اليه ما يشير اليه الleft الخاص بالعنصر الذي يشير اليه الTree (أي NULL لأن الleft الخاص بالعنصر ذو القيمة 3 يشير الى NULL) ,, كما تمرر اليه قيمة العنصر المراد انشاؤه وهي ال2 ... الإقتران insert ..

بما ان شرط جملة الif صحيح وهو ان ما يشير اليه الTree هو NULL (الleft الخاص بالعنصر ذو القيمة 3 يشير الى NULL) ,, يعمل الإقتران insert على انشاء عنصر جديد في المكان الذي يؤشر اليه الleft الخاص بالعنصر ذو القيمة 3 (تم تسمية الleft الخاص بالعنصر ذو القيمة 3 باسم Tree داخل الإقتران) ,, ويجعل مؤشري الleft والright الخاصين بالعنصر الجديد يشيران الى NULL ,, ثم يخزن القيمة 2 في العنصر الجديد ... هذا هو الجزء المنفذ من التعليمات الموجودة في الإقتران insert ..

**************************************************

تعمل هذه التعليمة على استدعاء الإقتران insertItem الموجود في test وتمرير القيمة 9 اليه ... الإقتران insertItem ..

ليقوم الإقتران insertItem بدوره بإستدعاء اقتران اخر وهو insert كما تظهر الصورة اعلاه وتمرير مؤشر الroot والقيمة 9 اليه ... الإقتران insert ..

يحاول الإقتران insert تنفيذ تعليمات جملة الif ولكن شرط الif غير صحيح اذ ان جذر الشجرة لا يشير الى NULL ,, لذلك ينتقل الى else if وأيضاً لا يكون الشرط صحيح ,, اذ أن قيمة العنصر المراد اضافته ليست اقل من قيمة العنصر الموجود في الجذر (9 اكبر من 5) ,, لذلك ينتقل الى جملة الelse حيث لا يوجد شرط ... الجزء المنفذ من التعليمات الموجودة في الإقتران insert ..

تعمل التعليمة الموجودة داخل جملة الelse على اعادة استدعاء الإقتران insert بحيث تمرر اليه ما يشير اليه الright الخاص بالجذر (أي العنصر ذو القيمة 7) ,, كما تمرر اليه قيمة العنصر المراد انشاؤه وهي ال9 ... الإقتران insert ..

يحاول الإقتران insert تنفيذ تعليمات جملة الif ولكن شرط الif غير صحيح اذ ان Tree يشير الى العنصر ذو القيمة 7 أي لا يشير الى NULL ,, لذلك ينتقل الى else if وأيضاً لا يكون الشرط صحيح ,, اذ أن قيمة العنصر المراد اضافته ليست اقل من قيمة العنصر الذي يؤشر اليه الTree أي انه (9 اكبر من 7) ,, لذلك ينتقل الى جملة الelse حيث لا يوجد شرط ... الجزء المنفذ من التعليمات الموجودة في الإقتران insert ..

تعمل التعليمة الموجودة داخل جملة الelse على اعادة استدعاء الإقتران insert بحيث تمرر اليه ما يشير اليه الright الخاص بالعنصر الذي يشير اليه الTree (اي NULL لأن الright الخاص بالعنصر ذو القيمة 7 يشير الى NULL) ,, كما تمرر اليه قيمة العنصر المراد انشاؤه وهي ال9 ... الإقتران insert ..

بما ان شرط جملة الif صحيح وهو ان ما يشير اليه الTree هو NULL (الright الخاص بالعنصر ذو القيمة 7 يشير الى NULL) ,, يعمل الإقتران insert على انشاء عنصر جديد في المكان الذي يؤشر اليه الright الخاص بالعنصر ذو القيمة 7 (تم تسمية الright الخاص بالعنصر ذو القيمة 7 باسم Tree داخل الإقتران) ,, ويجعل مؤشري الleft والright الخاصين بالعنصر الجديد يشيران الى NULL ,, ثم يخزن القيمة 9 في العنصر الجديد ... هذا هو الجزء المنفذ من التعليمات الموجودة في الإقتران insert ..

**************************************************

تعمل هذه التعليمة على استدعاء الإقتران insertItem الموجود في test وتمرير القيمة 4 اليه ... الإقتران insertItem ..

ليقوم الإقتران insertItem بدوره بإستدعاء اقتران اخر وهو insert كما تظهر الصورة اعلاه وتمرير مؤشر الroot والقيمة 4 اليه ... الإقتران insert ..

يحاول الإقتران insert تنفيذ تعليمات جملة الif ولكن شرط الif غير صحيح اذ ان جذر الشجرة لا يشير الى NULL ,, لذلك ينتقل الى else if بحيث يكون الشرط صحيح ,, اذ ان قيمة العنصر المراد اضافته اقل من قيمة العنصر الموجود في الجذر (4 اقل من 5) ... الجزء المنفذ من التعليمات الموجودة في الإقتران insert ..

تعمل التعليمة الموجودة داخل جملة الelse if على اعادة استدعاء الإقتران insert بحيث تمرر اليه ما يشير اليه الleft الخاص بالجذر (أي العنصر ذو القيمة 3) ,, كما تمرر اليه قيمة العنصر المراد انشاؤه وهي ال4 ... الإقتران insert ..

يحاول الإقتران insert تنفيذ تعليمات جملة الif ولكن شرط الif غير صحيح اذ ان Tree يشير الى العنصر ذو القيمة 3 أي لا يشير الى NULL ,, لذلك ينتقل الى else if وأيضاً لا يكون الشرط صحيح ,, اذ أن قيمة العنصر المراد اضافته ليست اقل من قيمة العنصر الذي يؤشر اليه الTree أي انه (4 اكبر من 3) ,, لذلك ينتقل الى جملة الelse حيث لا يوجد شرط ... الجزء المنفذ من التعليمات الموجودة في الإقتران insert ..

تعمل التعليمة الموجودة داخل جملة الelse على اعادة استدعاء الإقتران insert بحيث تمرر اليه ما يشير اليه الright الخاص بالعنصر الذي يشير اليه الTree (اي NULL لأن الright الخاص بالعنصر ذو القيمة 3 يشير الى NULL) ,, كما تمرر اليه قيمة العنصر المراد انشاؤه وهي ال4 ... الإقتران insert ..

بما ان شرط جملة الif صحيح وهو ان ما يشير اليه الTree هو NULL (الright الخاص بالعنصر ذو القيمة 3 يشير الى NULL) ,, يعمل الإقتران insert على انشاء عنصر جديد في المكان الذي يؤشر اليه الright الخاص بالعنصر ذو القيمة 3 (تم تسمية الright الخاص بالعنصر ذو القيمة 3 باسم Tree داخل الإقتران) ,, ويجعل مؤشري الleft والright الخاصين بالعنصر الجديد يشيران الى NULL ,, ثم يخزن القيمة 4 في العنصر الجديد ... هذا هو الجزء المنفذ من التعليمات الموجودة في الإقتران insert ..

**************************************************

تعمل هذه التعليمة على استدعاء الإقتران insertItem الموجود في test وتمرير القيمة 6 اليه ... الإقتران insertItem ..

ليقوم الإقتران insertItem بدوره بإستدعاء اقتران اخر وهو insert كما تظهر الصورة اعلاه وتمرير مؤشر الroot والقيمة 6 اليه ... الإقتران insert ..

يحاول الإقتران insert تنفيذ تعليمات جملة الif ولكن شرط الif غير صحيح اذ ان جذر الشجرة لا يشير الى NULL ,, لذلك ينتقل الى else if وأيضاً لا يكون الشرط صحيح ,, اذ أن قيمة العنصر المراد اضافته ليست اقل من قيمة العنصر الموجود في الجذر (6 اكبر من 5) ,, لذلك ينتقل الى جملة الelse حيث لا يوجد شرط ... الجزء المنفذ من التعليمات الموجودة في الإقتران insert ..

تعمل التعليمة الموجودة داخل جملة الelse على اعادة استدعاء الإقتران insert بحيث تمرر اليه ما يشير اليه الright الخاص بالجذر (أي العنصر ذو القيمة 7) ,, كما تمرر اليه قيمة العنصر المراد انشاؤه وهي ال6 ... الإقتران insert ..

يحاول الإقتران insert تنفيذ تعليمات جملة الif ولكن شرط الif غير صحيح اذ ان Tree يشير الى العنصر ذو القيمة 7 ولا يشير الى NULL ,, لذلك ينتقل الى else if بحيث يكون الشرط صحيح ,, اذ ان قيمة العنصر المراد اضافته اقل من قيمة العنصر الذي يشير اليه الTree اي انه (6 اقل من 7) ... الجزء المنفذ من التعليمات الموجودة في الإقتران insert ..

تعمل التعليمة الموجودة داخل جملة الelse if على اعادة استدعاء الإقتران insert بحيث تمرر اليه ما يشير اليه الleft الخاص بالعنصر الذي يشير اليه الTree (أي NULL لأن الleft الخاص بالعنصر ذو القيمة 7 يشير الى NULL) ,, كما تمرر اليه قيمة العنصر المراد انشاؤه وهي ال6 ... الإقتران insert ..

بما ان شرط جملة الif صحيح وهو ان ما يشير اليه الTree هو NULL (الleft الخاص بالعنصر ذو القيمة 7 يشير الى NULL) ,, يعمل الإقتران insert على انشاء عنصر جديد في المكان الذي يؤشر اليه الleft الخاص بالعنصر ذو القيمة 7 (تم تسمية الleft الخاص بالعنصر ذو القيمة 7 باسم Tree داخل الإقتران) ,, ويجعل مؤشري الleft والright الخاصين بالعنصر الجديد يشيران الى NULL ,, ثم يخزن القيمة 2 في العنصر الجديد ... هذا هو الجزء المنفذ من التعليمات الموجودة في الإقتران insert ..

**************************************************

تعمل هذه التعليمة على طباعة نص ثم تستدعي الإقتران length الموجود داخل الtest والذي لا يحتاج لتمرير قيم اليه ثم تطبع نص اخر وتطبع سطرين جديدين ... الإقتران length ..

ليقوم الإقتران length بدوره بإستدعاء اقتران اخر وهو recursiveNumberOfNodes كما تظهر الصورة اعلاه وتمرير مؤشر الroot اليه ... الإقتران recursiveNumberOfNodes ..

يقوم بالتحقق من شرط جملة الif بحيث يتأكد ان الجذر لا يشير الى NULL (تم استبدال الإسم root بالإسم Tree ليعبر عن الجذر داخل الإقتران) ,, ولكن الجذر لا يشير الى NULL وبالتالي ينتقل لتنفيذ جملة الesle ... الجزء المنفذ من التعليمات الموجودة في الإقتران recursiveNumberOfNodes ..

تقوم هذه التعليمة بالإستدعاء التكراري للإقتران recursiveNumberOfNodes بحيث ينتهي هذا الإستدعاء التكراري عندما يصبح Tree يشير الى NULL ,, وبعد انتهاء الإستدعاء التكراري كاملاً تقوم الكلمة المحجوزة return بإرجاع الناتج النهائي الى التعليمة التي استدعت الإقتران recursiveNumberOfNodes اساساً وهي التعليمة الموجودة داخل الإقتران length.

لتتبع تنفيذ الإستدعاء التكراري .. سنتتبع تنفيذ الإقتران لل(Tree->left) أما تنفيذ الإقتران لل(Tree->right) فسيكون بنفس الكيفية ...

في ال(Tree->left) بدايةً سيتم اعادة استدعاء الإقتران recurseiveNumberOfNodes بحيث يتم تمرير ما يشير اليه الleft الخاص بالTree (وهو ما يشير اليه الleft الخاص بالجذر ,, اي العنصر ذو القيمة 3) ... الإقتران recursiveNumberOfNodes ..

يقوم بالتحقق من شرط جملة الif بحيث يتأكد ان الTree لا يشير الى NULL ,, ولكن الTree لا يشير الى NULL لأنه يشير الى العنصر ذو القيمة 3 وبالتالي ينتقل لتنفيذ جملة الesle ... الجزء المنفذ من التعليمات الموجودة في الإقتران recursiveNumberOfNodes ..

وهنا ايضاً سيقوم بالإستدعاء التكراري للإقتران لكل من ال(Tree->left) وال(Tree->right) ,, في حالة ال(Tree->left) سيمرر ما يشير اليه الleft الخاص بالعنصر ذو القيمة 3 وهو العنصر ذو القيمة 2 ,, اما في حالة ال(Tree->right) سيمرر ما يشير اليه الright الخاص بالعنصر ذو القيمة 3 وهو العنصر ذو القيمة 4.

وطبعاً في الحالتين سيتحقق من شرط الif وهو ان الTree يشير الى الNULL وسيكون الشرط خاطئ لأن احدهما يشير الى العنصر ذو القيمة 2 والاخر يشير الى العنصر ذو القيمة 4 ... الإقتران recursiveNumberOfNodes ..

في كلتا الحالتين سيتم تنفيذ الجزء التالي ..

بحيث انه سواء في حالة العنصر ذو القيمة 2 أو العنصر ذو القيمة 4 ,, سيمرر NULL الى (Tree->left) والى (Tree->right) وذلك لأن الright والleft الخاصين بكل من العنصر ذو القيمة 2 والعنصر ذو القيمة 4 يشيران الى NULL.

في الخطوة التالية لكل NULL تم تمريرها سيتم اعادة التحقق من شرط جملة الif وفي هذه الحالة فإن الشرط صحيح ... الجزء المنفذ من التعليمات الموجودة في الإقتران recursiveNumberOfNodes ..

يقوم بإعادة صفر للإقتران الخاص ب(Tree->left) وصفر للإقتران الخاص ب(Tree->right) ثم اضافة واحد الى الناتج حسب التعليمة الموجودة في الelse ..

واعادة الناتج كامل من خلال الreturn الى التعليمة التي قامت بإستدعاء الإقترانrecursiveNumberOfNodes وهكذا ... وصولاً الى التعليمة التي استدعت الإقتران recursiveNumberOfNodes من داخل الإقتران length ,, فإن القيمة التي سيتم اعادتها الى التعليمة الموجودة داخل الإقتران length ستكون 7 ... الإقتران length ..

الرسم التالي يوضح تسلسل تنفيذ عمليات استدعاء الrecursiveNumberOfNodes ..

الرسم التالي يوضح تسلسل اعادة الناتج ..

**************************************************

تعمل هذه التعليمة على استدعاء الإقتران inOrderTraversing الموجود داخل الtest والذي لا يحتاج لتمرير قيم اليه ثم تطبع سطر جديد في تعليمة منفصلة ... الإقتران inOrderTraversing ..

ليقوم الإقتران inOrderTraversing بدوره بطباعة نص واستدعاء اقتران اخر وهو recursiveInOrder كما تظهر الصورة اعلاه وتمرير مؤشر الroot اليه ... الإقتران recursiveInOrder ..

يقوم بالتحقق من الشرط داخل جملة الif بحيث يتأكد ان الtreeSubRoot (الذي يشير الى الجذر) لا يشير الى NULL ,, وهو فعلاً لا يشير الى NULL ,, لذلك سيقوم بتنفيذ التعليمات الموجودة داخل جملة الif.

سيقوم بالإستدعاء التكراري لrecursiveInOrder بحيث يضمن الطباعة بترتيب left ثم root ثم right ... استدعاء الإقتران لل(treeSubRoot->left) اولاً ثم الطباعة ثم استدعاء الإقتران لل(treeSubRoot->right) تدل على هذا الترتيب كما تبين التعليمات الظاهرة في الصورة اعلاه ... تستطيع تتبع تسلسل تنفيذ الإقتران التكراري هنا لتتأكد بنفسك من هذا الترتيب.

الرسومات التالية توضح تسلسل طباعة قيم العناصر بطريقة In-Order ..

**************************************************

تعمل هذه التعليمة على استدعاء الإقتران preOrderTraversing الموجود داخل الtest والذي لا يحتاج لتمرير قيم اليه ثم تطبع سطر جديد في تعليمة منفصلة ... الإقتران preOrderTraversing ..

ليقوم الإقتران preOrderTraversing بدوره بطباعة نص واستدعاء اقتران اخر وهو recursivePreOrder كما تظهر الصورة اعلاه وتمرير مؤشر الroot اليه ... الإقتران recursivePreOrder ..

يقوم بالتحقق من الشرط داخل جملة الif بحيث يتأكد ان الtreeSubRoot (الذي يشير الى الجذر) لا يشير الى NULL ,, وهو فعلاً لا يشير الى NULL ,, لذلك سيقوم بتنفيذ التعليمات الموجودة داخل جملة الif.

سيقوم بالإستدعاء التكراري لrecursivePreOrder بحيث يضمن الطباعة بترتيب root ثم left ثم right ... الطباعة أولاً ثم استدعاء الإقتران لل(treeSubRoot->left) ثم استدعاء الإقتران لل(treeSubRoot->right) تدل على هذا الترتيب كما تبين التعليمات الظاهرة في الصورة اعلاه ... تستطيع تتبع تسلسل تنفيذ الإقتران التكراري هنا لتتأكد بنفسك من هذا الترتيب.

الرسومات التالية توضح تسلسل طباعة قيم العناصر بطريقة Pre-Order ..

**************************************************

تعمل هذه التعليمة على استدعاء الإقتران postOrderTraversing الموجود داخل الtest والذي لا يحتاج لتمرير قيم اليه ثم تطبع سطر جديد في تعليمة منفصلة ... الإقتران postOrderTraversing ..

ليقوم الإقتران postOrderTraversing بدوره بطباعة نص واستدعاء اقتران اخر وهو recursivePostOrder كما تظهر الصورة اعلاه وتمرير مؤشر الroot اليه ... الإقتران recursivePostOrder ..

يقوم بالتحقق من الشرط داخل جملة الif بحيث يتأكد ان الtreeSubRoot (الذي يشير الى الجذر) لا يشير الى NULL ,, وهو فعلاً لا يشير الى NULL ,, لذلك سيقوم بتنفيذ التعليمات الموجودة داخل جملة الif.

سيقوم بالإستدعاء التكراري لrecursivePostOrder بحيث يضمن الطباعة بترتيب left ثم right ثم root ... استدعاء الإقتران لل(treeSubRoot->left) أولاً ثم استدعاء الإقتران لل(treeSubRoot->right) ثم الطباعة تدل على هذا الترتيب كما تبين التعليمات الظاهرة في الصورة اعلاه ... تستطيع تتبع تسلسل تنفيذ الإقتران التكراري هنا لتتأكد بنفسك من هذا الترتيب.

الرسومات التالية توضح تسلسل طباعة قيم العناصر بطريقة Post-Order ..

**************************************************

تعمل هذه التعليمة على استدعاء الإقتران deleteItem الموجود في test وتمرير القيمة 2 اليه ... الإقتران deleteItem ..

ليقوم الإقتران deleteItem بدوره بإستدعاء اقتران اخر وهو Delete كما تظهر الصورة اعلاه وتمرير مؤشر الroot والقيمة 2 اليه ... الإقتران Delete ..

يحاول الإقتران Delete تنفيذ تعليمات جملة الif ولكن شرط الif غير صحيح اذ ان الTree (يشير الى الجذر في هذه الحالة) لا يشير الى NULL ,, لذلك ينتقل الى else if وأيضاً لا يكون الشرط صحيح ,, اذ أن قيمة العنصر المراد حذفه لا تساوي قيمة العنصر الذي يؤشر اليه الTree اي ان (2 لا تساوي 5) ,, لذلك ينتقل الى جملة الelse if الثانية حيث يكون الشرط صحيح وذلك لأن قيمة العنصر المراد حذفه اقل من قيمة العنصر الذي يشير اليه الTree ... الجزء المنفذ من التعليمات الموجودة في الإقتران Delete ..

تعمل التعليمة الموجودة داخل جملة الelse if الثانية على اعادة استدعاء الإقتران Delete بحيث تمرر اليه ما يشير اليه الleft الخاص بالجذر (أي العنصر ذو القيمة 3) ,, كما تمرر اليه قيمة العنصر المراد حذفه وهي ال2 ... الإقتران Delete ..

يحاول الإقتران Delete تنفيذ تعليمات جملة الif ولكن شرط الif غير صحيح اذ ان الTree (يشير الى العنصر ذو القيمة 3) لا يشير الى NULL ,, لذلك ينتقل الى else if وأيضاً لا يكون الشرط صحيح ,, اذ أن قيمة العنصر المراد حذفه لا تساوي قيمة العنصر الذي يؤشر اليه الTree اي ان (2 لا تساوي 3) ,, لذلك ينتقل الى جملة الelse if الثانية حيث يكون الشرط صحيح وذلك لأن قيمة العنصر المراد حذفه اقل من قيمة العنصر الذي يشير اليه الTree ... الجزء المنفذ من التعليمات الموجودة في الإقتران Delete ..

تعمل التعليمة الموجودة داخل جملة الelse if الثانية على اعادة استدعاء الإقتران Delete بحيث تمرر اليه ما يشير اليه الleft الخاص بالعنصر ذو القيمة 3 (أي العنصر ذو القيمة 2) ,, كما تمرر اليه قيمة العنصر المراد حذفه وهي ال2 ... الإقتران Delete ..

يحاول الإقتران Delete تنفيذ تعليمات جملة الif ولكن شرط الif غير صحيح اذ ان الTree (يشير الى العنصر ذو القيمة 2) لا يشير الى NULL ,, لذلك ينتقل الى else if حيث يكون الشرط صحيح وذلك لأن قيمة العنصر المراد حذفه تساوي قيمة العنصر الذي يشير اليه الTree ... الجزء المنفذ من التعليمات الموجودة في الإقتران Delete ..

تعمل التعليمة الموجودة داخل جملة الelse if الأولى على استدعاء الإقتران deleteNode بحيث تمرر اليه ما يشير اليه الTree وهو العنصر ذو القيمة 2 ويقوم بتعليمة منفصلة بإعادة واحد من خلال الكلمة المحجوزة return للتعليمة التي قامت بإستدعاء الإقتران Delete والموجودة في الإقتران deleteItem ... الإقتران deleteItem ..

الإقتران deleteNode ..

يعمل الإقتران deleteNode على الإعلان عن مؤشر مؤقت بإسم tempPtr وجعله يشير الى العنصر الذي يشير اليه الTree ,, اي ان tempPtr يشير الى العنصر ذو القيمة 2 ... ثم يتحقق من شرط جملة الif بحيث ان الleft الخاص بالعنصر ذو القيمة 2 يشير الى NULL وهو كذلك فعلياً ,, اذاً يقوم بتنفيذ التعليمات الموجودة في جملة الif ... الجزء المنفذ من التعليمات الموجودة في الإقتران deleteNode ..

بحيث يجعل الTree يشير الى ما يشير اليه الright الخاص بالعنصر ذو القيمة 2,, ثم يحذف ما يشير اليه الtempPtr (يحذف العنصر ذو القيمة 2).

**************************************************

كما في عملية حذف العنصر ذو القيمة 2 ,, الا انه سيتم تنفيذ التعليمات الموجودة في الelse داخل اقتران الdeleteNode ... الجزء المنفذ من التعليمات الموجودة في الإقتران deleteNode ..

بحيث يضمن الحذف بحالة الحذف الثالثة ,, اي عندما يكون هناك ورقتين متصلتين بالجذر ... preDecessor هو مؤشر تم انشاؤه بهدف البحث عن العنصر الذي يسبق الجذر الفرعي المراد حذفه (الجذر الفرعي المراد حذفه هو العنصر ذو القيمة 7) حسب طريقة الIn-Order ,, هنا سيتم استبدال قيمة العنصر المراد حذفه بالقيمة 6 وهي قيمة العنصر الذي يسبق العنصر المراد حذفه حسب ترتيب الIn-Order ,, ومن ثم يتم حذف العنصر ذو القيمة 7 وهو العنصر الذي كان يخزن القيمة 6 قبل عملية الإستبدال.

**************************************************

كما في عملية حذف العنصر ذو القيمة 7 ,, هنا سيتم استبدال قيمة الجذر بالقيمة 4 وهي قيمة العنصر الذي يسبق العنصر المراد حذفه حسب ترتيب الIn-Order ,, ومن ثم حذف العنصر ذو القيمة 5 وهو العنصر الذي كان يخزن القيمة 4 قبل عملية الإستبدال.

**************************************************