ต้นไม้แบบทวิภาค

ต้นไม้ทวิภาค () ในศาสตร์คอมพิวเตอร์ เป็นโครงสร้างข้อมูลแบบต้นไม้ซึ่งแต่ละปมมีปมลูกได้ไม่เกิน 2 ปม โดยแยกออกเป็นปมด้านซ้าย และปมด้านขวา  ปมที่มีปมลูก เรียกว่า ปมพ่อแม่  และปมลูกอาจมีรีเฟอร์เรนซ์ไปยังปมพ่อแม่ของมัน  ในโครงสร้างแบบต้นไม้จะมีปม ๆ หนึ่งเป็นปมบรรพบุรุษของทุกปม เราเรียกปมนี้ว่าปมราก การเข้าถึงปมทุกปมในโครงสร้างแบบต้นไม้ทำได้โดยเริ่มต้นจากปมราก และใช้รีเฟอร์เรนซ์ของปมนั้นท่องไปตามปมลูกด้านซ้ายและด้านขวาของมัน  ต้นไม้ที่มีเฉพาะปมราก เรียกว่าต้นไม้ว่าง (null tree) ในต้นไม้ทวิภาค กิ่งหรือดีกรีของทุก ๆ ปมมีค่ามากที่สุดได้ไม่เกิน 2 ต้นไม้ที่มีปมจำนวน  'n' ปมจะมีกิ่งได้ไม่เกิน 'n-1' กิ่ง 
ต้นไม้ทวิภาคมักใช้สำหรับต้นไม้ค้นหาทวิภาค (binary search trees) และฮีพทวิภาค (binary heaps)

คำจำกัดความสำหรับต้นไม้ราก
 ขอบโดยตรง (A directed edge) หมายถึงเส้นที่เชื่อมจากปมพ่อแม่ไปยังปมลูก
 ปมรากเป็นปมที่ไม่มีปมพ่อแม่ ต้นไม้หนึ่งต้นมีปมรากเพียงปมเดียว
 ปมใบ (leaf node) เป็นปมที่ไม่มีปมลูก
 ความลึกของปม (The depth of a node) n เป็นความยาวของเส้นทางจากปมราก ไปจนถึงปมนั้น  เซตของทุกปม ณ ความลึกที่ให้ บางครั้งเรียกว่าระดับของต้นไม้  ปมรากมีความลึกเท่ากับ 0
 ความลึก หรือความสูง (The depth or height) ของต้นไม้ เป็นความยาวของเส้นทางจากปมรากไปจนถึงปมที่อยู่ลึกที่สุดของต้นไม้นั้น  
 ปมพี่น้อง (Siblings nodes) เป็นปมที่มีปมพ่อแม่เดียวกัน
 ปม p เป็นปมบรรพบุรุษของปม  q ถ้ามีเส้นทางจากปมรากไปถึงปม  q และเรียกปม  q ว่าเป็นปมลูกหลานของปม p
 ขนาดของปม (The size of a node) คือ จำนวนปมลูกหลานของมันทั้งหมดรวมทั้งตัวมันด้วย 
 กิ่งเข้า (In-degree) ของปม คือจำนวนกิ่งที่เข้าหามัน
 กิ่งออก (Out-degree) ของปม คื่อจำนวนกิ่งที่ออกจากปมนั้น 
 ปมรากเป็นเพียงปมเดียวในต้นไม้ที่มีกิ่งเข้า (In-degree) เท่ากับ 0
 ปมในมีกิ่งออก เท่ากับ 0

ชนิดของต้นไม้ทวิภาค
 ต้นไม้ทวิภาคที่มีราก (A rooted binary tree) เป็นต้นไม้ซึ่งปมรากหนึ่งปม และทุกปมในต้นไม้มีปมลูกได้ไม่เกิน 2 ปม 
 ต้นไม้ทวิภาคแบบเต็ม (A full binary tree) เป็นต้นไม้ซึ่งทุก ๆ ปมยกเว้นปมใบ มีปมลูก 2 ปม 
 ต้นไม้ทวิภาคแบบสมบูรณ์ (A perfect binary tree) เป็นต้นไม้ทวิภาคแบบเต็ม ซึ่งปมใบทุกปมจะอยู่ในระดับเดียวกันหรือมีความลึกเท่ากัน  
 complete binary tree เป็นต้นไม้ทวิภาคซึ่งปมทุกระดับยกเว้นระดับล่างสุด จะมีปมลูก 2 ปม และทุกปมจะเริ่มจากทางซ้ายสุด 
 ต้นไม้ทวิภาคสมดุล เป็นต้นไม้ทวิภาค ซึ่งความลึกของต้นไม้ย่อย (subtree) สองต้นของทุก ๆ ปม เท่ากัน ปมใบของต้นไม้ย่อยจะมีระดับเท่ากัน 

คุณสมบัติของต้นไม้ทวิภาค

หมวดหมู่:โครงสร้างข้อมูล
หมวดหมู่:ต้นไม้แบบทวิภาค