هياكل البيانات : الأشجار الثنائية Binary Trees

بسم الله الرحمن الرحيم

السلام عليكم ورحمة الله وبركاته

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

طريقة أخرى احفظ مجموعة البيانات وهي أبسط طريقة والتي تتمثل في المصفوفات سواء المصفوفات العادية أو مصفوفات القوائم.

في هذا الدرس سنتعرف على أحد أفضل الطرق في حفظ البيانات والتي تعتبر من الأفضل من ناحية العرض أو البحث وغيرها

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

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

 

ماذا نقصد بالأشجار الثنائية (Binary Trees):

هو نوع من أنواع تمثيل البيانات ويتكون من مكونين أساسيين هما العقد (Nodes) و الأقصان (Arcs). 

عندما نقوم بتمثيل هذه الشجرة فإننا نقلب مفهومها فيكون الجذر (Root) في الأعلى والأقصان في الأسفل.

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

هناك بعض المصطلحات التي يجب أن نتعرف عليها قبل الشروع الى صلب الموضوع:

- العقد (Node): وهو كل عنصر موجود في الشجرة، وهو المكان الذي يتم حفظ البيانات داخله.

أنواع خاصة من العقد (Nodes):

               - الجذر (Root): وهو العنصر الذي ليس لديه والد أي أنه أعلى عنصر في الشجرة. وكل شجرة تحتوي على جذر واحد فقط.

               - الأوراق (Leaves): وهذه هي مجموعة العقد التي ليس لديها أي أولاد. أي أنها في طرف الشجرة.

- القصن (Arc): هو الرابط الذي يربط العقد بين بعضها وهو ذي اتجاه واحد من الأعلى الى الأسفل.

 

يختلف مفهوم الشجرة الثنائية Binary Tree  حيث أن بعضها لا تحقق بعض الشروط مما يؤدي بها الى أن تكون عبارة عن قائمة عادية

لكن الأنواع الأخرى تحتوي على شروط التي تجعلها شجرة فعالة بأكبر قدر ممكن و تسمى بـ Binary Search Tree وهذا اساس جميع ما يلي.

 

تمثيل الشجرة الثنائية (Binayr Tree):

١. عن طريق المصفوفات (ArrayLists): وهذه الطريقة لديها مشاكلها كما ذكراناها سابقاً.

٢. عن طريق القوائم الثنائية (Linked lists): وهذه هي الطريق الأمثل لتمثيل الشجر.

 

أكواد الشجرة الثنائية (Binary Tree):

أ- إنشاء كلاس خاص بالعقد (Nodes) :

هذا الكلاس يسمى بـ BSTNode وهو كالتالي:

public class BSTNode {
	protected int key;

	protected BSTNode right, left; 

	public BSTNode(){
		this(0);
	}

	public BSTNode(int k){
		this(k, null, null);
	}
	
	public BSTNode(int k, BSTNode r, BSTNode l){
		this.key = k;
		this.right = r;
		this.left = l;
	}
	public void addRight(BSTNode r){
		this.right = r;
	}
	
	public void addLeft(BSTNode l){
		this.left = l;
	}
}

هذا الكلاس يحتوي على المتغيرات التالية:

- Key: وهو من نوع و int وهو المكان الذي يتم حفظ البيانات داخله.

 - right & left: وهما القصنان (Arcs) والذان يربطان العقد بأبنيه اليمين والشمال.

كما نرى فإننا نستطيع إنشاء عنصر من هذا الكلاس سواء كان في بيانات أو لا. لديه أولاد أولا.

كما وأنه لدينا ميثودين نستخدمها لإضافة ابن لليمين أو لليسار.

 

ب- انشاء كلاس الشجرة الثنائية (Binary Search Tree):

public class BST {
	private BSTNode root = null; 
	
	public BST(){
		
	}
	
	public void clear(){
		this.root =null;
	} 

	
	public boolean isEmpty(){
		return root == null;
	}
	
	
	public void visit(BSTNode n){
		System.out.println(n.key + " ");
	}
}

هنا نقوم بانشاء الهيكلة الأساسية للشجرة ويحتوي على التالي:

- root: الجذر وهو رأس الشجرة والوحيد الذي يربطنا بكامل عناصر الشكرة. وفي بداية انشاء الشجرة يكون الجذر فاضي.

لدينا الكثير من الميثود لكن سنذكر هنا الأشياء الأساسية ونترك الباقي للدرس القادم بحيث أنها تحتوي على الكثير من التفاصيل:

* clear(): تستخدم لتفريغ الشجرة من البيانات؛ وبما أن الجذر هو الرابط الوحيد لعناصر الشجرة فإن حذف الجذر سيؤدي الى حذف الشجرة كلها.

*isEmpty(): وستخدم للاستعمال اذا ما كانت الشجرة خالية أو لا. ترسل true في حال كانت الشجرة خالية.

*visit(): تستخدم لطباعة قيمة القيمة داخل العقد المرسل.

 

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

 

اسأل الله العلي العظيم بأني وفقت لاصال المعلومة بابسط طريقة

 

في حفظ الله

كلمات دليلية: