اجتياز الشجرة الثنائية

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

تشمل أساليب الاجتياز الشائعة للأشجار الثنائية: الاجتياز بالمستويات، والاجتياز المسبق، والاجتياز الوسطي، والاجتياز اللاحق.

الاجتياز بالمستويات

كما يوضح الشكل أدناه، فإن الاجتياز بالمستويات (level-order traversal) يجتاز الشجرة الثنائية من الأعلى إلى الأسفل، طبقةً طبقة. وفي كل مستوى، يزور العقد من اليسار إلى اليمين.

الاجتياز بالمستويات هو في جوهره الاجتياز بالعرض أولاً (breadth-first traversal)، ويُعرف أيضاً باسم البحث بالعرض أولاً (BFS)، حيث يتقدم نحو الخارج مستوى تلو الآخر.

تنفيذ الشيفرة

يُنفَّذ الاجتياز بالعرض أولاً عادةً بمساعدة «الطابور». فالطابور يتبع قاعدة «أول ما يدخل يخرج أولاً»، بينما يتبع الاجتياز بالعرض أولاً قاعدة «التقدم طبقةً طبقة»؛ والفكرتان الكامنتان وراءهما متطابقتان. وشيفرة التنفيذ كما يلي:

/* الاجتياز بالمستويات */
func levelOrder(root *TreeNode) []any {
	// هيّئ الطابور، وأضف عقدة الجذر
	queue := list.New()
	queue.PushBack(root)
	// هيّئ slice لحفظ تسلسل الاجتياز
	nums := make([]any, 0)
	for queue.Len() > 0 {
		// أخرج من الطابور
		node := queue.Remove(queue.Front()).(*TreeNode)
		// احفظ قيمة العقدة
		nums = append(nums, node.Val)
		if node.Left != nil {
			// أدخل عقدة الابن الأيسر إلى الطابور
			queue.PushBack(node.Left)
		}
		if node.Right != nil {
			// أدخل عقدة الابن الأيمن إلى الطابور
			queue.PushBack(node.Right)
		}
	}
	return nums
}

/* الاجتياز بالمستويات */
function levelOrder(root: TreeNode | null): number[] {
    // هيّئ الطابور، وأضف عقدة الجذر
    const queue = [root];
    // هيّئ قائمة لحفظ تسلسل الاجتياز
    const list: number[] = [];
    while (queue.length) {
        let node = queue.shift() as TreeNode; // أخرج من الطابور
        list.push(node.val); // احفظ قيمة العقدة
        if (node.left) {
            queue.push(node.left); // أدخل عقدة الابن الأيسر إلى الطابور
        }
        if (node.right) {
            queue.push(node.right); // أدخل عقدة الابن الأيمن إلى الطابور
        }
    }
    return list;
}

تحليل التعقيد

• التعقيد الزمني هو $O(n)$: تُزار جميع العقد مرة واحدة، مستخدماً زمن $O(n)$، حيث $n$ هو عدد العقد.
• التعقيد المكاني هو $O(n)$: في أسوأ الحالات، أي في شجرة ثنائية تامة، وقبل الاجتياز إلى المستوى السفلي، يحتوي الطابور في الوقت نفسه على $(n + 1) / 2$ عقدة على الأكثر، شاغلاً مساحة $O(n)$.

الاجتياز المسبق والوسطي واللاحق

وبالمقابل، تنتمي الاجتيازات المسبق والوسطي واللاحق جميعها إلى الاجتياز بالعمق أولاً (depth-first traversal)، ويُعرف أيضاً باسم البحث بالعمق أولاً (DFS)، حيث يتعمق قدر الإمكان ثم يتراجع.

ويوضح الشكل أدناه كيفية عمل الاجتياز بالعمق أولاً على شجرة ثنائية. الاجتياز بالعمق أولاً أشبه بـ«المشي» حول محيط الشجرة الثنائية بأكملها، حيث نصادف عند كل عقدة ثلاثة مواضع تقابل الاجتياز المسبق والوسطي واللاحق.

تنفيذ الشيفرة

يُنفَّذ البحث بالعمق أولاً عادةً استناداً إلى التعاود:

/* الاجتياز اللاحق */
func postOrder(node *TreeNode) {
	if node == nil {
		return
	}
	// أولوية الزيارة: الشجرة الفرعية اليسرى -> الشجرة الفرعية اليمنى -> عقدة الجذر
	postOrder(node.Left)
	postOrder(node.Right)
	nums = append(nums, node.Val)
}

/* الاجتياز اللاحق */
function postOrder(root: TreeNode | null): void {
    if (root === null) {
        return;
    }
    // أولوية الزيارة: الشجرة الفرعية اليسرى -> الشجرة الفرعية اليمنى -> عقدة الجذر
    postOrder(root.left);
    postOrder(root.right);
    list.push(root.val);
}

يوضح الشكل أدناه العملية التعاودية للاجتياز المسبق لشجرة ثنائية، ويمكن تقسيمها إلى مرحلتين متعاكستين: «النزول» و«العودة».

1. «النزول» يعني إجراء استدعاء تعاودي جديد، يزور البرنامج خلاله العقدة التالية.
2. «العودة» تعني عودة استدعاء الدالة، ما يشير إلى أن العقدة الحالية قد اكتملت معالجتها.

تحليل التعقيد

• التعقيد الزمني هو $O(n)$: تُزار جميع العقد مرة واحدة، مستخدماً زمن $O(n)$.
• التعقيد المكاني هو $O(n)$: في أسوأ الحالات، أي عندما تتدهور الشجرة إلى قائمة مترابطة، يبلغ عمق التعاود $n$، ويشغل النظام مساحة إطار مكدس $O(n)$.