LECTURE8

DTS:08-26-08-2552

เรื่อง Tree

-ทรี(Tree)เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ระหว่างโหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับชั้น(Hierarchical Relationship)แต่ละโหนดจะมีความสัมพันธ์กับโหนดในระดับที่ต่ำลงมา หนึ่งระดับได้หลายๆโหนดเรียกโหนดดังกล่าวว่า โหนดแม่(ParentorMotherNode)โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่หนึ่งระดับเรียกว่า โหนดลูก(Child or Son Node)โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่เรียกว่าโหนดราก(Root Node)

-โหนดที่มีโหนดแม่เป็นโหนดเดียวกันเรียกว่า โหนดพี่น้อง (Siblings)โหนดที่ไม่มีโหนดลูก เรียกว่าโหนดใบ (Leave Node)เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนดเรียกว่า กิ่ง (Branch)

นิยามของทรี

1. นิยามทรีด้วยนิยามของกราฟทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด (loop) ในโครงสร้าง โหนดสองโหนดใด ๆ ในทรีต้องมีทางติดต่อกันทางเดียวเท่านั้น และทรีที่มี N โหนด ต้องมีกิ่งทั้งหมด N-1 เส้น

2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟทรีประกอบด้วยสมาชิกที่เรียกว่าโหนด โดยที่ ถ้าว่าง ไม่มีโหนดใด ๆ เรียกว่านัลทรี (Null Tree) และถ้ามีโหนดหนึ่งเป็นโหนดราก ส่วนที่เหลือจะแบ่งเป็นทรีย่อย (Sub Tree)T1, T2, T3,…,Tk โดยที่ k>=0 และทรีย่อยต้องมีคุณสมบัติเป็นทรี

นิยามที่เกี่ยวข้องกับทรี
1. ฟอร์เรสต์ (Forest)หมายถึง กลุ่มของทรีที่เกิดจากการเอาโหนดรากของทรีออกหรือ เซตของทรีที่แยกจากกัน(Disjoint Trees)

2. ทรีที่มีแบบแผน (Ordered Tree)หมายถึง ทรีที่โหนดต่าง ๆ ในทรีนั้นมีความสัมพันธ์ที่แน่นอน เช่น ไปทางขวาไปทางซ้าย เป็นต้น

3. ทรีคล้าย (Similar Tree) คือทรีที่มีโครงสร้างเหมือนกัน หรือทรีที่มีรูปร่างของทรีเหมือนกัน โดยไม่คำนึงถึงข้อมูลที่อยู่ในแต่ละโหนด

4. ทรีเหมือน (Equivalent Tree) คือทรีที่เหมือนกันโดยสมบูรณ์ โดยต้องเป็นทรีที่คล้ายกันและแต่ละโหนดในตำแหน่งเดียวกันมีข้อมูลเหมือนกัน

5. กำลัง (Degree) หมายถึงจำนวนทรีย่อยของโหนด นั้น ๆ

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

-โครงสร้างทรีที่แต่ละโหนดมีลิงค์ฟิลด์แค่สองลิงค์ฟิลด์ ซึ่งช่วยให้ประหยัดเนื้อที่ในการจัดเก็บได้มาก เรียกโครงสร้างทรีที่แต่ละโหนดมีจำนวนโหนดลูกไม่เกินสองหรือแต่ละโหนดมีจำนวนทรีย่อยไม่เกินสองนี้ว่า ไบนารีทรี (Binary Tree)

มีวิธีการท่องเข้าไปในทรี 6 วิธี คือ NLR LNR LRN NRL RNL และ RLN แต่วิธีการท่องเข้าไปไบนารีทรีที่นิยมใช้กันมากเป็นการท่องจากซ้ายไปขวา 3 แบบแรกเท่านั้นคือ NLR LNR และ LRN ซึ่งลักษณะการเป็นนิยามแบบ รีเคอร์ซีฟ(Recursive) ซึ่งขั้นตอนการท่องไปในแต่ละแบบมีดังนี้

1. การท่องไปแบบพรีออร์เดอร์(Preorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธีNLR มีขั้นตอนการเดินดังต่อไปนี้
(1) เยือนโหนดราก
(2) ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
(3) ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์

2.การท่องไปแบบอินออร์เดอร์(Inorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่าง ๆในทรีด้วยวิธี LNR
มีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
(2) เยือนโหนดราก
(3) ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์

3. การท่องไปแบบโพสออร์เดอร์(Postorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่าง ๆในทรีด้วยวิธี LRN มีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบโพสต์ออร์เดอร์
(2) ท่องไปในทรีย่อยทางขวาแบบโพสต์ออร์เดอร์
(3) เยือนโหนดราก

LECTURE7

DTS:07-05-08-2552

เรื่อง Queue


คิว (Queue)เป็นโครงสร้างข้อมูลแบบเชิงเส้นหรือลิเนียร์ลิสต์ซึ่งการเพิ่มข้อมูลจะกระทำที่ปลายข้างหนึ่งซึ่งเรียกว่าส่วนท้ายหรือเรียร์ (rear)และการนำข้อมูลออกจะกระทำที่ปลายอีกข้างหนึ่งซึ่งเรียกว่า ส่วนหน้าหรือฟรอนต์(front)

-ลักษณะการทำงานของคิวเป็นลักษณะของการเข้าก่อนออกก่อนหรือที่เรียกว่าFIFO (First In First Out)

การทำงานของคิวการใส่สมาชิกตัวใหม่ลงในคิวเรียกว่าEnqueueซึ่งมีรูปแบบคือenqueu(queue,newElement) หมายถึง การใส่ข้อมูลnewElement ลงไปที่ส่วนเรียร์ของคิว

การนำสมาชิกออกจากคิว เรียกว่าDequeue ซึ่งมีรูปแบบคือdequeue (queue, element) หมายถึง การนำออกจากส่วนหน้าของคิวและให้ ข้อมูลนั้นกับ element


-การนำข้อมูลที่อยู่ตอนต้นของคิวมาแสดงจะเรียกว่า Queue Frontแต่จะไม่ทำการเอาข้อมูลออกจากคิว
-การนำข้อมูลที่อยู่ตอนท้ายของคิวมาแสดงจะ เรียกว่าQueue Rear แต่จะไม่ทำการเพิ่มข้อมูลเข้าไปในคิว



การแทนที่ข้อมูลของคิวสามารถทำได้ 2 วิธี คือ

1. การแทนที่ข้อมูลของคิวแบบลิงค์ลิสต์

2. การแทนที่ข้อมูลของคิวแบบอะเรย์



การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์จะประกอบไปด้วย 2 ส่วน คือ

1. Head Nodeจะประกอบไปด้วย 3 ส่วนคือพอยเตอร์จำนวน 2 ตัว คือ Front และ rear กับจำนวนสมาชิในคิว

2. Data Node จะประกอบไปด้วยข้อมูล (Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป


การดำเนินการเกี่ยวกับคิว ได้แก่

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

-ในกรณีที่เป็นคิวแบบวงกลมคิวจะเต็มก็ต่อเมื่อมีการเพิ่มข้อมูลเข้าไปในคิวเรื่อยๆจนกระทั่งrearมีค่าน้อกว่า front อยู่หนึ่งค่าคือ rear = front - 1