Trees (ทรี)

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)
       อัลกิริทึมการวิ่งแบบโพส-ออเดอร์

โครงสร้างข้อมูลแบบ Queue

 โครงสร้างข้อมูลแบบ Queue
        โครงสร้าง  Queue เป็น list ของ Element (รายการ) ที่มีการเพิ่ม 1 ทางและลบข้อมูลออก 1 ทางมีคุณสมบัติที่เข้าก่อนออกก่อน FIFO (First in First out)
การสร้าง Queue
        ในการสร้าง Queue สามารถจัดเก็บได้หลายลักษณะ แต่ทั่วไปจะใช้การเก็บแบบ list ทางเดียวหรือ Array แบบต่อเนื่องโดยต้องใช้ pointer อีก 2 ตัว ชื่อว่า F (front pointer) เป็นตัวชี้ที่เก็บตำแหน่งส่วนหน้า และ R (rear pointer) เป็นตัวชี้ที่เก็บตำแหน่งส่วนท้าย โดยข้อมูลจะเข้าไปทาง rear หรือส่วนท้ายและจะออกจาก Queue ทาง front หรือส่วนหน้า
การดำเนินงานของคิว(Queue Operations)
            1. ฟังก์ชั่น Enqueue
         ฟังก์ชั่น Enqueue เป็นการนำข้อมูลเพิ่มเข้าไปในคิว โดยหลังจากที่ข้อมูลได้เพิ่มเข้าไปในคิวแล้วสมาชิกใหม่ที่เพิ่มเข้าไปจะนำไป ต่อจากส่วน Rear  ซึ่งการเพิ่มข้อมูลเข้าไปในคิวก็ไม่ได้แตกต่างไปจากสแต็กตรงที่จะต้องมี พื้นที่ว่างพอที่จะใส่สมาชิกใหม่เข้าไป  ดังนั้นหากมีพื้นที่ไม่เพียงพอต่อการเพิ่มสมาชิกใหม่เข้าไปในคิวก็จะเกิด สถานะ Overflow
          2.ฟังก์ชั่น Dequeue
        ฟังก์ชั่น Dequeue เป็นการลบข้อมูลออกจากคิว โดยข้อมูลที่อยู่ส่วน Front จะถูกคืนค่าส่งไปยังยูสเซอร์หรือโมดูลที่เรียกใช้จากนั้นก็จะนำข้อมูลนี้ออก จากคิวในกรณีที่มีการเรียกใช้ฟังก์ชั่นนี้และหากภายในคิวไม่มีข้อมูล ก็จะทำให้เกิดสถานะ Underflow
          3.ฟังก์ชั่น Queue Front
        ฟังก์ชั่น Queue Front ข้อมูลที่อยู่ส่วน Front นั้น สามารถดึงขึ้นมาใช้งานได้ด้วยฟังก์ชั่น Queue Front ฟังก์ชั่นดังกล่าวจะทำการคืนค่าข้อมูลกลับไปยังผู้เรียกใช้โดยไม่มีการ เปลี่ยนแปลงใด ๆ ในคิวอย่างไรก็ตามหากในคิวว่างเปล่า และมีการเรียกใช้งานฟังก์ชั่นนี้  ก็จะทำให้เกิดสถานะของข้อผิดพลาดที่เรียกว่า Underflow

4.ฟังก์ชั่น Queue Rear
        ฟังก์ชั่น Queue Rear มีลักษณะการทำงานเช่นเดียวกันกับฟังก์ชั่น Queue Front แต่จะแตกต่างกันตรงที่เป็นการดึงข้อมูลตรงส่วนท้ายคิวหรือ Rear ออกมาใช้งานในกรณีที่เรียกใช้ฟังก์ชั่นนี้และปรากฏว่าภายในคิวว่างเปล่าก็จะ ทำให้เกิดสถานะของข้อผิดพลาดที่เรียกว่า Underflow

การออกแบบคิวด้วยอาร์เรย์ (Queue Array Design)
          การเพิ่มข้อมูลเข้าไปในคิวด้วย โครงสร้างข้อมูลแบบอาร์เรย์นั้น ก็จะเพิ่มเข้าในส่วนท้ายคิวที่เรียกว่า Rear ส่วนการนำข้อมูลออกก็จะดำเนินการที่ส่วนของหัวคิวที่เรียกว่า Front
และด้วยการใช้โครงสร้างอาร์เรย์ในการสร้างคิว จะเป็นการจัดสรรหน่วยความจำแบบคงที่ ดังนั้น จึงสามารถเกิดกรณีคิวเต็มได้ หากมีการเพิ่มจำนวนสมาชิกมากกว่าที่ประกาศไว้ แต่อย่างไรก็ตามในกรณีที่มีการเพิ่มข้อมูลต่อท้ายจนเต็ม ในขณะที่ส่วนหน้าของ Front ที่ถูก Dequeue ไปยังมีที่ว่างอยู่
การแก้ปัญหาเพื่อให้สามารถเพิ่มข้อมูลเข้าไปได้อีก นั้น สามารถกระทำได้ด้วยการเลื่อนขยับกลุ่มสมาชิกข้อมูลเหล่านั้นไปไว้ยังส่วน หน้าของอาร์เรย์ทั้งหมด โดยการขยับสมาชิกทุกตัวไปข้างหน้า 1 ตำแหน่งไปเรื่อย ๆ

โครงสร้างข้อมูลแบบคิววงกลม (Circular Queue) หรือ Dequeue

         การจัด Array ให้ทำงานเป็น Queue แบบธรรมดา มีข้อจำกัดคือ บางครั้ง Queue มีที่ว่างอยู่ด้าน F แต่ด้าน R เต็ม ทำให้ไม่สามารถนำข้อมูลเข้า Queue ได้ ดังนั้นการนำที่ว่างในส่วนหน้า (F) มาใช้อีก ทำได้โดยให้ส่วนท้ายของ Queue   โครงสร้าง Queue   แบบนี้เรียกว่า   Circular Queue หมายความว่า Queue นั้นเต็ม แต่ Queue แบบ Circular เมื่อ R=N จะปรับให้ R=1   ในกรณีค่า R=ค่าสุดท้ายใน Array ทั่วไป จะหมายถึง Queue เต็ม แต่กรณีของ  Circular Queue สามารถให้ R เลื่อนกลับตำแหน่งแรกได้ ถ้าตำแหน่งนั้นว่าง