الفرق بين المراجعتين لصفحة: «Algorithms/binary trees»

مراجعة 12:18، 24 يونيو 2019

تصنف المصفوفات والقوائم المترابطة والأكداس والأرتال كبنى معطيات خطية، أمّا أشجار البيانات فتصنّف كبنى معطيات هرمية hierarchical.

تسمى العقدة العليا في شجرة البيانات بجذر الشجرة root، وتسمى العناصر التي تتفرع من عنصر معين بأبناء ذلك العنصر children، أما العنصر الذي يكون فوق عنصر آخر فيسمى بالعنصر الأب parent، أما العناصر التي لا تمتلك أبناء فتسمّى بالأوراق leaves.

في المثال التالي العنصر a هو ابن للعنصر f والعنصر f هو أب العنصر a.

      tree
      ----
       j    <-- جذر
     /   \
    f      k  
  /   \      \
 a     h      z    <-- أوراق

تطبيقات تستخدم أشجار البيانات

تستخدم أشجار البيانات لتخزين المعلومات بصورة هرمية، مثل نظام الملفات في الحاسوب:

file system
-----------
     /    <-- الجذر
  /      \
...       home
      /          \
   ugrad        course
    /       /      |     \
  ...      cs101  cs112  cs113

وهناك تطبيقات أخرى لأشجار البيانات منها:

تتيح أشجار البيانات (مع بعض الترتيب مثل أشجار البيانات الثنائية) إجراء عمليات وصول وبحث متوسطة السرعة (أسرع من القوائم المترابطة وأبطأ من المصفوفات).
تتيح أشجار البيانات إجراء عمليات إدراج وحذف متوسطة السرعة (أسرع من المصفوفات وأبطأ من القوائم المترابطة غير المرتبة).
تشبه أشجار البيانات القوائم المترابطة في عدم وجود حدّ علوي لعدد العقد وذلك لأنّها مترابطة بواسطة المؤشرات.
معالجة البيانات الهرمية.
تسهيل عملية البحث عن المعلومات (راجع التنقل في شجرة البيانات).
معالجة القوائم المرتبة من البيانات.
تستخدم أشجار البيانات كمسار عمل لمعالجة الصور الرقمية وإضافة المؤثرات البصرية.
خوارزميات المسارات Router.
صورة من صور عمليات اتخاذ القرار ذات المراحل المتعددة.
الكومة هي شجرة بيانات ويمكن إنشاؤها باستخدام المصفوفات وتستخدم لإنشاء أرتال الأولوية.
B-Tree و B+ Tree وتستخدم لتنفيذ عملية الفهرسة في قواعد البيانات.
شجرة الصيغة Syntax Tree: تستخدم في المصرّفات Compilers.
K-D Tree: شجرة لتجزئة المساحة وتستخدم لترتيب النقاط في مساحة من K من الأبعاد.
شجرة اللواحق Suffix Tree: وتستخدم للبحث السريع عن نمط معين في نص ثابت.

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

تسمى الشجرة التي يمتلك كل عنصر فيها ابنين اثنين على الأكثر بشجرة البيانات الثنائية Binary Tree، ولما كان كل عنصر يمتلك ابنين فقط، فيمكن تسميتهما بالابن الأيمن والابن الأيسر.

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

تمثّل شجرة البيانات الثنائية بواسطة مؤشر إلى العقدة العلوية في شجرة البيانات، وإن كانت الشجرة فارغة فإنّ قيمة الجذر تساوي NULL.

تضمّ العقدة الأجزاء التالية:

البيانات.
مؤشر إلى العقدة اليسرى.
مؤشر إلى العقدة اليمنى.

يمكن تمثيل العقدة في لغة C بواسطة البنى structures، ويعرض المثال التالية عقدة تضمّ بيانات عددية:

struct node 
{ 
int data; 
struct node *left; 
struct node *right; 
};

أما في لغتي بايثون وجافا فيمكن استخدام الأصناف لتمثيل العقد:

بايثون:

class Node: 
	def __init__(self,key): 
		self.left = None
		self.right = None
		self.val = key

جافا

class Node 
{ 
	int key; 
	Node left, right; 

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

إنشاء شجرة بيانات ثنائية بسيطة

تعرض الشيفرات التالية طريقة إنشاء شجرة البيانات الثنائية التالية والتي تضمّ أربع عقد:

      tree
      ----
       1    <-- الجذر
     /   \
    2     3  
   /   
  4

C++‎:

struct node 
{ 
	int data; 
	struct node *left; 
	struct node *right; 
}; 

/* تحجز هذه الدالة عقدة جديدة تمتلك البيانات المعطاة ومؤشرين للعقدتين اليمنى واليسرى واللتان تحملان القيمة null */
struct node* newNode(int data) 
{ 
// حجز الذاكرة للعقدة الجديدة
struct node* node = (struct node*)malloc(sizeof(struct node)); 

// إسناد البيانات إلى هذه العقدة
node->data = data; 

// NULL تهيئة العقدتين اليمنى واليسرى لتحملا القيمة 
node->left = NULL; 
node->right = NULL; 
return(node); 
} 


int main() 
{ 
// إنشاء الجذر
struct node *root = newNode(1); 
/* بعد تنفيذ العبارة أعلاه تصبح الشجرة بالشكل التالي

		1 
	/       \ 
   NULL    NULL 
*/
	

root->left	 = newNode(2); 
root->right	 = newNode(3); 
/* أصبحت العقدتان 2 و 3 الابنين الأيسر والأيمن للعقدة 1
		1 
		/ \ 
		2	 3 
	/ \ / \ 
	NULL NULL NULL NULL 
*/


root->left->left = newNode(4); 
/* أصبحت العقدة 4 الابن الأيسر للعقدة 2 
		1 
	/	 \ 
	2		 3 
	/ \	 / \ 
4 NULL NULL NULL 
/ \ 
NULL NULL 
*/

getchar(); 
return 0; 
}

بايثون:

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


# إنشاء الجذر
root = Node(1) 
''' أصبحت الشجرة بعد تنفيذ العبارة السابقة بالشكل التالي 
		1 
	/ \ 
	None None'''

root.left	 = Node(2); 
root.right	 = Node(3); 
	
''' أصبحت العقدتان 2 و 3 الابنين الأيسر والأيمن للعقدة 1 
		1 
		/ \ 
		2	 3 
	/ \ / \ 
None None None None'''


root.left.left = Node(4); 
'''أصبحت العقدة 4 الابن الأيسر للعقدة 2 
		1 
	/	 \ 
	2		 3 
	/ \	 / \ 
4 None None None 
/ \ 
None None'''

جافا:

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

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

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

	// الدوال البانية
	BinaryTree(int key) 
	{ 
		root = new Node(key); 
	} 

	BinaryTree() 
	{ 
		root = null; 
	} 

	public static void main(String[] args) 
	{ 
		BinaryTree tree = new BinaryTree(); 

		/*إنشاء الجذر*/
		tree.root = new Node(1); 

		/* تصبح الشجرة بعد تنفيذ العبارة السابقة بالشكل التالي 

			1 
			/ \ 
		null null	 */

		tree.root.left = new Node(2); 
		tree.root.right = new Node(3); 

		/* أصبحت العقدتان 2 و 3 الابنين الأيسر والأيمن للعقدة 1 
			1 
			/ \ 
			2	 3 
		/ \ / \ 
		null null null null */


		tree.root.left.left = new Node(4); 
		/* أصبحت العقدة 4 الابن الأيسر للعقدة 2 
					1 
				/	 \ 
			2		 3 
			/ \	 / \ 
			4 null null null 
		/ \ 
		null null 
		*/
	} 
}

خصائص أشجار البيانات الثنائية

1- أقصى عدد للعقد في أي مستوى 'l' في شجرة البيانات الثنائية هو ‎2^‎l-1

يقصد بالمستوى هنا هو عدد العقد ابتداءً من الجذر وانتهاءً بالعقدة المعنية (ومن ضمنها الجذر والعقدة المعنية)، ويقع الجذر في المستوى رقم 1.

يمكن إثبات هذه القاعدة بالطريقة التالية:

l = 1 في الجذر، وبهذا يصبح عدد العقد ‎2^1-1 = 1‎

لو فرضنا أنّ أقصى عدد للعقد في المستوى l هو ‎2^l-1، ولمّا كانت كل عقدة في شجرة البيانات الثنائية تمتلك عقدتين فقط من عقد الأبناء، فإنّ المستوى التالي لهذه العقدة سيمتلك ضعف عدد العقد، أي ‎2*2^l-1.

2- أقصى عدد للعقد في شجرة بيانات ثنائية ذات ارتفاع 'h' هو ‎2^h-1‎

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

تمتلك الشجرة أقصى عدد من العقد إن احتوت جميع المستويات على أقصى عدد من العقد؛ لذا فإنّ العدد الأقصى للعقد في الشجرة الثنائية ذات الارتفاع h هو 1 + 2 + 4 + .. + 2^h-1، وهي متسلسلة هندسية بسيطة تضمّ h من الأطراف ومجموعها هو ‎‎‎2^h-1‎‎‎.

تشير بعض الكتب إلى أنّ ارتفاع الجذر هو 0، وعلى هذا الفرض تصبح الصيغة السابقة بالهيئة التالية: 2‎‎‎^h+1-1‎‎‎.

3- إن أدنى ارتفاع ممكن أو أدنى عدد من المستويات في شجرة بيانات ثنائية تمتلك N من العقد هو Log₂(N+1)‎

لو أخذنا بنظر الاعتبار الفرض القائل بأن عقدة الورقة تمتلك الارتفاع 0، فإنّ الصيغة السابقة ستصبح: ‎Log₂(N+1)‎ - 1.

4- شجرة البيانات الثنائية التي تحتوي على L من الأوراق تمتلك على الأقل Log₂L + 1 من المستويات

تمتلك شجرة البيانات الثنائية أقصى عدد من الأوراق (وأدنى عدد من المستويات) عندما تكون جميع المستويات مملوءة بالكامل، ولو فرضنا أنّ لدنيا مستوى واحدًا فقط، فإنّ ما يلي صحيح لعدد L من من الأوراق.

   L   <=  2l-1  [From Point 1]
   l =   ? Log2L ? + 1 
   l هو أدنى عدد من المستويات
   where l is the minimum number of levels.

5- في شجرة البيانات الثنائية التي تمتلك كل عقدة فيها إمّا 0 أو 2 من عقد الأبناء، فإنّ عدد عقد الأوراق هو دائمًا أكبر بواحد من العقد التي تمتلك عقدتي أبناء

   L = T + 1
	  L = عدد عقد الأوراق
      T = عدد العقد الداخلية التي تمتلك عقدتي أبناء

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

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

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

               18
           /       \  
         15         30  
        /  \        /  \
      40    50    100   40

             18
           /    \   
         15     20    
        /  \       
      40    50   
    /   \
   30   50

               18
            /     \  
          40       30  
                   /  \
                 100   40

إن عدد عقد الأوراق في شجرة البيانات الثنائية الممتلئة يساوي عدد العقد الداخلية مضافًا إليه واحد.

L = I + 1

L = عدد عقد الأوراق.

I = عدد العقد الداخلية.

شجرة البيانات الثنائية الكاملة Complete

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

               18
           /       \  
         15         30  
        /  \        /  \
      40    50    100   40


               18
           /       \  
         15         30  
        /  \        /  \
      40    50    100   40
     /  \   /
    8   7  9

الكومات الثنائية هي من الأمثلة العملية على أشجار البيانات الثنائية الكاملة.

أشجار البيانات الثنائية التامّة Perfect

تعدّ شجرة البيانات الثنائية تامّة إن كان لجميع العقد الداخلية عقدتا أبناء وكانت جميع عقد الأوراق في مستوى واحد.

               18
           /       \  
         15         30  
        /  \        /  \
      40    50    100   40


               18
           /       \  
         15         30

تحتوي شجرة البيانات الثنائية التامّة ذات الارتفاع h على ‎2^h-1 من العقد.

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

      			   الشخص
			/    	          \
		  الأب                 الأم
	 /          \         /         \
أب الأب    أم الأب    أب الأم       أم الأم

شجرة البيانات الثنائية المتوازنة Balanced

تكون شجرة البيانات الثنائية متوازنة إن كان ارتفاع الشجرة هو O(Log n)‎ و n هو عدد العقد. على سبيل المثال تحافظ شجرة AVL على الارتفاع O(Log n)‎ وذلك بالتأكد من أنّ الفرق بين ارتفاع الأفرع اليسرى والأفرع اليمنى هو 1. أما أشجار البيانات أحمر-أسود فتحافظ على الارتفاع O(Log n)‎ وذلك بالتأكد من أن عدد العقد السوداء متساوٍ في كل المسارات التي تبدأ من الجذر وتنتهي بعقدة ورقة ولا وجود لعقد حمراء مجاورة.

تعدّ أشجار البيانات الثنائية المتوازنة خيارًا جيّدًا من ناحية الأداء في عمليات البحث والإدراج والحذف لأنّ التعقيد الزمني لها هو O(Log n)‎.

الأشجار البيانية الثنائية المتحللة degenerate (المريضة pathological)

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

إدراج العناصر في أشجار البيانات الثنائية

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

أمثلة

تعرض الأمثلة التالية طريقة إدراج عنصر في شجرة البيانات الثنائية وفي عدد من لغات البرمجة:

C++‎:

#include <iostream> 
#include <queue> 
using namespace std; 

/* تمتلك العقدة في الشجرة الثائية مفتاحًا ومؤشرًا إلى العقدة الابن اليسرى ومؤشراً إلى العقدة الابن اليمنى */
struct Node { 
	int key; 
	struct Node* left, *right; 
}; 

/* دالة لإنشاء عقدة جديدة في الشجرة الثنائية وإعادة المؤشر */
struct Node* newNode(int key) 
{ 
	struct Node* temp = new Node; 
	temp->key = key; 
	temp->left = temp->right = NULL; 
	return temp; 
}; 

/* التنقل عبر عناصر الشجرة الثنائي حسب الترتيب */

void inorder(struct Node* temp) 
{ 
	if (!temp) 
		return; 

	inorder(temp->left); 
	cout << temp->key << " "; 
	inorder(temp->right); 
} 

/* دالة لإدراج عنصر في الشجرة الثنائية */

void insert(struct Node* temp, int key) 
{ 
	queue<struct Node*> q; 
	q.push(temp); 

	// التنقل عبر مستويات الشجرة الثنائية بحثًا عن مكان فارغ
    
    while (!q.empty()) { 
		struct Node* temp = q.front(); 
		q.pop(); 

		if (!temp->left) { 
			temp->left = newNode(key); 
			break; 
		} else
			q.push(temp->left); 

		if (!temp->right) { 
			temp->right = newNode(key); 
			break; 
		} else
			q.push(temp->right); 
	} 
} 

// اختبار الدوال السابقة
int main() 
{ 
	struct Node* root = newNode(10); 
	root->left = newNode(11); 
	root->left->left = newNode(7); 
	root->right = newNode(9); 
	root->right->left = newNode(15); 
	root->right->right = newNode(8); 

	cout << "Inorder traversal before insertion:"; 
	inorder(root); 

	int key = 12; 
	insert(root, key); 

	cout << endl; 
	cout << "Inorder traversal after insertion:"; 
	inorder(root); 

	return 0; 
}

بايثون:

class newNode(): 

	def __init__(self, data): 
		self.key = data 
		self.left = None
		self.right = None
		
# التنقل عبر مستويات الشجرة الثنائية

def inorder(temp): 

	if (not temp): 
		return

	inorder(temp.left) 
	print(temp.key,end = " ") 
	inorder(temp.right) 


# دالة لإدراج عنصر في الشجرة الثنائية

def insert(temp,key): 

	q = [] 
	q.append(temp) 
	
    # التنقل عبر مستويات الشجرة الثنائية بحثاً عن مكان فارغ
	while (len(q)): 
		temp = q[0] 
		q.pop(0) 

		if (not temp.left): 
			temp.left = newNode(key) 
			break
		else: 
			q.append(temp.left) 

		if (not temp.right): 
			temp.right = newNode(key) 
			break
		else: 
			q.append(temp.right) 
	
# اختبار الدوال السابقة
if __name__ == '__main__': 
	root = newNode(10) 
	root.left = newNode(11) 
	root.left.left = newNode(7) 
	root.right = newNode(9) 
	root.right.left = newNode(15) 
	root.right.right = newNode(8) 

	print("Inorder traversal before insertion:", end = " ") 
	inorder(root) 

	key = 12
	insert(root, key) 

	print() 
	print("Inorder traversal after insertion:", end = " ") 
	inorder(root)

جافا:

import java.util.LinkedList; 
import java.util.Queue; 
public class GFG { 
	
	// تمتلك العقدة في الشجرة الثنائية مفتاحًا ومؤشرًا إلى عقدة الابن اليسرى ومؤشرًا إلى عقدة الابن اليمنى
	static class Node { 
		int key; 
		Node left, right; 
		
		// دالة بانية
		Node(int key){ 
			this.key = key; 
			left = null; 
			right = null; 
		} 
	} 
	static Node root; 
	static Node temp = root; 
	
    // التنقل عبر مستويات الشجرة الثنائية
	
	static void inorder(Node temp) 
	{ 
		if (temp == null) 
			return; 
	
		inorder(temp.left); 
		System.out.print(temp.key+" "); 
		inorder(temp.right); 
	} 
	
	// دالة لإدراج عنصر في الشجرة الثنائية
	static void insert(Node temp, int key) 
	{ 
		Queue<Node> q = new LinkedList<Node>(); 
		q.add(temp); 
	
		// التنقل عبر مستويات الشجرة الثنائية بحثًا عن مكان فارغ
		while (!q.isEmpty()) { 
			temp = q.peek(); 
			q.remove(); 
	
			if (temp.left == null) { 
				temp.left = new Node(key); 
				break; 
			} else
				q.add(temp.left); 
	
			if (temp.right == null) { 
				temp.right = new Node(key); 
				break; 
			} else
				q.add(temp.right); 
		} 
	} 
	
	// اختبار الدوال السابقة
	public static void main(String args[]) 
	{ 
		root = new Node(10); 
		root.left = new Node(11); 
		root.left.left = new Node(7); 
		root.right = new Node(9); 
		root.right.left = new Node(15); 
		root.right.right = new Node(8); 
	
		System.out.print( "Inorder traversal before insertion:"); 
		inorder(root); 
	
		int key = 12; 
		insert(root, key); 
	
		System.out.print("\nInorder traversal after insertion:"); 
		inorder(root); 
	} 
}

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

Inorder traversal before insertion: 7 11 10 15 9 8
Inorder traversal after insertion: 7 11 12 10 15 9 8

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

تستخدم عملية التنقل البعدي في مسح الشجرة، وهي مفيدة كذلك في الحصول على تعبير اللاحقة 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)‎.

الطريقة الثانية: استخدام الأرتال

الخوارزمية

تتم زيارة كل عقدة في شجرة البيانات الثنائية، وتضاف العقد الأبناء لكلّ عقدة في رتل من نوع (يدخل أولًا يخرج أولًا FIFO)، وحسب الخطوات التالية:

ننشئ رتلًا فارغًا.
نبدأ من الجذر temp_node = root.
نستخدم حلقة تكرارية تؤدي العمليات التالية ما دام temp_node يمتلك أيّ قيمة عدا NULL:
1. نطبع بيانات العقدة المؤقتة temp_node->data.
2. ندرج أبناء العقدة المؤقتة (الابن الأيسر ثم الأيمن) في الرتل.
3. نزيل عقدة من الرتل ونسند قيمتها إلى المتغير temp_node.

التنفيذ

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

C++‎‎‎:

#include <iostream> 
#include <queue> 
using namespace std; 

// عقدة شجرة ثنائية
struct Node 
{ 
	int data; 
	struct Node *left, *right; 
}; 

// طريقة تكرارية للعثور على ارتفاع الشجرة الثنائية
void printLevelOrder(Node *root) 
{ 
	// الحالة الأساس
	if (root == NULL) return; 

	// إنشاء رتل فارغ لإجراء عملية التنقل عبر مستويات الشجرة
	queue<Node *> q; 

	// إدراج الجذر في الرتل وتهيئة الارتفاع
	q.push(root); 

	while (q.empty() == false) 
	{ 
		// طباة العنصر الأمامي في الرتل وإزالته من الرتل
		Node *node = q.front(); 
		cout << node->data << " "; 
		q.pop(); 

		// إدراج الابن الأيسر
		if (node->left != NULL) 
			q.push(node->left); 

		// إدراج الابن الأيمن
		if (node->right != NULL) 
			q.push(node->right); 
	} 
} 

// دالة مساعدة لإنشاء عقدة جديدة في الشجرة
Node* newNode(int data) 
{ 
	Node *temp = new Node; 
	temp->data = data; 
	temp->left = temp->right = NULL; 
	return temp; 
} 

// اختبار الدوال السابقة
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): 
	# الحالة الأساس
	if root is None: 
		return
	
	# إنشاء رتل فارغ لغرض إجراء عملية التنقل عبر المستويات
	queue = [] 

	# إدراج الجذر وتهيئة الارتفاع
	queue.append(root) 

	while(len(queue) > 0): 
		# طباعة العنصر الموجود في مقدمة الرتل وحذفه من الرتل
		print queue[0].data, 
		node = queue.pop(0) 

		# إدراج الابن الأيسر
		if node.left is not None: 
			queue.append(node.left) 

		# إدراج الابن الأيمن
		if node.right is not None: 
			queue.append(node.right) 

#اختبار الدوال السابقة
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)

جافا

/* استيراد أصناف جافا الداخلية المطلوبة لعمل البرنامج */
import java.util.Queue; 
import java.util.LinkedList; 

// صنف يمثّل عقدة في الشجرة الثنائية
class Node { 
	int data; 
	Node left, right; 

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

// يستخدم هذا الصنف لطباعة نتيجة عملية التنقل عبر مستويات الشجرة الثنائية
class BinaryTree { 

	Node root; 

	// تطبع الدالة العقد الموجودة في الشجرة الثنائية المعطاة
    // حسب المستوى باستخدام مصفوفة لإنشاء الرتل
	void printLevelOrder() 
	{ 
		Queue<Node> queue = new LinkedList<Node>(); 
		queue.add(root); 
		while (!queue.isEmpty()) 
		{ 

			// تحذف هذه الدالة الرأس الحالي
			Node tempNode = queue.poll(); 
			System.out.print(tempNode.data + " "); 

			// إدراج الابن الأيسر 
			if (tempNode.left != null) { 
				queue.add(tempNode.left); 
			} 

			// إدراج الابن الأيمن
			if (tempNode.right != null) { 
				queue.add(tempNode.right); 
			} 
		} 
	} 

	public static void main(String args[]) 
	{ 
		// إنشاء شجرة ثنائية وإدراج العقد فيها
		BinaryTree tree_level = new BinaryTree(); 
		tree_level.root = new Node(1); 
		tree_level.root.left = new Node(2); 
		tree_level.root.right = new Node(3); 
		tree_level.root.left.left = new Node(4); 
		tree_level.root.left.right = new Node(5); 

		System.out.println("Level order traversal of binary tree is - "); 
		tree_level.printLevelOrder(); 
	} 
}

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

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

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

يبلغ التعقيد الزمني لهذه الطريقة O(n)‎ وتمثّل n عدد العقد في الشجرة الثنائية.

المصادر

صفحة Binary Tree | Set 1 (Introduction)‎ في توثيق بنى المعطيات في موقع GeeksforGeeks.
صفحة Binary Tree | Set 2 (Properties)‎ في توثيق بنى المعطيات في موقع GeeksforGeeks.
صفحة Binary Tree | Set 3 (Types of Binary Tree)‎ في توثيق بنى المعطيات في موقع GeeksforGeeks.
صفحة Deletion in a Binary Tree في توثيق بنى المعطيات في موقع GeeksforGeeks.
صفحة Tree Traversals (Inorder, Preorder and Postorder)‎ في توثيق بنى المعطيات في موقع GeeksforGeeks.
صفحة Level Order Tree Traversal في توثيق بنى المعطيات في موقع GeeksforGeeks.

@@ سطر 390: / سطر 390: @@
 تسمّى شجرة البيانات الثنائية التي يكون لكل عقدة داخلية فيها عقدة ابن واحدة بالشجرة البيانية الثنائية المتحللة (المريضة). يوازي هذا النوع من أشجار البيانات الثنائية في أدائه القوائم المترابطة.
-<source lang="">      10
+<source lang="text">      10
        /