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