บทที่ 7 Binary Tree

Binary Tree

            Binary Tree มีลักษณะเหมือนกับ Tree ปกติแต่มีคุณสมบัติพิเศษ คือ “แต่ละโหนดจะมีโหนดลูกได้ไม่เกิน 2 โหนด” หรือพูดอีกนัยหนึ่งก็คือ แต่ละโหนดใน binary tree จะมีดีกรีได้ไม่เกิน 2
Complete Binary Tree
            Complete Binary Tree หรือต้นไม้ไบนารีแบบสมบูรณ์ มีลักษณะคล้ายกับ Binary Tree แต่มีข้อพิเศษ คือ

1.      ทุกโหนดที่ไม่ใช่ Leaf Node จะต้องมีโหนดลูก 2 โหนด

2.      Leaf Node จะต้องอยู่ในระดับเดียวกัน

Almost  Complete  Binary  Tree
            Almost  Complete  Binary  Tree หรือ ไบนารี่ทรีเกือบ จะมีโหนดเฉพาะบางส่วนอาจเป็นโหนดซ้ายหรือโหนดขวา 

การท่องไปในทรี (Tree Traversal)สามารถท่องเข้าไปในทรีเพื่อดูข้อมูล ได้ 3 วิธีด้วยกันคือ
1. Pre-order
2. In-order
3. Post-order
1.แบบพรี-ออเดอร์ (Pre-order)
            มีลักษณะการวิ่งในแนวลึกก่อน (Depth-first Order)
อัลกอริทึมการวิ่งแบบพรี-ออเดอร์

2.แบบอิน-ออเดอร์ (In-Order)
            มีการวิ่งลักษณะแบบสมดุล (Symmetric Order)
อัลกิริทึมการวิ่งแบบอิน-ออเดอร์
3.แบบโพสต์-ออเดอร์(Post-Oder)
             อัลกิริทึมการวิ่งแบบโพส-ออเดอร์