สรุปครั้งที่8 โครงสร้างข้อมูลและขั้นตอนวิธี

Tree
      ทรี เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ระหว่างโหนด จะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับชั้น เช่น Flowchat เป็นต้น
         แต่ละโหนกจะมีความสัมพันธ์กับโหนดในระดับที่ต่ำลงมาหนึ่งระดับได้หลายๆโหนด เรียกว่า โหนดแม่
         โหนดที่อยู่ต่ำกว่าโหนกแม่อยู่หนึ่งระดับเรียกว่า โหนดลูก
         โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่ เรียกว่า โหนดราก
         โหนดที่มีโหนดแม่เป็นโหนดเดียวกัน เรียกว่า โหนดพี่น้อง
         โหนดที่ไม่มีโหนดลูก เรียกว่า โหนดใบ
         เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนด เรียกว่า กิ่ง


นิยามของทรี 
1.นิยามทรีด้วยนิยามของกราฟ
            ทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด (Loop) ในโครงสร้าง โหนดสองโหนดใดๆ ในทรีต้องมีทางติดต่อกันทางเดียวเท่านั้น และทรีที่มี N โหนด ต้องมีกิ่งทั้งหมด N-1 เส้น
            การเขียนรูปแบบทรี เขียนได้ 4 แบบ คือ แบบที่มีรากอยู่ข้างบน,แบบที่มีรากอยู่ข้างล่าง,แบบที่มีรากอยู่ด้านซ้าย,แบบที่มีรากอยู่ด้านขวา
2.นิยามทรีด้วยรูปแบบรีเคอร์ซีฟ
            ทรี ประกอบด้วยสมาชิกที่เรียกว่าโหนด โดยที่ถ้าว่าง ไม่มีโหนดใดๆเรียกว่า Null Tree และถ้ามีโหนดหนึ่งเป็นโหนดราก ส่วนที่เหลือจะแบ่งเป็นทรีย่อย (Sub Tree)

นิยามที่เกี่ยวข้องกับทรี
1.Forest คือ เซตของทรีที่แยกจากกัน
2.Ordered Tree คือ ทรีโหนดต่างๆในทรีนั้นมีความสัมพันธ์ที่แน่นอน
3.ทรีคล้าย (Similar Tree) คือ ทรีที่มีโครงสร้างเหมือนกัน (แต่ Data ต่าง)
4.ทรีเหมือน คือ ทรีที่เหมือนกันโดนสมบูรณ์ (Order และ Data เหมือนกัน)
5.Degree คือ จำนวนทรีย่อยของโหนดนั้นๆ
6.Level of Node คือ ระยะทางในแนวดึงของโหนดนั้นๆ ที่อยู่ห่างจากโหนดราก ซึ่งระดับของโหนดจะเท่ากับจำนวนกิ่งที่น้อยที่สุดจากโหนดรากไปยังโหนดใดๆบวกด้วย 1 และจำนวนเส้นทางตามแนวดิ่งของโหนดใดๆ ซึ่งห่างจากโหนดราก เรียกว่า ความสูง หรือ ความลึก

การแทนที่ืทรีในหน่วยความจำหลัก
              จะมีพอยเตอร์เชื่อมโยงจากโหนดแม่ไปยังโหนดลูก แต่ละโหนดต้องมีลิงค์ฟิลด์เพื่อเก็บที่อยู่ของโหนดลูกต่างๆนั้นคือ จำนวนลิงค์ฟิลด์
1. โหนดแต่ละโหนดเก็บพอยเตอร์ชี้ไปยังโหนดลูกทุกโหนด
               การแทนที่วิธีนี้ จะทำให้จำนวนฟิลด์ในแต่ละโหนดเท่ากัน และค่อนข้างใช้เนื้อที่จำนวนมาก เนื่องจากแต่ละโหนดมีจำนวนโหนดลูกไม่เท่ากันหรือบางโหนดไม่มีลูกเลย ถ้าเป็นทรีที่แต่ละโหนดมีจำนวนโหนดลูกที่แตกต่างกันมาก จะเป็นการสิ้นเปลืองเนื้อที่ในหน่วยความจำโดยเปล่าประโยชน์
2. แทนที่ด้วยไบนารีทรี
               เป็นวิธีแก้ปัญหาเพื่อลดการสิ้นเปลืองเนื้อที่ในหน่วยความจำ โดยกำหนดให้แต่ละโหนดมีจำนวนลิงค์ฟิลด์สองลิงค์ฟิลด์
- ลิงค์ฟิลด์แรกเก็บที่อยู่ของโหนดลูกคนโต
- ลิงคฟิลด์ที่สองเก็บที่อยู่ของโหนดพี่น้องที่เป็นโหนดถัดไปโหนดใดไม่มีโหนดลูกหรือไม่มีโหนดพี่น้องให้ค่าพอยเตอร์ในลิงค์ฟิลด์มีค่าเป็น Null

การแปลงทรีทั่วไปให้เป็นไบนารีทรี มีลำดับขั้นตอนการแปลงดังต่อไปนี้
1.ให้โหนดแม่ชี้ไปยังโหนดลูกคนโต แล้วลบความสัมพันธ์ ระหว่างโหนดแม่และโหนดลูกอื่นๆ
2.ให้เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง
3.จับให้ทรีย่อยทางขวาเอียงลงมา 45 องศา

การท่องไปในไบนารีทรี
              ปฏิบัติการที่สำคัญในไบนารีทรี คือการท่องไปในไบนารี เพื่อเข้าไปเยือนทุกๆโหนดในทรี สามารถเยือนโหนดทุกๆโหนดๆละหนึ่งครั้ง โหนดที่ถูกเยือนอาจเป็นโหนดแ่ม่ (แทนด้วย N) ทรีย่อยทางซ้าย (แทนด้วย L) หรือทรีย่อยทางขวา (แทนด้วย R)

สรุปครั้งที่7โครงสร้างข้อมูลและขั้นตอนวิธี

Queue
         คิว เป็นโครงสร้างข้อมูลแบบเชิงเส้น ซึ่งการเพิ่มข้อมูลจะกระทำที่ส่วนท้าย (rear) และการนำข้อมูลออกจะกระทำที่ปลายส่วนหน้า(front) ลักษณะการทำงานของคิวเป็นลักษณะเข้าก่อนออกก่อน (FIFO : First In First Out)

การดำเนินการเกี่ยวกับคิว
1. Create Queue จัดสรรหน่วยความจำให้แก่ Head Node และให้ค่า Pointer ทั้ง2 ตัวมีค่าเป็น Null และจำนวนสมาชิกเป็น0
2. Enqueue การเพิ่มข้อมูลเข้าไปในคิว
3. Dequeue การนำข้อมูลออกจากคิว
4. Queue Front เป็นการนำข้อมูลที่อยู่ส่วนต้นของคิวมาแสดง
5. Queue Rear เป็นการนำข้อมูลที่อยู่ส่วนท้ายของคิวมาแสดง
6. Empty Queue เป็นการตรวจสอบว่าคิวว่างหรือไม่
7. Full Queue เป็นการตรวจสอบว่าคิวเต็มหรือไม่
8. Queue Count เป็นการนับจำนวนสมาชิกที่อยู่ในคิว
9. Destroy Queue เป็นการลบข้อมูลทั้งหมดที่อยู่ในคิว

          การนำข้อมูลเข้าสู่คิว จะไม่สามารถนำเข้าในขณะที่คิวเต็ม หรือไม่มีที่ว่าง ถ้าพยายามนำเข้าจะทำให้เกิดความผิดพลาดที่เรียกว่า Overflow
          การนำข้อมูลออกจากคิว จะไม่สามารถนำอะไรออกจากคิวที่ว่างเปล่าได้ ถ้าพยายามจะทำให้เกิดความผิดพลาดที่เรียกว่า underflow