تابع شجرة البيانات الثنائية

•  Algorithms/binary trees
• أدوات الصفحة

•  دخول
•  حساب جديد

•  أحدث التغييرات
•  صفحة عشوائية
• أدوات الصفحة
  •  التاريخ
• أدوات
  •  ماذا يصل هنا
  •  تغييرات ذات علاقة
  •  رابط دائم
  •  معلومات عن هذه الصفحة
• موسوعة حسوب
  • عن موسوعة حسوب
  • دليل المساهمين
  • سياسة الخصوصية
  • إخلاء مسؤولية
• تابع موسوعة حسوب
  • حسوب I/O
  • فيسبوك
  • تويتر
  • الخلاصات

التنقل في شجرة البيانات الثنائية

يمكن التنقل traverse في بنى المعطيات الخطية (المصفوفات، القوائم المترابطة، الأرتال، الأكداس) بطريقة منطقية واحدة، ولكن أشجار البيانات تختلف من هذه الناحية في إمكانة التنقل عبر عناصرها بطرق مختلفة.

وهناك طريقتان شائعتان للتنقل عبر عناصر شجرة البيانات هما:

1. التنقل بالعمق أولًا Depth First Traversal: وتتضمن ثلاثة طرق:
   • التنقل الوسطي Inorder (يسار، جذر، يمين): ‎4 2 5 1 3‎
   • التنقل القبلي Preorder (جذر، يسار، يمين): ‎1 2 4 5 3
   • التنقل البعدي Postorder (يسار، يمين، جذر): ‎4 5 2 3 1
2. التنقل بالعرض أولًا Breadth First Traversal: وتسمى أيضًا Level Order Traversal (التنقل حسب المستويات) وتبدأ بالجذر ثم تنتقل إلى العقد المجاورة وتبدأ عملية البحث في نفس المستوى قبل الانتقال إلى المستوى اللاحق. ينتج عن تطبيق عملية التنقل هذه على الشجرة أعلاه: ‎1 2 3 4 5

التنقل بالعمق أولًا

هناك ثلاثة طرق للتنقل بالعمق أولًا:

التنقل الوسطي

تتبع عملية التنقل هذه الخوارزمية التالية:

1. الانتقال إلى الفرع الأيسر، أي استدعاء Inorder(left-subtree)‎.
2. الانتقال إلى الجذر.
3. الانتقال إلى الفرع الأيمن، أي استدعاء Inorder(right-subtree)‎.

تؤدي عملية التنقل الوسطي في شجرة البيانات أعلاه إلى الحصول على النتيجة التالية: ‎4 2 5 1 3.

التنقل القبلي

تتبع هذه العملية الخوارزمية التالية:

1. الانتقال إلى الجذر.
2. الانتقال إلى الفرع الأيسر، أي استدعاء Inorder(left-subtree)‎.
3. الانتقال إلى الفرع الأيمن، أي استدعاء Inorder(right-subtree)‎.

يمكن استخدام طريقة التنقل القبلي في إنشاء نسخة من شجرة البيانات، وتستخدم هذه الطريقة كذلك في الحصول على تعبير السابقة prefix expression في شجرة التعابير expression tree.

تؤدي عملية التنقل القبلي في شجرة البيانات أعلاه إلى الحصول على النتيجة التالية: ‎1 2 4 5 3.

التنقل البعدي

تتبع هذه العملية الخوارزمية التالية:

1. الانتقال إلى الفرع الأيسر، أي استدعاء Inorder(left-subtree)‎.
2. الانتقال إلى الفرع الأيمن، أي استدعاء Inorder(right-subtree)‎.
3. الانتقال إلى الجذر.

تستخدم عملية التنقل البعدي في مسح الشجرة، وهي مفيدة كذلك في الحصول على تعبير اللاحقة postfix expression في شجرة التعابير.

تؤدي عملية التنقل البعدي في شجرة البيانات أعلاه إلى الحصول على النتيجة التالية: ‎4 5 2 3 1.

التعقيد الزمني

التعقيد الزمني للعمليات الثلاثة السابقة هو O(n)‎.

أمثلة

تعرض الأمثلة التالية كيفية تنفيذ طرق التنقل الثلاثة أعلاه باستخدام عدد من لغات البرمجة:

• C++‎

#include <iostream> 
using namespace std; 

// تمتلك العقدة في شجرة البيانات الثنائية بيانات ومؤشرًا إلى عقدة الابن الأيسر وعقدة الابن الأيمن

struct Node 
{ 
 int data; 
 struct Node* left, *right; 
 Node(int data) 
 { 
  this->data = data; 
  left = right = NULL; 
 } 
}; 

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

void printPostorder(struct Node* node) 
{ 
 if (node == NULL) 
  return; 

 // استدعاء الدالة لذاتها على الفرع الأيسر
 printPostorder(node->left); 

 // استدعاء الدالة لذاتها على الفرع الأيمن
 printPostorder(node->right); 

 // طباعة بيانات العقدة
 cout << node->data << " "; 
} 

// طباعة محتويات شجرة البيانات الثنائية حسب طريقة التنقل الوسطي

void printInorder(struct Node* node) 
{ 
 if (node == NULL) 
  return; 

 // استدعاء الدالة لذاتها على الفرع الأيسر
 printInorder(node->left); 

 /* طباعة بيانات العقدة */
 cout << node->data << " "; 

 // استدعاء الدالة لذاتها على الفرع الأيمن
 printInorder(node->right); 
} 

// طباعة محتويات شجرة البيانات الثنائية حسب طريقة التنقل القبلي

void printPreorder(struct Node* node) 
{ 
 if (node == NULL) 
  return; 

 /* طباعات بيانات العقدة */
 cout << node->data << " "; 

 // استدعاء الدالة لذاتها على الفرع الأيسر
 printPreorder(node->left); 

 // استدعاء الدالة لذاتها على الفرع الأيمن
 printPreorder(node->right); 
} 

// اختبار الدوال السابقة
int main() 
{ 
 struct Node *root = new Node(1); 
 root->left    = new Node(2); 
 root->right   = new Node(3); 
 root->left->left  = new Node(4); 
 root->left->right = new Node(5); 

 cout << "\nPreorder traversal of binary tree is \n"; 
 printPreorder(root); 

 cout << "\nInorder traversal of binary tree is \n"; 
 printInorder(root); 

 cout << "\nPostorder traversal of binary tree is \n"; 
 printPostorder(root); 

 return 0; 
}

• بايثون:

# يمثّل هذا الصنف عقدة مفردة في شجرة البيانات الثنائية
class Node: 
 def __init__(self,key): 
  self.left = None
  self.right = None
  self.val = key 


# التنقل الوسطي عبر بيانات الشجرة الثنائية
def printInorder(root): 

 if root: 

  # استدعاء الدالة لذاتها على الفرع الأيسر 
  printInorder(root.left) 

  # طباعة بيانات العقدة 
  print(root.val), 

  # استدعاء الدالة لذاتها على الفرع الأيسر  
  printInorder(root.right) 



# التنقل البعدي عبر بيانات الشجرة الثنائية
def printPostorder(root): 

 if root: 

  # استدعاء الدالة لذاتها على الفرع الأيسر  
  printPostorder(root.left) 

  # استدعاء الدالة لذاتها على الفرع الأيمن  
  printPostorder(root.right) 

  # طباعة محتويات العقدة 
  print(root.val), 


# التنقل القبلي عبر بيانات الشجرة الثنائية 
def printPreorder(root): 

 if root: 

  # طباعة بيانات العقدة 
  print(root.val), 

  # استدعاء الدالة لذاتها على الفرع الأيسر 
  printPreorder(root.left) 

  # استدعاء الدالة لذاتها على الفرع الأيمن 
  printPreorder(root.right) 


# اختبار الدوال السابقة
root = Node(1) 
root.left  = Node(2) 
root.right  = Node(3) 
root.left.left = Node(4) 
root.left.right = Node(5) 
print "Preorder traversal of binary tree is"
printPreorder(root) 

print "\nInorder traversal of binary tree is"
printInorder(root) 

print "\nPostorder traversal of binary tree is"
printPostorder(root)

• جافا

/* صنف يتضمّن عقدتي الابنين الأيسر والأيمن لهذه العقدة إضافة إلى قيمة المفتاح */
class Node 
{ 
 int key; 
 Node left, right; 

 public Node(int item) 
 { 
  key = item; 
  left = right = null; 
 } 
} 

class BinaryTree 
{ 
 // جذر شجرة البيانات 
 Node root; 

 BinaryTree() 
 { 
  root = null; 
 } 

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

 void printPostorder(Node node) 
 { 
  if (node == null) 
   return; 

  // first recur on left subtree 
  printPostorder(node.left); 

  // then recur on right subtree 
  printPostorder(node.right); 

  // now deal with the node 
  System.out.print(node.key + " "); 
 } 

 // طباعة محتويات شجرة البيانات الثنائية حسب طريقة التنقل الوسطي
 void printInorder(Node node) 
 { 
  if (node == null) 
   return; 

  // استدعاء الدالة لذاتها على الفرع الأيسر
  printInorder(node.left); 

  // طباعة بيانات العقدة
  System.out.print(node.key + " "); 

  // استدعاء الدالة لذاتها على الفرع الأيمن
  printInorder(node.right); 
 } 

 // طباعة محتويات شجرة البيانات الثنائية حسب طريقة التنقل القبلي
 void printPreorder(Node node) 
 { 
  if (node == null) 
   return; 

  /* طباعة بيانات العقدة */
  System.out.print(node.key + " "); 

  // استدعاء الدالة لذاتها على الفرع الأيسر
  printPreorder(node.left); 

  // استدعاء الدالة لذاتها على الفرع الأيمن
  printPreorder(node.right); 
 } 

 // دوال لتغليف الدوال التعاودية السابقة 
 void printPostorder() {  printPostorder(root); } 
 void printInorder() {  printInorder(root); } 
 void printPreorder() {  printPreorder(root); } 

 // اختبار الدوال السابقة
 public static void main(String[] args) 
 { 
  BinaryTree tree = new BinaryTree(); 
  tree.root = new Node(1); 
  tree.root.left = new Node(2); 
  tree.root.right = new Node(3); 
  tree.root.left.left = new Node(4); 
  tree.root.left.right = new Node(5); 

  System.out.println("Preorder traversal of binary tree is "); 
  tree.printPreorder(); 

  System.out.println("\nInorder traversal of binary tree is "); 
  tree.printInorder(); 

  System.out.println("\nPostorder traversal of binary tree is "); 
  tree.printPostorder(); 
 } 
}

تعطي الشيفرات السابقة المخرجات التالية:

Preorder traversal of binary tree is
1 2 4 5 3 
Inorder traversal of binary tree is
4 2 5 1 3 
Postorder traversal of binary tree is
4 5 2 3 1

التنقل بالعرض أولًا

يمكن تنفيذ عملية النتقل بالعرض أولًا بطريقتين:

الطريقة الأولى: استخدام دالة لطباعة مستوى معين

الخوارزمية

تتضمّن هذه الطريقة دالتين، الأولى مهمّتها طباعة جميع العقد في مستوى معين (printGivenLevel) والثانية طباعة مستوى التنقل في الشجرة (printLevelorder). تستفيد الدالة printLevelorder من الدالة printGivenLevel لطباعة العقد في جميع المستويات واحدًا تلو الآخر وابتداءً من الجذر.

أمثلة

تعرض الأمثلة التالية طريقة تنفيذ عملية البحث بالعرض أولًا وفي عدد من لغات البرمجة:

• C++‎:

#include <bits/stdc++.h> 
using namespace std; 

/* تمتلك العقدة في شجرة البيانات الثنائية معلومات، ومؤشرًا إلى 
عقدة الابن الأيسر ومؤشراً إلى عقدة الابن الأيمن */
class node 
{ 
 public: 
 int data; 
 node* left, *right; 
}; 


void printGivenLevel(node* root, int level); 
int height(node* node); 
node* newNode(int data); 

// دالة لطباعة نتيجة إجراء عملية التنقل عبر مستويات الشجرة
void printLevelOrder(node* root) 
{ 
 int h = height(root); 
 int i; 
 for (i = 1; i <= h; i++) 
  printGivenLevel(root, i); 
} 

// تطبع الدالة العقد الموجودة في مستوى معين
void printGivenLevel(node* root, int level) 
{ 
 if (root == NULL) 
  return; 
 if (level == 1) 
  cout << root->data << " "; 
 else if (level > 1) 
 { 
  printGivenLevel(root->left, level-1); 
  printGivenLevel(root->right, level-1); 
 } 
} 

/* تحسب الدالة ارتفاع الشجرة
ارتفاع الشجرة هو أطول مسار من العقدة الجذر نزولًا إلى أبعد عقدة ورقة
*/
int height(node* node) 
{ 
 if (node == NULL) 
  return 0; 
 else
 { 
  // تحسب الدالة ارتفاع كل شجرة فرعية
  int lheight = height(node->left); 
  int rheight = height(node->right); 

  // استخدام أعلى ارتفاع
  if (lheight > rheight) 
   return(lheight + 1); 
  else return(rheight + 1); 
 } 
} 

// دالة مساعدة تحجز عقدة جديدة مع البيانات المعطاة ومؤشرين للعقدة اليسرى واليمنى 
node* newNode(int data) 
{ 
 node* Node = new node(); 
 Node->data = data; 
 Node->left = NULL; 
 Node->right = NULL; 

 return(Node); 
} 

// اختبار الدوال السابقة
int main() 
{ 
 node *root = newNode(1); 
 root->left = newNode(2); 
 root->right = newNode(3); 
 root->left->left = newNode(4); 
 root->left->right = newNode(5); 

 cout << "Level Order traversal of binary tree is \n"; 
 printLevelOrder(root); 

 return 0; 
}

• بايثون

# بنية العقدة
class Node: 

 # دالة مساعدة لإنشاء عقدة جديدة
 def __init__(self, key): 
  self.data = key 
  self.left = None
  self.right = None


# دالة لطباعة نتيجة التنقل عبر مستويات الشجرة
def printLevelOrder(root): 
 h = height(root) 
 for i in range(1, h+1): 
  printGivenLevel(root, i) 


# تطبع الدالة العقد الموجودة في مستوى معين
def printGivenLevel(root , level): 
 if root is None: 
  return
 if level == 1: 
  print "%d" %(root.data), 
 elif level > 1 : 
  printGivenLevel(root.left , level-1) 
  printGivenLevel(root.right , level-1) 

""" تحسب الدالة ارتفاع الشجرة
ارتفاع الشجرة هو أطول مسار من العقدة الجذر نزولًا إلى أبعد عقدة ورقة
"""

def height(node): 
 if node is None: 
  return 0
 else : 
  # حساب ارتفاع كل شجرة فرعية
  lheight = height(node.left) 
  rheight = height(node.right) 

  # استخدام الارتفاع الأعلى
  if lheight > rheight : 
   return lheight+1
  else: 
   return rheight+1

# اختبار الدوال السابقة
root = Node(1) 
root.left = Node(2) 
root.right = Node(3) 
root.left.left = Node(4) 
root.left.right = Node(5) 

print "Level order traversal of binary tree is -"
printLevelOrder(root)

• جافا

/* صنف يحتوي على الابن الأيسر والأيمن للعقدة الحالية وقيمة مفتاح */
class Node 
{ 
 int data; 
 Node left, right; 
 public Node(int item) 
 { 
  data = item; 
  left = right = null; 
 } 
} 

class BinaryTree 
{ 
 // جذر الشجرة الثنائية
 Node root; 

 public BinaryTree() 
 { 
  root = null; 
 } 

 /* دالة لطباعة نتيجة التنقل عبر مستويات الشجرة */
 void printLevelOrder() 
 { 
  int h = height(root); 
  int i; 
  for (i=1; i<=h; i++) 
   printGivenLevel(root, i); 
 } 

    
 
    /* تحسب الدالة ارتفاع الشجرة
    ارتفاع الشجرة هو أطول مسار من العقدة الجذر نزولًا إلى أبعد عقدة ورقة
    */
 int height(Node root) 
 { 
  if (root == null) 
  return 0; 
  else
  { 
   /* حساب ارتفاع كل شجرة فرعية */
   int lheight = height(root.left); 
   int rheight = height(root.right); 
   
   /* استخدام أعلى ارتفاع */
   if (lheight > rheight) 
    return(lheight+1); 
   else return(rheight+1); 
  } 
 } 

 /* طباعة العقد الموجودة في مستوى معين */
 void printGivenLevel (Node root ,int level) 
 { 
  if (root == null) 
   return; 
  if (level == 1) 
   System.out.print(root.data + " "); 
  else if (level > 1) 
  { 
   printGivenLevel(root.left, level-1); 
   printGivenLevel(root.right, level-1); 
  } 
 } 
 
 /* اختبار الدوال السابقة */
 public static void main(String args[]) 
 { 
 BinaryTree tree = new BinaryTree(); 
 tree.root= new Node(1); 
 tree.root.left= new Node(2); 
 tree.root.right= new Node(3); 
 tree.root.left.left= new Node(4); 
 tree.root.left.right= new Node(5); 
  
 System.out.println("Level order traversal of binary tree is "); 
 tree.printLevelOrder(); 
 } 
}

تعطي الأمثلة السابقة المخرجات التالية:

Level order traversal of binary tree is - 
1 2 3 4 5

التعقيد الزمني

يبلغ التعقيد الزمني لهذه الطريقة في أسوأ الحالات O(n^2)‎. في أشجار البيانات المائلة skewed تستغرق الدالة O(n)‎ من الوقت وتمثّل n عدد العقد في شجرة البيانات المائلة؛ لذا يصبح التعقيد الزمني للدالة printLevelOrder()‎ مساويًا لـ ‎O(n) + O(n-1) + O(n-2) + .. + O(1)‎‎ والتي تعادل O(n^2)‎.