
_START_ARTICLE_
شجرة (بنية بيانات)
_START_PARAGRAPH_
في علم الحاسوب, الشجرة هي هيكل بيانات واسع الاستخدام يحاكي شكل شجرة هرمية مع مجموعة من الرؤوس المرتبطة._NEWLINE_في علم رياضيات، هي شجرة متصلة متجهة: رسم بياني متصل عديم الحلقات حيث لكل رأس يوجد صفر أو أكثر من الرؤوس الأبناء وأب واحد على الأكثر. أيضا، لأبناء رأس ما يوجد ترتيبا محددا.
_START_SECTION_
مصطلحات
_START_PARAGRAPH_
الرأس هو بنية تمتلك قيمة، شرط، أو تمثل هيكل بيانات منفصل (الذي يمكن أن يكون شجرة بحد ذاته). لكل رأس يوجد صفر أو أكثر من الرؤوس الأبناء، التي تكون تحته في الشجرة (بالإجماع، الشجر يرسم لأسفل). الرأس الذي يمتلك ابنا يسمى رأس أب لذلك الرأس, (أو سلفه، أو سابقه). للرأس يوجد على الأكثر أب واحد._NEWLINE_رأس داخلي أو رأس باطني هو أي رأس من الشجرة بحيث يمتلك رؤوس أبناء. وبالمثل, رأس خارجي (أيضا يطلع عليه ورقة أو رأس طرفي) هو أي رأس بحيث لا يمتلك أية رؤوس أبناء._NEWLINE_يطلق على الرأس الأعلى في شجرة الجذر. كونه الرأس الأعلى، الجذر لا يمتلك آباء. هو الرأس الذي عادة ما تبدأ منه العمليات (بالرغم من أن بعض الخوارزميات تبدأ من الأوراق). يمكن الوصول لكل الرؤوس الأخرى منه (الجذر) باتباع الحواف أو الروابط. (بالتعريف الرسمي، كل مسار كهذا هو فريد). في الرسوم البيانية، يرسم عادة في الأعلى. في بعض الأشجار مثل الأكوام، للجذر هناك خصائص مميزة. كل رأس في الشجرة يعد جذرا للشجرة الفرعية المبتدئة به._NEWLINE_شجرة حرة هي الشجرة التي ليس لها جذر._NEWLINE_ارتفاع رأس هو طول أطول مسار سفلي لورقة من ذلك الرأس. ارتفاع الجذر هو ارتفاع الشجرة. عمق رأس هو أطول مسار للجذر. هناك حاجة لهذه الخاصية في معالجة العديد من الأشجار المتزنة، شجرة AVL على وجه الخصوص. بالإجماع، القيمة 1- تعطى لشجرة فرعية بدون رؤوس، حيث يعطى الصفر شجرة فرعية برأس واحد._NEWLINE_شجرة فرعية لشجرة ج هي شجرة تتكون من رأس في الشجرة ج وكل أحفاده في ج. (هذا تعريف مختلف عن التعريف الرسمي للشجرة الفرعية في نظرية المخططات). شجرة فرعية التي تبدأ من الجذر هي الشجرة الكاملة؛ الشجرة الفرعية التي تبدأ من أي رأس اخر تسمى شجرة فرعية حقيقية (مشابها لمصطلح المجموعة الجزئية الحقيقية).
_START_SECTION_
تمثيل
_START_PARAGRAPH_
هناك العديد من الطرق لتمثيل الأشجار. التمثيلات العامة تمثل الرؤوس كسجلات مخصصة بشكل حيوي لعائلة ما مع مؤشرات لابنائهم، آبائهم، أو كلاهما، أو كعناصر في مصفوفة مع علاقات بين بعضهم البعض محددة حسب موقعهم في المصفوفة (مثل الكومة الثنائية).
_START_SECTION_
الشجر والرسوم البيانية
_START_PARAGRAPH_
هيكل بيانات الشجرة يمكن أن يعمم ليمثل رسوما بيانية متصلة عن طريق إزالة التقييدات بأنه للرأس (أب) واحد على الأكثر، وبأن الحلقات غير مسموحة. والزوايا تبقى معتبرة تجريديا أزواج من الرؤوس، مع ذلك، والمصطلحات أب وابن عادة ما يتم استبدالهم بمصطلحات أخرى (على سبيل المثال، مصدر وهدف)، وتوجد العديد من أساليب التنفيد، مثل قائمة الجوار.
_START_SECTION_
العلاقة مع الشجر في نظرية المخططات
_START_PARAGRAPH_
في نظرية المخططات، الشجرة هي رسم بياني متصل عديم الحلقات؛ إلا إذا نص غير ذلك، الشجر والرسوم البيانية غير متصلة.
_START_SECTION_
طرق الاجتياز
_START_PARAGRAPH_
المرور خلال عناصر الشجرة، عن طريق العلاقات بين الآباء والأبناء، يسمى اجتياز الشجرة. عادة، بالإمكان تنفيذ عملية ما عندما يصل المؤشر إلى رأس معين. اجتياز الذي يتم به المرور على كل أب قبل أبنائه يسمى اجتياز بترتيب خلفي؛ اجتياز الذي يتم به المرور على كل أب قبل أبنائه يسمى اجتياز بترتيب أمامي؛ اجتياز الذي يتم به المرور على الشجرة الفرعية اليسرى ثم الرأس نفسه يسمى اجيازا مرتبا. (الحالة الأخيرة، تشير إلى شجرتين فرعيتين بالضبط، شجرة فرعية يمني وشجرة فرعية يسرى، يفترض بالتحديد شجرة ثنائية.)