This post is also available in: English (الإنجليزية)
الشجرة الثنائية هي بنية بيانات غير خطية. وبالتالي ، يمكن عبور الشجرة الثنائية بأكثر من طريقة. دعونا نناقش عمليات اجتياز الأشجار الثنائية المختلفة التي يجب أن يعرفها الأطفال.
اجتياز أشجار البحث الثنائي
يمكن تتبع الشجرة الثنائية بثلاث طرق مختلفة وهذه هي
- طلب مسبق(Preorder)
- مرتب (Inorder)
- طلب آخر(Postorder)
اجتياز الطلب المسبق
في هذه الطريقة ، تتم أولاً زيارة جذر العقدة ، ثم الشجرة الفرعية اليسرى (أو العقدة اليسرى) ، وأخيرًا الشجرة الفرعية اليمنى (أو العقدة اليمنى). تتكرر العملية حتى تتم زيارة جميع العقد. لفهم العملية ، دعونا ننظر في الشجرة الثنائية التالية.
في هذه الشجرة الثنائية ، القيمة في الجذر هي 1. العقدة الأولى التي يجب زيارتها هي 1. التالي هو الشجرة الفرعية اليسرى. الشجرة الفرعية اليسرى هي
مرة أخرى وفقًا لطريقة الطلب المسبق ، أولاً وقبل كل شيء ، تتم زيارة الجذر (القيمة 2) ، ثم تتم زيارة العقدة اليسرى (القيمة 4) ثم زيارة العقدة اليمنى (القيمة 3). مع هذا ، تتم زيارة جميع عقد الشجرة الفرعية اليسرى.
ثم يتم زيارة الشجرة الفرعية اليمنى. الشجرة اليمنى هي –
في هذه الشجرة الفرعية ، تتم زيارة العقدة الجذرية (القيمة 3) أولاً ، متبوعة بالعقدة اليسرى (القيمة 6) وأخيراً العقدة اليمنى (القيمة 7).
ترتيب العقد التي يتم عرضها باستخدام طريقة اجتياز الطلب المسبق هو 1 و 2 و 4 و 5 و 3 و 6 و 7.
خوارزمية اجتياز الطلب المسبق
حتى يتم اجتياز جميع العقد:
Step 1: Visit the root node.
Step 2: Recursively traverse the left subtree.
Step 3: Recursively traverse the right subtree.
رمز اجتياز الطلب المسبق في ++C
struct node {
int data;
struct node *left;
struct node *right;
};
void preorder(struct node *root) {
if (root != NULL) {
cout<<root->data<<" ";
preorder(root->left);
preorder(root->right);
}
}
int main() {
struct node *root = NULL;
cout<<"Pre-Order traversal of the Binary Search Tree is: ";
preorder(root);
return 0;
}
الاجتياز الداخلي
في هذه الطريقة تتم أولاً زيارة الشجرة الفرعية اليسرى (أو العقدة اليسرى) ، ثم الجذر ، وأخيرًا الشجرة الفرعية اليمنى (أو العقدة اليمنى). تتكرر العملية حتى تتم زيارة جميع العقد. لفهم العملية ، دعونا ننظر في الشجرة الثنائية التالية.
في هذه الشجرة الثنائية ، الشجرة الفرعية اليسرى هي
مرة أخرى وفقًا لطريقة inorder ، أولاً وقبل كل شيء ، تتم زيارة اليسار (القيمة 4) ، ثم تتم زيارة الجذر (القيمة 2) ثم زيارة العقدة اليمنى (القيمة 5). مع هذا ، تتم زيارة جميع عقد الشجرة الفرعية اليسرى.
بعد ذلك ، تتم زيارة جذر الشجرة الثنائية (القيمة 1).
ثم يتم زيارة الشجرة الفرعية اليمنى. الشجرة اليمنى هي –
في هذه الشجرة الفرعية ، تتم زيارة العقدة اليسرى (القيمة 6) أولاً ، متبوعةً بعقدة جذر (القيمة 3) وأخيراً العقدة اليمنى (القيمة 7).
ترتيب العقد التي يتم عرضها باستخدام طريقة الاجتياز الداخلي هو 4 و 2 و 5 و 1 و 6 و 3 و 7.
خوارزمية الاجتياز الداخلي
حتى يتم اجتياز جميع العقد:
Step 1: Recursively traverse the left subtree.
Step 2: Visit the root node.
Step 3: Recursively traverse the right subtree.
رمز الاجتياز الداخلي في لغة سي
struct node {
int data;
struct node *left;
struct node *right;
};
void inorder(struct node *root) {
if (root != NULL) {
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
}
int main() {
struct node *root = NULL;
cout<<"In-Order traversal of the Binary Search Tree is: ";
inorder(root);
return 0;
}
اجتياز الطلب البريدي
في هذه الطريقة ، تتم أولاً زيارة الشجرة الفرعية اليسرى (أو العقدة اليسرى) ، ثم الشجرة الفرعية اليمنى (أو العقدة اليمنى) ، وأخيراً الجذر. تتكرر العملية حتى تتم زيارة جميع العقد. لفهم العملية ، دعونا ننظر في الشجرة الثنائية التالية.
في هذه الشجرة الثنائية ، الشجرة الفرعية اليسرى هي
مرة أخرى وفقًا لطريقة الطلب البريدي ، أولاً وقبل كل شيء ، اليسار (القيمة 4) تتم زيارة العقدة اليمنى (value 5) تمت زيارتها ثم زيارة الجذر (القيمة 2). مع هذا ، تتم زيارة جميع عقد الشجرة الفرعية اليسرى.
بعد ذلك ، تتم زيارة الشجرة الفرعية الصحيحة. الشجرة اليمنى هي –
في هذه الشجرة الفرعية ، العقدة اليسرى (القيمة 6) تتم زيارتها أولاً ، متبوعة بالعقدة اليمنى (value 7) وأخيرًا عقدة الجذر (القيمة 3).
وأخيرًا ، تمت زيارة جذر الشجرة الثنائية (القيمة 1).
ترتيب العقد التي يتم عرضها باستخدام طريقة السفر بعد الطلب هو 4 و 5 و 2 و 6 و 7 و 3 و 1.
خوارزمية لاجتياز الطلب البريدي
حتى يتم اجتياز جميع العقد:
Step 1: Recursively traverse the left subtree.
Step 2: Recursively traverse the right subtree.
Step 3: Visit the root node.
رمز اجتياز الطلب البريدي في ++C
struct node {
int data;
struct node *left;
struct node *right;
};
void postorder(struct node *root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
cout<<root->data<<" ";
}
}
int main() {
struct node *root = NULL;
cout<<"Post-Order traversal of the Binary Search Tree is: ";
postorder(root);
return 0;
}
ما هي شجرة البحث الثنائية؟
شجرة البحث الثنائية (BST) هي شجرة ثنائية تتبع فيها جميع العقد الخصائص التالية:
- قيمة مفتاح الشجرة الفرعية اليسرى أقل من قيمة مفتاح عقدة الجذر الخاصة بها.
- قيمة مفتاح الشجرة الفرعية اليمنى أكبر من قيمة مفتاح عقدة الجذر الخاصة بها.
في الشجرة الثنائية أعلاه ، إذا اخترت أي قيمة ، فستكون قيمة العقدة اليسرى أقل وقيمة العقدة اليمنى أكثر.
ما هو استخدام شجرة البحث الثنائية؟
يتم استخدام شجرة بحث ثنائية لفرز البيانات. عندما يتم اجتياز شجرة بحث ثنائية بطريقة داخلية ، ستكون العناصر التي تمت زيارتها بترتيب تصاعدي. دعونا نجتاز الشجرة الثنائية المذكورة أعلاه بطريقة داخلية.
بادئ ذي بدء ، تمت زيارة الشجرة الفرعية اليسرى. الشجرة الفرعية اليسرى هي
بادئ ذي بدء ، تمت زيارة العقدة اليسرى (القيمة 1). تمت زيارة الجذر التالي (القيمة 3). وبعد ذلك ، تمت زيارة الشجرة الفرعية اليمنى.
في هذه الشجرة الفرعية ، تتم زيارة العقدة اليسرى الأولى (القيمة 4) ، متبوعة بالجذر (القيمة 6) ، ويتم زيارة العقدة اليمنى (القيمة 7).
الآن ، تمت زيارة جميع العقد المتبقية للشجرة الثنائية الأصلية. الآن تمت زيارة عقدة الجذر (القيمة 8).
بعد زيارة عقدة الجذر ، تتم زيارة الشجرة الفرعية اليمنى.
في هذه الشجرة الفرعية ، نظرًا لعدم وجود عقدة يسرى ، تتم زيارة عقدة الجذر (القيمة 10) ، ثم الشجرة الفرعية اليمنى (التي تحتوي على عقدتين فقط).
أخيرًا ، تتم زيارة العقدة اليسرى (القيمة 13) للشجرة الفرعية الأخيرة متبوعة بجذرها (القيمة 14). (لا توجد شجرة فرعية أو عقدة صحيحة في هذه الشجرة الفرعية).
نتيجة الاجتياز هي 1 و 3 و 4 و 6 و 7 و 8 و 10 و 13 و 14 بترتيب تصاعدي.
