اجتياز الشجرة (الترتيب، الطلب المسبق، الطلب اللاحق)

ما هو اجتياز الشجرة؟

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

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

أنواع اجتياز الشجرة

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

• اتساع أول اجتياز
• العمق-الاجتياز الأول
• اجتياز الطلب المسبق
• اجتياز ما بعد الطلب
• اجتياز الطلب

اتساع أول اجتياز

تُعرف أيضًا باسم عملية الانتقال حسب المستوى. دعنا نفكر في الشجرة التالية لتوضيح عملية الانتقال حسب المستوى.

لذلك، سنبدأ من العقدة الجذرية "1". سيتم وضع علامة عليه على أنه المستوى 1. ثم ستنتقل الخوارزمية إلى جميع أبناء العقدة الحالية. سنقوم بزيارة العقدة 2 و 3 الآن. سيتم وضع علامة عليهم على أنهم المستوى 2.

بعد ذلك، بما أن لدينا عقدتين في المستوى 2، فسوف نقوم بزيارة أطفالهم أيضًا. لذا، سنزور 2،5,6,8,7،3،XNUMX ونضع علامة عليها على أنها المستوى XNUMX. إليك شيء لم يتم ذكره،

مستوى العقدة = مستوى العقدة الأصلية + 1

المستوى 1: 1

المستوى 2: 2 3

المستوى 3: 5 6 8 7

يتم استخدام خوارزمية مماثلة لـ BFS (اتساع البحث أولا).

إليك الكود الزائف لاجتياز ترتيب المستوى:

level_order(node)
Q → Queue()
Q.push(node)
while !Q.empty():
    current_node = Q.pop()
    print current_node.value
# Checking if the current node have any child or not
if current_node.left is not NULL:
    Q.push(current_node.left)
if current_node.right is not NULL:
    Q.push(current_node.right)

اجتياز الشجرة الثنائية بالترتيب الداخلي

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

بالنسبة للشجرة بأكملها، لنفترض أن الجذر هو 1. الآن ستتبع الخوارزمية ما يلي:

• قم بزيارة الشجرة الفرعية اليسرى للعقدة 1.
• العقدة الحالية هي 2 (لأنها الشجرة الفرعية اليسرى 1)

• قم بزيارة الشجرة الفرعية اليسرى من 2. العقدة الحالية ستكون 5 هذه المرة.
• بالانتقال إلى 5، لا يوجد أي عناصر فرعية، لذلك سيتم وضع علامة على العقدة 5 على أنها تمت زيارتها. وسوف يعود إلى العقدة الأصلية؛ وهو 2.
• عند زيارة الشجرة الفرعية اليسرى 2، سيتم الآن زيارة 2 أيضًا.
• استخدم خوارزمية ستنقل العقدة الحالية إلى الشجرة الفرعية اليمنى للعقدة 2، وهي العقدة 6. بعد زيارة العقدة 6. ستنتقل إلى العقدة الأصلية 2.
• عند زيارة العقدة 2، سنقوم الآن بزيارة العقدة الأم 2؛ وهي العقدة 1.
• بعد ذلك، سنقوم بزيارة الشجرة الفرعية الصحيحة.

وبالتالي فإن الاجتياز النهائي سيبدو كما يلي:

بالترتيب: 5 → 2 → 6 → 1 → 8 → 3 → 7

إليك الرمز الزائف للاجتياز حسب الطلب:

InOrder(node):
  if node is not null:
    InOrder(node.left)
  print node.value
    InOrder(node.right)

هذه هي الخوارزمية العودية للاجتياز الداخلي. ل شجرة البحث الثنائية (BST)، اجتياز Inorder يعطي مجموعة من القيم التي تم فرزها.

اجتياز ما بعد الطلب

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

هنا للجذر = 1،

• سنذهب إلى الشجرة الفرعية اليسرى أولاً. وبالتالي يصبح الجذر 2.
• ثم ترك 2 الشجرة الفرعية، لذلك سنذهب إلى العقدة 5. الآن الجذر هو 5.
• ليس لديها شجرة فرعية يسرى، كما أنها لا تحتوي على شجرة فرعية يمنى. لذا، الآن سنضع علامة على العقدة 5 على أنها تمت زيارتها وسننتقل إلى العقدة الأصلية.

• الآن الجذر هو 2 وتمت زيارة الشجرة الفرعية اليسرى بالكامل. سننتقل الآن إلى الشجرة الفرعية اليمنى. وبالتالي يصبح الجذر 6.
• نظرًا لأن العقدة 6 لا تحتوي على شجرة فرعية يسارية ويمينية، فسنضع علامة على العقدة 6 التي تمت زيارتها وننتقل إلى العقدة الأصلية 2.
• الآن، تتم زيارة كل من الشجرة الفرعية اليسرى واليمنى للعقدة 2. وسيتم وضع علامة عليها على أنها تمت زيارتها أيضًا.
• سننتقل إلى العقدة الأم 2، وهي العقدة 1.
• تتم زيارة الشجرة الفرعية اليسرى للجذر 1. والآن، بالمثل، سنقوم بزيارة الشجرة الفرعية اليمنى.

الدائرة المميزة هي الشجرة الفرعية اليمنى. سنقوم الآن بزيارة الشجرة الفرعية اليمنى كما قمنا بزيارة الشجرة الفرعية اليسرى. بعد ذلك سنقوم بزيارة العقدة. وبالتالي فإن الاجتياز النهائي سيكون:

طلب ما بعد الطلب: 5 → 6 → 2 → 8 → 7 → 3 → 1

إليك الرمز الزائف لاجتياز الطلب اللاحق:

PostOrder(node):
    if node is not null:
       PostOrder(node.left)
       PostOrder(node.right)
       print node.value

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

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

لذلك، دعونا نختار العقدة 1 كالجذر.

• وفقًا للخوارزمية، سيتم اكتشاف الجذر أولاً، ثم الشجرة الفرعية اليسرى، ثم الشجرة الفرعية اليمنى.
• لذلك، سنقوم بزيارة الجذر 1. ثم سننتقل إلى الشجرة الفرعية اليسرى. يصبح الجذر 2.
• سنزور العقدة رقم 2 وننتقل إلى شجرتها الفرعية اليسرى. وبذلك، يصبح الجذر هو العقدة رقم 3.
• نزور العقدة 3، ثم ننتقل إلى العقدة الأصلية. تمت الآن زيارة العقدة 2 والشجرة الفرعية اليسرى لها. حان الوقت لزيارة الشجرة الفرعية الصحيحة.
• سوف ننتقل إلى الشجرة الفرعية اليمنى، ويصبح الجذر 4. سنقوم بزيارة 4. وبما أن 4 لا تحتوي على عقدة فرعية، فسوف ننتقل إلى الشجرة الأم.
• الآن الجذر هو 2 ويتم زيارته مع شجرته الفرعية اليمنى واليسرى. لذلك، سوف ننتقل إلى العقدة الأصلية. الآن يصبح الجذر 1.
• وبالمثل، سنقوم بزيارة الشجرة الفرعية الصحيحة.

الطلب المسبق: 1 → 2 → 3 → 4 → 5 → 6 → 7

إليك الشفرة الزائفة لاجتياز الترتيب المسبق:

PreOrder(node):
   if node is not null:
     print node.value
         PreOrder(node.left)
         PreOrder(node.right)

التنفيذ في Python

class Node:
    def __init__(self, item):
    self.left = None
self.right = None
self.val = item
# creating a tree data structure
def inorder(root):
#checking if the root is null or not
if root:
    inorder(root.left)
# recursively calling left subtree
print(str(root.val) + " ", end = '')
inorder(root.right)
# recursively calling right subtree
def postorder(root):
    if root:
    postorder(root.left)
postorder(root.right)
print(str(root.val) + " ", end = '')
def preorder(root):
    if root:
    print(str(root.val) + " ", end = '')
preorder(root.left)
preorder(root.right)
def levelOrder(root):
    queue = list()
queue.append(root)
while len(queue) >
0:
    current = queue[0]
queue = queue[1: ]
print(str(current.val) + " ", end = "")
if current.left:
    queue.append(current.left)
if current.right:
   queue.append(current.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("\nLevelOrder traversal:\t", end = " ")
levelOrder(root)
print("\nInorder traversal:\t", end = " ")
inorder(root)
print("\nPreorder traversal:\t", end = " ")
preorder(root)
print("\nPostorder traversal:\t", end = " ")
postorder(root)

الإخراج:

LevelOrder traversal:  1 2 3 4 5 6 7
Inorder traversal:     4 2 5 1 6 3 7
Preorder traversal:    1 2 4 5 3 6 7
Postorder traversal:   4 5 2 6 7 3 1

التنفيذ في ج

#include <stdio.h>
#include <stdlib.h>
struct node {
   int value;
   struct node* left;
   struct node* right;
};
// Inorder traversal
void InOrder(struct node* root) {
   if (root == NULL) return;
   InOrder(root->left);
   printf("%d ", root->value);
   InOrder(root->right);
}
// PreOrder traversal
void PreOrder(struct node* root) {
  if (root == NULL) return;
  printf("%d ", root->value);
  PreOrder(root->left);
  PreOrder(root->right);
}
// PostOrder traversal
void PostOrder(struct node* root) {
  if (root == NULL) return;
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->value);
}
// Create a new Node
struct node* createNode(int value) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->value = value;
  newNode->left = NULL;
  newNode->right = NULL;
  return newNode;
}
int main() {
  struct node* root = createNode(1);
  root->left = createNode(2);
  root->right = createNode(3);
  root->left->left = createNode(4);
  root->left->right = createNode(5);
  root->right->left = createNode(6);
  root->right->right = createNode(7);
  printf("Inorder traversal:\t");
  InOrder(root);
  printf("\PreOrder traversal:\t");
  PreOrder(root);
  printf("\nPostOrder traversal:\t");
  PostOrder(root);
}

انتاج:

Inorder traversal: 4 2 5 1 6 3 7
Preorder traversal: 1 2 4 5 3 6 7
Postorder traversal: 4 5 2 6 7 3 1

بداية شئ C++ (استخدام std::queue لترتيب المستويات)

#include <stdio.h>
#include <stdlib.h>
#include<queue>
typedef struct node {
  int value;
  struct node* left;
  struct node* right;
}node;
// Inorder traversal
void InOrder(struct node* root) {
  if (root == NULL) return;
  InOrder(root->left);
  printf("%d ", root->value);
  InOrder(root->right);
}
// PreOrder traversal
void PreOrder(struct node* root) {
  if (root == NULL) return;
  printf("%d ", root->value);
  PreOrder(root->left);
  PreOrder(root->right);
}
// PostOrder traversal
void PostOrder(struct node* root) {
  if (root == NULL) return;
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->value);
}
void LevelOrder(struct node* root){
   std::queue<struct node*> Q;
   Q.push(root);
   while(!Q.empty()){
   struct node* current = Q.front();
   Q.pop();
   printf("%d ",current->value);
 if(current->left)
   Q.push(current->left);
 if(current->right)
   Q.push(current->right);
  }
}
// Create a new Node
struct node* createNode(int value) {
  struct node* newNode = new node();
  newNode->value = value;
  newNode->left = NULL;
  newNode->right = NULL;
  return newNode;
}
int main() {
  struct node* root = createNode(1);
  root->left = createNode(2);
  root->right = createNode(3);
  root->left->left = createNode(4);
  root->left->right = createNode(5);
  root->right->left = createNode(6);
  root->right->right = createNode(7);
  printf("Level Order traversal:\t");
  LevelOrder(root);
  printf("\nInorder traversal:\t");
  InOrder(root);
  printf("\nPreOrder traversal:\t");
  PreOrder(root);
  printf("\nPostOrder traversal:\t");
  PostOrder(root);
}

LevelOrder traversal:  1 2 3 4 5 6 7
Inorder traversal:     4 2 5 1 6 3 7
Preorder traversal:    1 2 4 5 3 6 7
Postorder traversal:   4 5 2 6 7 3 1

الأسئلة الشائعة