เวลาเจอคำว่า “ต้นไม้ทวิภาคสมบูรณ์ (Complete Binary Tree)” ในโจทย์ หลายคนจะสับสนกับ “ต้นไม้ทวิภาคเต็ม (Full/Perfect)” เราเคยงงเหมือนกัน เลยสรุปแบบที่ใช้จำตอนทำแบบฝึกหัดจริง ๆ ให้ค่ะ 1) นิยามที่ใช้ตอบโจทย์ได้เร็ว - Complete Binary Tree = ทุกระดับ (level) ถูกเติมโหนดให้ “เต็มที่สุดเท่าที่ทำได้” จากซ้ายไปขวา - ยกเว้นระดับสุดท้ายที่อาจไม่เต็ม แต่ต้องเรียงชิดซ้ายเสมอ ทริคจำ: “ไม่เว้นช่องว่างด้านซ้าย” 2) ต่างจาก Perfect/Full ยังไง (กันงง) - Perfect Binary Tree: ทุกระดับเต็มหมด (จำนวนโหนด = 2^(h+1)-1) - Full Binary Tree: ทุกโหนดมีลูก 0 หรือ 2 คน (ไม่มีลูกคนเดียว) - Complete: อนุญาตให้ระดับล่างสุดไม่เต็ม และบางโหนดอาจมีลูกคนเดียวได้ แต่ตำแหน่งต้องชิดซ้าย 3) ทำไม Complete ถึงเจอบ่อยในโจทย์ เพราะมันเข้ากับการเก็บข้อมูลแบบอาเรย์ (array) มาก ๆ เช่น heap/priority queue โดย mapping ตำแหน่งได้เลย: - โหนดที่ index i - ลูกซ้าย = 2i - ลูกขวา = 2i+1 - พ่อแม่ = floor(i/2) (กรณีเริ่ม index ที่ 1; ถ้าเริ่มที่ 0 จะเป็น 2i+1 และ 2i+2) 4) ตัวอย่างที่ชอบออกแนว “Output ที่ 4” หลายโจทย์จะให้เราพิมพ์ผลลัพธ์เป็นลำดับ เช่น level-order, in-order, pre-order หรือ post-order แล้วมีตัวเลือก Output 1-4 วิธีช่วยให้เลือก “Output ที่ 4” ได้แม่นขึ้น: - วาดโครงต้นไม้ก่อน โดยเติมโหนดทีละตัวจากซ้ายไปขวาตามนิยาม complete - ระบุ traversal ที่โจทย์ต้องการ - Pre-order: root-left-right - In-order: left-root-right - Post-order: left-right-root - Level-order: ไล่ทีละชั้น จากนั้นค่อยเทียบกับตัวเลือก 5) เคสค่าติดลบอย่าง -21 ต้องระวังอะไร ค่าของโหนดจะเป็นบวก/ลบไม่เกี่ยวกับความเป็น complete เลย จุดที่พลาดบ่อยคือ “คิดว่าเลขติดลบอยู่ซ้าย/ขวาเสมอ” ซึ่งจริง ๆ จะเป็นแบบนั้นเฉพาะ Binary Search Tree (BST) ดังนั้นถ้าโจทย์บอกแค่ Complete Binary Tree ให้ยึดตำแหน่งตามการเติมชิดซ้าย ไม่ใช่ตามค่าตัวเลข 6) เช็กลิสต์กันพลาด (ใช้ก่อนส่งคำตอบ) - ระดับก่อนสุดท้ายเต็มไหม? (ควรเต็ม) - ระดับสุดท้ายเรียงชิดซ้ายหรือมีช่องว่างกลาง ๆ - มีโหนดที่มี “ลูกขวาอย่างเดียว” ไหม? ถ้ามี = ไม่ complete (เพราะต้องเติมซ้ายก่อน) - Traversal ที่ใช้ถูกชนิดไหม (โจทย์ชอบสลับคำ) ถ้าคุณกำลังทำโจทย์แล้วติดที่การเลือก “Output ที่ 4” แนะนำให้ลองเขียนลำดับ traversal ทีละขั้นลงกระดาษ/โน้ตสั้น ๆ จะลดความผิดพลาดได้เยอะมาก โดยเฉพาะตอนมีตัวเลขอย่าง -21 ปนอยู่ในต้นไม้