33. خوارزميات اجتياز الأشجار

الاجتياز هو عملية زيارة كل عُقدة في الشجرة مرة واحدة بالضبط. يتم تعريف عمليات الاجتياز الرئيسية الثلاثة للعمق أولاً (depth-first) حسب وقت زيارة عُقدة الجذر بالنسبة لأبنائها.

لتكن N هي العُقدة (Node)، و L هي الشجرة الفرعية اليسرى (Left Subtree)، و R هي الشجرة الفرعية اليمنى (Right Subtree).

1. اجتياز Inorder (L N R)

• زيارة الشجرة الفرعية اليسرى، ثم زيارة العُقدة، ثم زيارة الشجرة الفرعية اليمنى.
• النتيجة: بالنسبة لـ BST، ينتج عن اجتياز Inorder العناصر بالترتيب المفرز.

2. اجتياز Preorder (N L R)

• زيارة العُقدة، ثم الشجرة الفرعية اليسرى، ثم الشجرة الفرعية اليمنى.
• النتيجة: يستخدم لإنشاء نسخة من الشجرة أو للحصول على التعبير البادئ (prefix expression) للشجرة.

3. اجتياز Postorder (L R N)

• زيارة الشجرة الفرعية اليسرى، ثم الشجرة الفرعية اليمنى، ثم زيارة العُقدة.
• النتيجة: يستخدم لحذف الشجرة (يجب حذف الأبناء قبل حذف الأب) أو للتعبيرات اللاحقة (postfix expressions).