شجرة (بنية بيانات)

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

رأس داخلي أو رأس باطني هو أي رأس من الشجرة بحيث يمتلك رؤوس أبناء. وبالمثل, رأس خارجي (أيضا يطلع عليه ورقة أو رأس طرفي) هو أي رأس بحيث لا يمتلك أية رؤوس أبناء.

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

شجرة حرة هي الشجرة التي ليس لها جذر.

ارتفاع رأس هو طول أطول مسار سفلي لورقة من ذلك الرأس. ارتفاع الجذر هو ارتفاع الشجرة. عمق رأس هو أطول مسار للجذر. هناك حاجة لهذه الخاصية في معالجة العديد من الأشجار المتزنة، شجرة AVL على وجه الخصوص. بالإجماع، القيمة 1- تعطى لشجرة فرعية بدون رؤوس، حيث يعطى الصفر شجرة فرعية برأس واحد.

شجرة فرعية لشجرة ج هي شجرة تتكون من رأس في الشجرة ج وكل أحفاده في ج. (هذا تعريف مختلف عن التعريف الرسمي للشجرة الفرعية في نظرية المخططات[1]). شجرة فرعية التي تبدأ من الجذر هي الشجرة الكاملة؛ الشجرة الفرعية التي تبدأ من أي رأس اخر تسمى شجرة فرعية حقيقية (مشابها لمصطلح المجموعة الجزئية الحقيقية).

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

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

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

• تعداد كافة العناصر
• تعداد جزء من شجرة
• البحث عن عنصر
• إضافة عنصر جديد في موقع معين على الشجرة
• حذف عنصر
• إزالة مقطع كامل من شجرة (تسمى التقليم)
• إضافة قسم كامل لشجرة (تسمى التطعيم)
• العثور على الجذر لأي رأس

• التلاعب الهرمي بالبيانات
• جعل المعلومات سهلة البحث (انظر شجرة بحث ثنائية)
• التلاعب بقوائم الترتيب من البيانات
• خوارزميات التوجيه

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

• Donald Knuth. The Art of Computer Programming: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.3: Trees, pp. 308–423.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithm, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 10.4: Representing rooted trees, pp. 214–217. Chapters 12–14 (Binary Search Trees, Red-Black Trees, Augmenting Data Structures), pp. 253–320.

قالب:بنية بيانات

• بوابة برمجة الحاسوب
• بوابة علم الحاسوب

في كومنز صور وملفات عن: شجرة