كيفية اجتياز شجرة بحث ثنائية

تعد الأشجار الثنائية من أكثر هياكل البيانات استخدامًا في البرمجة. تسمح شجرة البحث الثنائية (BST) بتخزين البيانات في شكل عقد (العقدة الأصلية والعقدة الفرعية العقدة) بحيث تكون العقدة الفرعية اليسرى أصغر من العقدة الأصلية والعقدة الفرعية اليمنى أكبر.

تسمح أشجار البحث الثنائية بعمليات اجتياز وبحث وحذف وإدراج فعالة. في هذه المقالة ، ستتعرف على الطرق الثلاث لاجتياز شجرة بحث ثنائية: اجتياز الطلب المسبق ، واجتياز الطلب الداخلي ، واجتياز الطلب اللاحق.

اجتياز الداخل

الاجتياز الداخلي هو عملية اجتياز العقد لـ شجرة البحث الثنائية عن طريق المعالجة المتكررة للشجرة الفرعية اليسرى ، ثم معالجة عقدة الجذر ، وأخيراً معالجة الشجرة الفرعية اليمنى بشكل متكرر. نظرًا لأنها تعالج العقد بترتيب قيمة تصاعدي ، تسمى التقنية اجتياز الداخل.

العبور هو عملية زيارة كل عقدة في بنية بيانات الشجرة مرة واحدة بالضبط.

خوارزمية الاجتياز الداخلي

كرر لاجتياز جميع عقد BST:

1. اجتياز بشكل متكرر الشجرة الفرعية اليسرى.
2. قم بزيارة عقدة الجذر.
3. اجتياز بشكل متكرر الشجرة الفرعية اليمنى.

تصور الاجتياز الداخلي

يمكن أن يساعد المثال المرئي في شرح اجتياز شجرة البحث الثنائية. يوضح هذا الشكل الاجتياز الداخلي لمثال لشجرة البحث الثنائية:

في شجرة البحث الثنائية هذه ، 56 هي عقدة الجذر. أولاً ، عليك اجتياز الشجرة الفرعية اليسرى 32 ، ثم العقدة الجذرية 56 ، ثم الشجرة الفرعية اليمنى 62.

بالنسبة للشجرة الفرعية 32 ، قم أولاً باجتياز الشجرة الفرعية اليسرى ، 28. لا تحتوي هذه الشجرة الفرعية على أي أطفال ، لذلك اجتياز العقدة 32 بعد ذلك. بعد ذلك ، اجتز الشجرة الفرعية اليمنى ، 44 ، والتي ليس لها أيضًا أبناء. لذلك فإن ترتيب الاجتياز للشجرة الفرعية عند 32 هو 28 -> 32 -> 44.

بعد ذلك ، قم بزيارة عقدة الجذر ، 56.

بعد ذلك ، اجتز الشجرة الفرعية اليمنى ، المتجذرة عند 62. ابدأ باجتياز شجرتها الفرعية اليسرى ، المتجذرة في 58. ليس لديها أي أطفال ، لذا قم بزيارة العقدة 62 بعد ذلك. أخيرًا ، اجتز الشجرة الفرعية اليمنى ، 88 ، والتي ليس لها أيضًا أبناء.

لذلك تقوم الخوارزمية بزيارة عقد الشجرة بالترتيب التالي:

28 -> 32 -> 44 -> 56 -> 58 -> 62 -> 88

تطبيق الاجتياز الداخلي

يمكنك استخدام الاجتياز بالترتيب للحصول على قيم عناصر العقدة بترتيب متزايد. للحصول على القيم بترتيب تنازلي ، ما عليك سوى عكس العملية: قم بزيارة الشجرة الفرعية اليمنى ، ثم عقدة الجذر ، ثم الشجرة الفرعية اليسرى. يمكنك استخدام الخوارزمية للعثور على تعبير البادئة لشجرة التعبير.

اجتياز الطلب المسبق

يشبه اجتياز الطلب المسبق الأمر الداخلي ، ولكنه يعالج العقدة الجذرية قبل المعالجة العودية للشجرة الفرعية اليسرى ، ثم الشجرة الفرعية اليمنى.

خوارزمية اجتياز الطلب المسبق

كرر لاجتياز جميع عقد BST:

1. قم بزيارة عقدة الجذر.
2. اجتياز بشكل متكرر الشجرة الفرعية اليسرى.
3. اجتياز بشكل متكرر الشجرة الفرعية اليمنى.

تصور اجتياز الطلب المسبق

يوضح الشكل التالي اجتياز الطلب المسبق لشجرة البحث الثنائية:

في شجرة البحث الثنائية هذه ، ابدأ بمعالجة عقدة الجذر ، 56. ثم اعبر الشجرة الفرعية اليسرى ، 32 ، متبوعة بالشجرة الفرعية اليمنى ، 62.

بالنسبة للشجرة الفرعية اليسرى ، قم بمعالجة القيمة عند عقدة الجذر ، 32. بعد ذلك ، اعبر الشجرة الفرعية اليسرى ، 28 ، ثم أخيرًا الشجرة الفرعية اليمنى ، 44. يكمل هذا اجتياز الشجرة الفرعية اليسرى المتجذرة عند 32. يتم الاجتياز بالترتيب التالي: 56 -> 32 -> 28 -> 44.

بالنسبة للشجرة الفرعية اليمنى ، قم بمعالجة القيمة عند عقدة الجذر ، 62. بعد ذلك ، اعبر الشجرة الفرعية اليسرى ، 58 ، ثم أخيرًا الشجرة الفرعية اليمنى ، 88. مرة أخرى ، لا تحتوي أي من العقدة على أي توابع ، لذلك يكون الاجتياز قد اكتمل في هذه المرحلة.

لقد اجتزت الشجرة الكاملة بالترتيب التالي:

56 -> 32 -> 28 -> 44 -> 62 -> 58 -> 88

تطبيق اجتياز الطلب المسبق

يمكنك استخدام اجتياز الطلب المسبق لإنشاء نسخة من الشجرة بسهولة أكبر.

اجتياز الطلب البريدي

اجتياز Postorder هو عملية اجتياز عقد شجرة بحث ثنائية بشكل متكرر معالجة الشجرة الفرعية اليسرى ، ثم معالجة الشجرة الفرعية اليمنى بشكل متكرر ، وأخيرًا معالجة عقدة الجذر. نظرًا لأنها تعالج العقدة الجذرية بعد كلتا الشجرتين الفرعيتين ، فإن هذه الطريقة تسمى اجتياز الطلب.

خوارزمية اجتياز الطلب البريدي

كرر لاجتياز جميع عقد BST:

1. اجتياز بشكل متكرر الشجرة الفرعية اليسرى.
2. اجتياز بشكل متكرر الشجرة الفرعية اليمنى.
3. قم بزيارة عقدة الجذر.

تمثيل مرئي لاجتياز الطلب

يوضح الشكل التالي اجتياز الطلب اللاحق لشجرة البحث الثنائية:

ابدأ باجتياز الشجرة الفرعية اليسرى ، 32 ، ثم الشجرة الفرعية اليمنى ، 62. قم بالإنهاء بمعالجة عقدة الجذر ، 56.

لمعالجة الشجرة الفرعية ، المتجذرة في 32 ، اجتياز الشجرة الفرعية اليسرى ، 28. نظرًا لأن 28 ليس لديها أي أطفال ، انتقل إلى الشجرة الفرعية اليمنى ، 44. العملية 44 نظرًا لعدم وجود أطفال أيضًا. أخيرًا ، قم بمعالجة عقدة الجذر ، 32. لقد اجتزت هذه الشجرة الفرعية بالترتيب 28 -> 44 -> 32.

قم بمعالجة الشجرة الفرعية الصحيحة باستخدام نفس الطريقة لزيارة العقد بالترتيب 58 -> 88 ← 62.

أخيرًا ، قم بمعالجة عقدة الجذر ، 56. ستجتاز الشجرة الكاملة بهذا الترتيب:

28 -> 44 -> 32 -> 58 -> 88 -> 62 -> 56

تطبيق الاجتياز بالبريد

يمكنك استخدام اجتياز طلب التسجيل لحذف شجرة من ورقة إلى جذر. يمكنك أيضًا استخدامه للعثور على تعبير postfix لشجرة التعبير.

لزيارة جميع العقد الطرفية لعقدة معينة قبل زيارة العقدة نفسها ، يمكنك استخدام تقنية اجتياز الطلب البريدي.

تعقيد الزمان والمكان لمسارات شجرة البحث الثنائية

التعقيد الزمني لجميع تقنيات الاجتياز الثلاثة هو على)، أين ن هو حجم شجرة ثنائية. التعقيد المكاني لجميع تقنيات المسح هو أوه)، أين ح هو ارتفاع الشجرة الثنائية.

حجم الشجرة الثنائية يساوي عدد العقد في تلك الشجرة. ارتفاع الشجرة الثنائية هو عدد الحواف بين عقدة جذر الشجرة وأبعد عقدتها الورقية.

شفرة Python لاجتياز شجرة البحث الثنائي

يوجد أدناه برنامج Python لإجراء عمليات اجتياز شجرة البحث الثنائية الثلاثة:

# Node class is used to create individual nodes
# of the Binary Search Tree (BST)
classNode:
def__init__(self, element):
self.left = None
self.right = None
self.value = element
# Function to perform the inorder tree traversal
definorder(root):
 if root:
# Traverse left subtree
inorder(root.left)
# Traverse root
print(str(root.value) + ", ", end='')
# Traverse right subtree
inorder(root.right)
# Function to perform the postorder tree traversal
defpostorder(root):
 if root:
# Traverse left subtree
postorder(root.left)
# Traverse right subtree
postorder(root.right)
# Traverse root
print(str(root.value) + ", ", end='')
# Function to perform the preorder tree traversal
defpreorder(root):
 if root:
# Traverse root
print(str(root.value) + ", ", end='')
# Traverse left subtree
preorder(root.left)
# Traverse right subtree
preorder(root.right)
# Creating nodes of the tree
root = Node(56)
root.left = Node(32)
root.right = Node(62)
root.left.left = Node(28)
root.left.right = Node(44)
root.right.left = Node(58)
root.right.right = Node(88)
print("Inorder Traversal of BST: ")
inorder(root)
print()
print("Preorder Traversal of BST: ")
preorder(root)
print()
print("Postorder Traversal of BST: ")
postorder(root)

يجب أن ينتج هذا البرنامج المخرجات التالية:

يجب أن يعرف الخوارزميات للمبرمجين

تعد الخوارزميات جزءًا أساسيًا من رحلة كل مبرمج. من الأهمية بمكان أن يكون المبرمج ضليعًا في الخوارزميات. يجب أن تكون على دراية ببعض الخوارزميات مثل دمج الفرز ، والفرز السريع ، والبحث الثنائي ، والبحث الخطي ، والبحث المتعمق أولاً ، وما إلى ذلك.