الأشجار

من ويكي الهندسة المعلوماتية
اذهب إلى: تصفح، ابحث

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

  • عقد (nodes)
  • روابط بين تلك العقد (links)

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

تعاريف ومفاهيم

جذر الشجرة

ونسميه أيضاً رأس الشجرة (root) العقدة التي ليس لها أب.

العقد الخارجية External Nodes

(الأوراق) (leaves) وهي العقد التي ليس لها أبناء .

External Nodes = Leaves ={ hasn't any child }


العقد الداخلية Internal Nodes

هي العقد التي لها أبناء .

Internal Nodes ={ has one child at least }

العقدة الأب

العقدة الأب بالنسبة لعقدة معينة هي العقدة التي تتفرع منها تلك العقدة مباشرة.

العقدة السلف

العقدة السلف بالنسبة لعقدة معينة هي العقدة الأب أو أب الأب أو التي فوقها.....

العقدة الأخ

العقدة الأخ لعقدة معينة هي العقدة التي لها نفس أب تلك العقدة.

العقدة الحفيد

هي الحفيد لعقدة معينة هي العقدة المتفرعة من أحد أبنائها أو أحد أبناء أبنائها وهكذا....

الطريق path

الطريق path بين عقدتين هو عدد الوصلات بين هاتين العقدتين .

ارتفاع عقدة

هو طول الطريق path بين الجذر والعقدة .

الشجرة الجزئية

نقول إن شجرة جزئية من إذا وجدت في مكان ما من ونكتب

ارتفاع الشجرة
طول أطول طريق يصل بين عقدة من الشجرة، وبين جذر هذه الشجرة. أو  : ( هو أطول ارتفاع عقدة في هذه الشجرة )
حجم الشجرة
عدد عقدها

درجة الشجرة أو رتبتها

هو العدد الأعظمي لأبناء أي عقدة. ويمكن ألا يكون للشجرة درجة (أي عدد الأبناء غير محدود). وأشهر رتبة هي الرتبة الثانية (الأشجار الثنائية).

مسافة التجول

is a node in the Tree

مسافة التجول=مسافة التجول الخارجي+مسافة التجول الداخلي

حيث : is a leaf in Tree

is an internal node in Tree

التعريف العودي للشجرة

يمكن تعريف الشجرة T عودياً كما يلي :

T شجرة -->

  • إما T=0 {لا تحوي أي عقدة}.
  • أو T تحوي عنصر (هو الجذر) يرتبط به عدد من العناصر كل منها هو جذر لـ (شجرة جزئية)، قد يكون هذا العدد معدوم فنحصل على شجرة وحيدة العنصر أو غير معدوم.

تنفيذ الأشجار في الحواسيب

يمكن تمثيل الأشجار باستخدام المؤشرات والمصفوفات، ولكن الطريقة الأكثر شيوعاً وقدرة على تمثيل الأشجار هي المؤشرات:

تمثيل الأشجار باستخدام المؤشرات:

هنا تكون العقدة عبارة عن Object من كلاس معين. تحوي عادة على مفتاح key يميزها عن غيرها، أو أي معلومات أخرى. إضافة لذلك تحوي على مؤشرات إلى الأبناء. وقد تحوي على مؤش إلى العقدة الأب لها، ولكن هذا ليس ضرورياً حسب الاستخدام والحاجة.

إذا كان الابن غير موجود فإن المؤشر الخاص به يكون فارغاً، أي قيمته NULL.

إذا كان الأب غير موجود فإن المؤشر الخاص به يكون فارغاً أيضاً وقيمته NULL، علماً بأن هذه الحالة تصادف فقط في حال كانت هذه العقدة هي الجذر Root.


ويوجد طرق برمجية عديدة لتمثيل الأبناء باستخدام المؤشرات:


  • مؤشر مستقل لكل ابن

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


مثال لكلاس العقدة في C++

class Node
{
public:
	int Key;
	// Other members
	Node* Child_1, Child_2, Child_3, ..... Child_k;
	Node* Parent;	// Optional
};


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

  • مصفوفة مؤشرات

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


مثال لكلاس العقدة في C++

class Node
{
public:
	int Key;
	// Other members
	Node** ChildArray;
	Node* Parent;	// Optional
};


  • مؤشران فقط!
MIT Trees Child Sibling.png

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

مثال لكلاس العقدة في C++

class Node
{
public:
	int Key;
	// Other members;
	Node* Left_Child, Next_Sibling;
	Node* Parent;	// Optional
};