DTS 08-26/08/52

สรุป

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

(ก) ต้นไม้ปกติในธรรมชาติ (ข) ต้นไม้ในวิชาโครงสร้างข้อมูล
รูปลักษณะของโครงสร้างต้นไม้

ทรี ประกอบด้วยโหนด (node) ซึ่งเป็นส่วนที่เก็บข้อมูล ในทรีหนึ่งทรีจะประกอบไปด้วยรูทโหนด (root node) เพียงหนึ่งโหนด แล้วรูทโหนดสามารถแตกโหนดออกเป็นโหนดย่อยๆ ได้อีกหลายโหนดเรียกว่าโหนดลูก (Child node) เมื่อมีโหนดลูกแล้ว โหนดลูกก็ยังสามารถแสดงเป็นโหนดพ่อแม่ (Parent Node) โดยการแตกโหนดออกเป็นโหนดย่อยๆได้อีก













Root Node จากรูป คือ โหนด A
Child Node หรือ โหนดลูก จากรูป B , C , D และ E เป็น โหนดลูกของ A
Parent Node หรือโหนดพ่อแม่ โหนด B ที่เป็นโหนดลูกของโหนด A ก็สามารถแตกออกเป็น
โหนดย่อยๆ ได้แก่ F และ G ดังนั้น B จึงเป็นโหนดพ่อแม่ของ F และ G ในทำนองเดียวกัน A
ก็เป็นโหนด พ่อแม่ของ B , C , D และ E
กิ่ง (Branch or Edge) เป็นเส้นที่เชื่อมต่อระหว่างโหนดพ่อแม่กับโหนดลูก
Brother Node หรือโหนดพี่น้อง คือ โหนดที่มีพ่อแม่เดียวกัน เช่น B , C , D , E เป็นโหนดพี่น้องกันเพราะมีโหนดพ่อแม่เดียวกัน คือ โหนด A และ F และ G เป็นโหนดพี่น้องกันโดยมี B เป็นโหนดพ่อแม่
Leaf Node คือ โหนดที่ไม่มีโหนดลูก จากรูปโหนดที่ไม่มีโหนดลูก ได้แก่ F G H I J K L M
Branch Node คือ โหนดที่ไม่ใช่ Leaf Node เช่น โหนด B C D E เรียกว่า Branch Node
Degree คือ จำนวนลูกของโหนด x เช่น degree ของ โหนด A = 4 ได้แก่ B C D E จำนวน degree ของโหนด B = 2 จำนวนdegree ของโหนด F = 0 เนื่องจากโหนด F ไม่มีโหนดลูก
Direct Descendant Node คือโหนดที่มาทีหลังทันที จากรูป B C D E เป็น direct descendant node ของโหนด A เพราะเป็นโหนดที่มาทีหลังทันที
Descendant Node คือ โหนดลูกของโหนด x และโหนดที่ทุกโหนดที่แตกจากโหนดลูกของโหนด x
ตัวอย่าง descendant ของโหนด A คือ ทุกโหนดที่เหลือในทรี
Direct Ancestor Node หรือโหนดที่มาก่อนทันที ตัวอย่าง Direct Ancestor ของโหนด H คือ โหนด C , Direct Ancestor ของโหนด C คือ โหนด A
Level หรือระดับ คือ หมายเลขแสดงระดับของโหนดในทรี ซึ่งรูทโหนดจะมีค่า Level = 0 ส่วนโหนดลูกของรูทโหนดก็จะมีค่า = 1 หากค่าโหนด x อยู่ในระดับ L โหนดลูกของ x ก็จะอยู่ในระดับ L + 1
Binary Tree มีลักษณะเหมือนกับ Tree ปกติแต่มีคุณสมบัติพิเศษ คือ “แต่ละโหนดจะมีโหนดลูกได้ไม่เกิน 2 โหนด” หรือพูดอีกนัยหนึ่งก็คือ แต่ละโหนดใน binary tree จะมีดีกรีได้ไม่เกิน 2ตัวอย่าง binary tree















การแปลงทรีทั่วไปเป็นแบบไบนารี ในทรีทั่วไปโหนดแต่ละโหนดจะมีกี่ SON ก็ได้ ส่วนไบนารีแต่ละโหนดจะมี SON ได้มากที่สุดเท่ากับ 2 SONs การแปลงต้นไม้ทั่วไปให้เป็นแบบไบนารีจะใช้หลักความจริงที่ว่า ในต้นไม้ทั่วไปแต่ละโหนดจะมี SON ที่อยู่ทางซ้ายสุด 1 SON และ SON โหนดนั้นจะมีพี่น้องถัดไป 1โหนด
เท่านั้น การแปลงนั้นแบ่งได้เป็น 2 ขั้นตอน คือ
ขั้นที่ 1 แปลงต้นไม้ทั่วไปโดยใช้หลักความสัมพันธ์ระหว่างโหนดเป็น leftmost son - next sibiling
ขั้นที่ 2 หมุนต้นไม้ที่แปลงแล้วไป 45 องศา จะได้ต้นไม้ไบนารีแบบปกติ การแปลงต้นไม้ทั่วไปเป็นแบบ
ไบนารีทรี การท่องไปในไบนารีทรี (traversing binary tree) เพื่อเข้าไปเยือนทุก ๆ โหนดในทรี ซึ่งวิธีการท่องเข้าไปต้องเป็นไปอย่างมีระบบแบบแผน สามารถเยือนโหนดทุก ๆ โหนด ๆ ละหนึ่งครั้ง วิธีการท่องไปนั้นมีด้วยกันหลายแบบแล้วแต่ว่าต้องการลำดับขั้นตอนการเยือนอย่างไรในการเยือนแต่ละครั้ง โหนดที่ถูกเยือนอาจเป็นโหนดแม่ (แทนด้วย N) ทรีย่อยทางซ้าย (แทนด้วย L) หรือทรีย่อยทางขวา (แทนด้วย R) มีวิธีการท่องเข้าไปในทรี 6 วิธี คือ NLR LNR LRN NRL RNL และ RLN แต่วิธีการท่องเข้าไปไบนารีทรีที่นิยมใช้กันมากเป็นการท่องจากซ้ายไปขวา 3 แบบแรกเท่านั้นคือ NLR LNR และ LRN ซึ่งลักษณะการนิยามเป็นนิยามแบบ รีเคอร์ซีฟ (recursive) ซึ่งขั้นตอนการท่องไปในแต่ละแบบมีดังนี้
การท่องไปแบบพรีออร์เดอร์ (preorder traversal)
เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี NLR มีขั้นตอนการเดินดังต่อไปนี้
(1) เยือนโหนดราก
(2) ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
(3) ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์
การท่องไปแบบอินออร์เดอร์ (inorder traversal)
เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี LNR ซึ่งมีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
(2) เยือนโหนดราก
(3) ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์
การท่องไปแบบโพสออร์เดอร์ (postorder traversal)
เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรี ด้วยวิธี LRN ซึ่งมีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบโพสออร์เดอร์
(2) ท่องไปในทรีย่อยทางขวาแบบโพสออร์เดอร์
(3) เยือนโหนดราก
ตัวอย่าง แสดงการท่องไปในไบนารีทรีแบบพรีออร์เดอร์ แบบอินออร์เดอร์ และแบบโพสออร์เดอร์















ท่องแบบพรีออร์เดอร์ (NLR) ผลลัพธ์จากการเยือนโหนดต่าง ๆ ดังนี้ ABDGCEHIF จากรูป แสดงเส้นทางการท่องแบบพรีออร์เดอร์















ท่องแบบอินออร์เดอร์ (LNR) ผลลัพธ์จากการเยือนโหนดต่าง ๆ ดังนี้ DGBAHEICF ในรูป แสดงเส้นทางการท่องแบบอินออร์เดอร์















ท่องแบบโพสออร์เดอร์ (LRN) ผลลัพธ์จากการเยือนโหนดต่าง ๆ ดังนี้ GDBHIEFCA ในรูปแสดงเส้นทางการท่องแบบโพสออร์เดอร์

DTS 07-05/08/52

สรุป
คิวเป็นโครงสร้างข้อมูลแบบลำดับ (Sequential) ลักษณะของคิวเราสามารถพบได้ในชีวิตประจำวัน เช่น การเข้าแถวตามคิวเพื่อรอรับบริการต่างๆ ลำดับการสั่งพิมพ์งาน เป็นต้น ซึ่งจะเห็นได้ว่าลักษณะของการทำงานจะเป็นแบบใครมาเข้าคิวก่อน จะได้รับบริการก่อน เรียกได้ว่าเป็นลักษณะการทำงานแบบ FIFO (First In , First Out) ลักษณะของคิว จะมีปลายสองข้าง ซึ่งข้างหนึ่งจะเป็นช่องทางสำหรับข้อมูลเข้าที่เรียกว่า REAR และอีกข้างหนึ่งซึ่งจะเป็นช่องทางสำหรับข้อมูลออก เรียกว่า FRONT

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

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

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

1. Create Queue การจัดหน่วยความจำให้แก่ Head Node ให้ค่า Pointer ทั้ง 2 ตัวมีค่าเป็น Null

2. Enqueue การเพิ่มข้อมูลเข้าไปในคิว

3. Dequeue การนำข้อมูลออกจากคิว

4. Queue Front เป็นการนำข้อมูลที่อยู่ส่วนต้นของคิวมาแสดง

5. Queue Rear เป็นการนำข้อมูลที่อยู่ส่วนท้ายของคิวมาแสดง

6. Empty Queue เป็นการตรวจสอบว่าคิวว่างหรือไม่

7. Full Queue เป็นการตรวจสอบว่าคิวเต็มหรือไม่

8. Queue Count เป็นการนับจำนวนสมาชิกที่อยู่ในคิว

9. Destroy Queue เป็นการลบข้อมูลทั้งหมดที่อยู่ในคิว

DTS 06-29/07/52

สรุป
การดำเนินการเกี่ยวกับสแตก ได้แก่ 1. Create Stack การจัดสรรความจำให้แก่ Head Node และส่งค่าตำแหน่งที่ชี้ไปยัง Head ของสแตกกลับมา 2. Push Stack การเพิ่มข้อมูลลงไปในสแตก 3. Pop Stack การนำข้อมูลบนสุดออกจากสแตก 4. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสแตก5. Empty Stack เป็นการตรวจสอบการว่างของสแตก 6. Full Stack เป็นการตรวจสอบว่าสแตกเต็มหรือไม่ 7. Stack Count เป็นการนับจำนวนสมาชิกใน สแตก 8. Destroy Stack เป็นการลบข้อมูลทั้งหมดที่อยู่ในสแตก
การใช้ สแตกเพื่อแปลรูปนิพจน์ทางคณิตศาสตร์รูปแบบนิพจน์ทางคณิตศาสตร์
• นิพจน์ Infix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่ระหว่างตัวดำเนินการ (Operands)
เช่น A+B-C
• นิพจน์ Prefix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่หน้าตัวดำเนินการ (Operands)
เช่น +-AB
• นิพจน์ Postfix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่หลังตัวดำเนินการ (Operands)
เช่น AC*+
เราสามารถแปลงนิพจน์ Infix ให้เป็น Postfix ได้โดยอาศัยสแตกที่มีคุณสมบัติการเข้าหลังออกก่อนหรือ LIFO โดยมีอัลกอริทึมในการแปลงนิพจน์ ดังนี้
1. ถ้าข้อมูลเข้า (input) เป็นตัวถูกดำเนินการ (operand) ให้นำออกไปเป็นผลลัพธ์ (output)
2. ถ้าข้อมูลเข้าเป็นตัวดำเนินการ (operator) ให้ดำเนินการดังนี้
2.1 ถ้าสแตกว่าง ให้ push operator ลงในสแตก
2.2 ถ้าสแตกไม่ว่าง ให้เปรียบเทียบ operator ที่เข้ามากับ operator ที่อยู่ในตำแหน่ง TOP ของสแตก
2.3.ถ้า operator ที่เข้ามามีความสำคัญมากกว่า operator ที่ตำแหน่ง TOP ของสแตกให้ push ลงสแตก
2.4. ถ้า operator ที่เข้ามามีความสำคัญน้อยกว่าหรือเท่ากับ operator ที่อยู่ในตำแหน่ง TOP ของสแตก ให้ pop สแตกออกไปเป็นผลลัพธ์ แล้วทำการเปรียบเทียบ operator ที่เข้ามากับ operator ที่ตำแหน่ง TOP ต่อไป จะหยุดจนกว่า operator ที่เข้ามาจะมีความสำคัญมากกว่า operator ที่ตำแหน่ง TOP ของสแตก แล้วจึง push operator ที่เข้ามานั้นลงสแตก
3. ถ้าข้อมูลเข้าเป็นวงเล็บเปิด ให้ push ลงสแตก
4. ถ้าข้อมูลเข้าเป็นวงเล็บปิด ให้ pop ข้อมูลออกจากสแตกไปเป็นผลลัพธ์จนกว่าจะถึงวงเล็บ เปิด จากนั้นทิ้งวงเล็บเปิดและปิดทิ้งไป
5. ถ้าข้อมูลเข้าหมด ให้ pop ข้อมูลออกจากสแตกไปเป็นผลลัพธ์จนกว่าสแตกจะว่าง