กระบวนการทำงาน สำหรับการเยี่ยม ทุกจุด อย่างมีระบบ ของ ต้นไม้รากแบบอันดับ เรียกว่า 
อัลกอริทึมการแวะผ่าน
	(Procedures for systematically visiting every vertex of an ordered rooted tree are called
traversal algorithm.)
	เราจะอธิบาย อัลกอริทึม เช่นนี้ ซึ่งใช้ร่วมกันมากที่สุด  3 ชนิด คือ 

	
 การแวะผ่านแบบก่อนลำดับ (preorder traversal)
    
 การแวะผ่านแบบตามลำดับ (inorder traversal)
    
 การแวะผ่านแบบหลังลำดับ (postorder traversal)

บทนิยาม 1 ให้ T เป็นต้นไม้รากแบบอันดับ มีราก ชื่อ r ถ้า T มีการเพียงจุดเดียวเท่านั้น r คือ การแวะผ่าน
แบบก่อนลำดับ (postorder traversal) ของ T กรณีอื่นๆ สมมติว่า T1 , T2 ,  , Tn เป็นเซตย่อยของ  r จาก
ซ้ายไปขวา ใน  T  การแวะผ่านแบบก่อนลำดับ เริ่มต้นโดยการเยี่ยม  r  ต่อไป แวะผ่าน T1 แบบก่อนลำดับ 
จากนั้น แวะผ่าน T2 แบบก่อนลำดับ เช่นนี้เรื่อยไป จนกระทั่ง Tn ถูกแวะผ่าน แบบก่อนลำดับ





ขั้นที่ 2 
เยี่ยม T1 
แบบก่อนลำดับ


ขั้นที่ 3 
เยี่ยม T2 
แบบก่อนลำดับ


ขั้นที่ n+1 
เยี่ยม Tn 
แบบก่อนลำดับ


รูปที่ 2 การแวะผ่านแบบก่อนลำดับ (Preorder Traversal)

ตัวอย่าง 2 จงหา อันดับของการ และผ่านแบบก่อนลำดับ เยี่ยมจุดต่างๆ ในต้นไม้รากแบบอันดับชื่อ T ในรูปที่ 3
	ผลเฉลย ขั้นตอนต่างๆ ของ การแวะผ่านแบบก่อนลำดับ ของ T แสดงให้เห็นในรูปที่ 4 เราแวะผ่าน
	ต้นไม้ T แบบก่อนลำดับ โดยสิ่งแรก คือ ชื่อราก a ตามด้วยรายการแสดงแบบก่อนลำดับ ของต้นไม้
	ส่วนย่อยที่มีรากเป็น b รายการแสดงแบบก่อนลำดับ ของต้นไม้ส่วนย่อยด้วยราก c ( ซึ่งมีแค่ c จุด
	เดียว) และรายการแบบก่อนลำดับของต้นไม้ส่วนย่อย ด้วยราก d 


รูปที่ 3 ต้นไม้รากแบบอันดับ Tree

	รายการแสดงแบบก่อนลำดับ ของ ต้นไม้ส่วนย่อย ด้วยราก b เริ่มต้นด้วย ชื่อ b จากนั้นจุดต่างๆ
ของต้นไม้ส่วนย่อย ด้วยราก e แบบก่อนลำดับ แล้ว ต้นไม้ส่วนย่อย ด้วยราก f แบบก่อนลำดับ (มีเพียงจุด f)
	รายการแสดงแบบก่อนลำดับ ของ ต้นไม้ส่วนย่อย ด้วยราก d เริ่มต้นด้วย ชื่อ d ตามด้วยรายการ
แสดงแบบก่อนลำดับ ของต้นไม้ส่วนย่อยด้วยราก g ตามด้วยต้นไม้ส่วนย่อยด้วยราก h (มีเพียงจุด h)ตามด้วย 
ต้นไม้ส่วนย่อย ด้วยรากii (มีเพียงจุด i)
 	รายการแสดงแบบก่อนลำดับ ของ ต้นไม้ส่วนย่อย ด้วยราก e เริ่มต้นด้วย ชื่อ e ตามด้วยรายการ
แสดงแบบก่อนลำดับ ของต้นไม้ส่วนย่อย ด้วยราก j (มีเพียงจุด j) ตามด้วย รายการแสดงแบบก่อนอันดับ ของ
ต้นไม้ส่วนย่อย ด้วยราก k
	รายการแสดงแบบก่อนลำดับ ของต้นไม้ส่วนย่อย ด้วย ราก  g  คือชื่อ  g  ตามด้วย 1 ตามด้วย m 
รายการแสดงแบบก่อนลำดับ ของต้นไม้ส่วนย่อย ด้วยราก k คือ k, n, o, p 
	เพราะฉะนั้น การแวะผ่านแบบก่อนลำดับ ของ T คือ
	a, b, e, j, k, n, o, p, f, c, d, g, l, m, h, i


Preorder traversal: Visit root, visit subtrees left to right






FIGURE 4 The Preorder Traversal of T



บทนิยาม 2 ให้ T เป็นต้นไม้ราแบบอันดับ มีรากเป็น r ถ้า T มี r เพียงจุดเดียว ดังนั้น r คือ การแวะผ่านแบบ
ตามลำดับ (inorder traversal) ของ T กรณีอื่นๆ สมมติว่า T1 , T2 ,  , Tn เป็นต้นไม้ส่วนย่อย ที่ r จาก ซ้าย
ไปขวา การแวะผ่านแบบตามลำดับ เริ่มต้นด้วย การแวะผ่าน  T1  แบบตามลำดับ  จากนั้นเยี่ยมจุด r ต่อไป 
แวะผ่าน  T2  แบบตามลำดับ จากนั้น  T3  แบบตามลำดับ เช่นนี้เรื่อยไป และสุดท้าย แวะผ่าน Tn แบบตาม
ลำดับ ในรูปที่ 5 แสดงให้เห็นว่า การแวะผ่านแบบตามลำดับ ทำจนสำเร็จได้อย่างไร

ตัวอย่าง 3 จงหาอันดับของการแวะผ่านแบบตามลำดับ เยี่ยมจุดต่างๆ ของต้นไม้รากแบบอันดับ T ในรูปที่ 3 




ขั้นที่ 1 
เยี่ยม T1 
แบบตามลำดับ


ขั้นที่ 3 
เยี่ยม T2 
แบบตามลำดับ


ขั้นที่ n+1 
เยี่ยม Tn 
แบบตามลำดับ


รูปที่ 5 การแวะผ่านแบบตามลำดับ (Inorder Traversal)

	ผลเฉลย ขั้นตอนต่างๆ ของการแวะผ่านแบบตามลำดับ ของต้นไม้รากแบบอันดับ T แสดง
ให้เห็นในรูปที่ 6 
	การแวะผ่านแบบตามลำดับ เริ่มต้น การแวะผ่านแบบตามลำดับ ของต้นไม้ส่วนย่อย ด้วย
ราก b จากนั้น ราก a ต่อด้วยรายการแสดงแบบตามลำดับ ของต้นไม้ส่วนย่อย ด้วยราก c ซึ่งมีเพียงจุด
c และรายการแสดงแบบตามลำดับ ของต้นไม้ส่วนย่อย d ด้วยราก d 
	รายการแสดงแบบตามลำดับ ของต้นไม้ส่วนย่อย ด้วยราก b เริ่มต้น ด้วยรายการแสดงแบบ
ตามลำดับ ของ ต้นไม้ส่วนย่อย ด้วยราก e ราก b และ f
	รายการแสดงแบบตามลำดับ ของ ต้นไม้ส่วนย่อย ด้วยราก d เริ่มต้นด้วย รายการแสดงแบบ
ตามลำดับ ของ ต้นไม้ส่วนย่อย ด้วยราก g ตามด้วย ราก d และตามด้วย h, ตามด้วย i
  	รายการแสดงแบบตามลำดับ ของ ต้นไม้ส่วนย่อย ด้วยราก e คือ j ตามด้วย ราก e ตามด้วย
รายการแสดงแบบตามลำดับ ของ ต้นไม้ส่วนย่อย ด้วยราก k 
	รายการแสดงแบบตามลำดับ ของ ต้นไม้ส่วนย่อย ด้วยราก g คือ l, g, m
	รายการแสดงแบบตามลำดับ ของ ต้นไม้ส่วนย่อย ด้วยราก k คือ n, k, o, p
	เพราะฉะนั้น รายการแสดงแบบตามลำดับ ของ ต้นไม้รากแบบอันดับ คือ 
j, e, n, k, o, p, b, f, a, c, l, g, d, h, i 

T


Inorder traversal: Visit leftmost subtree, visit root, visit other subtrees left to right





รูปที่ 6 การแวะผ่านแบบตามลำดับ ของต้นไม้ T


บทนิยาม 3 ให้ T เป็นต้นไม้รากแบบอันดับ มีรากเป็น r ถ้า T มีเพียง r เพียงจุดเดียว จะได้ว่า r คือ การ
แวะผ่านแบบหลังลำดับ (postorder traversal) ของ  T  กรณีอื่นๆ สมมติว่า  T1 , T2 ,  , Tn คือ ต้นไม้
ส่วนย่อย ที่ r จากซ้ายไปขวา การแวะผ่านแบบหลังลำดับ เช่นนี้เรื่อยไป จนถึง Tn แบบหลังลำดับ ทำให้
สำเร็จได้อย่างไร




ขั้นที่ 1 :
เยี่ยม T1 
แบบหลังลำดับ


ขั้นที่ 2 :
เยี่ยม T2 
แบบหลังลำดับ


ขั้นที่ n :
เยี่ยม Tn 
แบบหลังลำดับ


รูปที่ 7 การแวะผ่านแบบหลังลำดับ (Postorder Traversal)


ตัวอย่าง 4 จงหา อันดับ ของการแวะผ่านแบบหลังลำดับ เยี่ยมจุดต่างๆ ของ ต้นไม้รากแบบอันดับ T ซึ่ง
แสดงในรูปที่ 3
	ผลเฉลย ขั้นตอนต่างๆ ของ การแวะผ่านแบบหลังลำดับ ของ ต้นไม้รากแบบอันดับ T แสดง
ให้เห็นในรูปที่ 8 การแวะผ่านแบบหลังลำดับ เริ่มต้นด้วย การแวะผ่านแบบหลังลำดับ ของ ต้นไม้ส่วนย่อย
ด้วยราก b เริ่มต้นด้วย การแวะผ่านแบบหลังลำดับ ของ ต้นไม้ส่วนย่อย ด้วยราก c ซึ่งมีเพียงจุด c ตาม
ด้วย การแวะผ่านแบบหลังลำดับ ของ ต้นไม้ส่วนย่อย ด้วยราก d และ สุดท้าย ตามด้วย ราก a
	การแวะผ่านแบบหลังลำดับ ของ ต้นไม้ส่วนย่อย ด้วยราก b เริ่มต้นด้วย การแวะผ่านแบบ
หลังลำดับ ของ ต้นไม้ส่วนย่อย ด้วยราก e ตามด้วย f ตามด้วยราก b
	การแวะผ่านแบบหลังลำดับ ของ ต้นไม้ราก ด้วยราก d เริ่มต้นด้วย การแวะผ่านแบบหลัง
ลำดับ ของ ต้นไม้ส่วนย่อย ด้วยราก g ตามด้วย h ตามด้วยii และตามด้วยราก d
	การแวะผ่านแบบหลังลำดับ ของ ต้นไม้ส่วนย่อย ด้วยราก e เริ่มต้นด้วย j ตามด้วย การแวะ
ผ่านแบบหลังลำดับ ของ ต้นไม้ส่วนย่อย ด้วยราก k ตามด้วย ราก e
	การแวะผ่านแบบหลังลำดับ ของ ต้นไม้ส่วนย่อย ด้วยราก g คือ l, m, g
	การแวะผ่านแบบหลังลำดับ ของ ต้นไม้ส่วนย่อย ด้วยราก k คือ n, o, p, k
	เพราะฉะนั้น การแวะผ่านแบบหลังลำดับ ของ ต้นไม้ T คือ j, n, o, p, k, e, f, b, c, l, m, g, h, I, d, a

T


Postorder traversal: Visit subtrees left to right; visit root





รูปที่ 8 การแวะผ่านแบบหลังลำดับของ T


	มีหลายวิธีง่ายๆ เพื่อแสดงรายการ จุดต่างๆ ของต้นไม้รากแบบอันดับ ในลักษณะ ก่อนลำดับ
ตามลำดับ และหลังลำดับ ในการทำสิ่งนี้ ขั้นแรก วาดรูป เส้นโค้ง รอบ ต้นไม้ราแบบอันดับ เริ่มต้นที่ราก 
เคลื่อนย้ายไปตามด้านต่างๆ เช่นที่แสดงให้เห็นในรูปที่ 9 เราสามารถเขียนรายการจุดต่างๆ แบบก่อนลำดับ 
โดย แสดงรายการ แต่ละจุด ในครั้งแรกที่เส้นโค้งนี้ ผ่านจุดนั้น และ รายการแสดง แต่ละจุด ของจุดภายใน 
ในครั้งที่ ซึ่ง เส้นโค้งผ่านจุดนั้น เราสามารถเขียนรายการจุดต่างๆ แบบหลังลำดับ โดย รายการแสดงจุดใน
ครั้งหลังสุด ที่ มันผ่าน บนทางย้อนกลับ ไป จุด ถึง จุดแม่ (parent) ของมัน เมื่อ สิ่งนี้กระทำเสร็จสิ้น ในรูปที่ 9 
จะพบว่า


รูปที่ 9 วิธีลัด สำหรับการแวะผ่าน ต้นไม้รากแบบอันดับ แบบก่อนอันดับ ตามลำดับ และแบบหลังอันดับ

การแวะผ่านแบบก่อนลำดับ คือ a, b, d, h, e, I, j, c, f, g, k
การแวะผ่านแบบตามลำดับ คือ h, d, b, I, e, j, a, f, c, k, g
การแวะผ่านแบบหลังลำดับ คือ h, d, I, j, e, b, f, k, g, c, a
อัลกอริทึม สำหรับการแวะผ่าน ต้นไม้ราแบบอันดับ ในลักษณะ ก่อนลำดับ ตามลำดับ หรือ หลังลำดับ 
แสดงให้เห็น ง่ายที่สุด แบบเรียกซ้ำ