DTS-08 26/08/52

Tree
ทรี หรือจะเรียกกันอีกอย่างว่าโครงสร้างต้นไม้
เป็นอีกโครงสร้างที่มีความสัมพันธ์กัน
จะประกอบไปด้วยโหนด (Node)
แต่ละโหนดจะมีความสัมพันธ์กัน
และยังสามารถแตกโหนดออกมาเป็นโหนดย่อยๆ
ได้อีกหลายโหนดด้วยกันเรียกว่าโหนดลูก
เมื่อเรามีโหนดลูกแล้วก้อยังสามารถ
แตกโหนดออกไปเป็นโหนดพ่อโหนดแม่ได้อีก
ชนิดของทรี จะแบ่งออกได้2ชนิดคือ
1 ทรีทั่วไป
2 ไบนารี่ทรี
ในแต่ละโหนดที่มีโหนดแม่เป็นโหนดเดียวกันนั้น
เรียกว่า โหนดพี่น้อง (Siblings)
โหนดที่ไม่มีโหนดลูก เรียกว่า โหนดใบ
และเส้นที่แสดงความสัมพันธ์กันระหว่างโหนดสองโหนด
เรียกว่า กิ่ง
ระดับของโหนดคือ
ระยะทางในแนวดิ่งของโหนดนั้นๆ
ที่อยู่ห่างจากโหนดราก เมื่อกำหนดให้
โหนดรากของทรีนั้นอยู่ในระดับ1และกิ่ง
แต่ละกิ่งที่มีความยาวเท่ากันหมด คือ
ยาวเท่ากับ1หน่วย ซึ่งระดับของโหนด
จะเท่ากับจำนวนกิ่ที่น้อยที่สุดจากโหนดราก
ไปยังโหนดใดๆ บวกด้วย1
และจำนวนเส้นทางตามแนวดิ่งของโหนดใดๆ
ซึ่งห่างจากโหนดราก เรียกว่า ความสูง
หรือความลึก
ไบนารี่ทรีทุกๆโหนดมีทรีย่อยทั้งทางซ้ายและทางขวา
ยกเว้นโหนดใบ และโหนดใบทุกโหนดจะต้องอยู่ในระดับ
เดียวกัน เรียกว่า ไบนารี่ทรีแบบสมบูรณ์
การแปลงทรีในทั่วไปให้เป็นไบนารี่ทรี
มีด้วยกันอยู่3ขั้นตอนคือ
1 ให้โหนดแม่ชี้ไปยังโหนดลูกคนโต
แล้วลบความสัมพันธ์ ระหว่างโหนดแม่
และโหนดลูกอื่นๆ
2 ให้มีความเชื่อมความสัมพันธ์กันระหว่างโหนดพี่น้อง
3 จับให้ทรีย่อยทางขวาเอียงลงมา 45องศา
การท่องไปในไบนารี่ทรีมีด้วยกัน3แบบคือ
1 การท่องไปแบบพรีออร์เดอร์
เป็นการเดินเข้าไปเยือนในโหนดต่างๆ
ในทรีด้วยวิธี NLR มีขั้นตอนการเดินดังต่อไปนี้
1) เยือนโหนดราก
2) ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
3) ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์
2 การท่องไปแบบอินออร์เดอร์
เป็นการเดินเข้าไปเยือนโหนดต่างๆ
ในทรีด้วยวิธี LNR
มีขั้นตอนการเดินดังต่อไปนี้
1) ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
2) เยือนโหนดราก
3) ท่องไปในทรีย่อยทางขวาแบบอืนออร์เดรอ์
3 การท่องไปแบบโพสต์ออร์เดอร์
เป็นการเดินเข้าไปเยือนโหนดต่างๆ
ในทรีด้วยวิธี LRN
มีขั้นตอนการเดินดังต่อไปนี้
1) ท่องไปในทรีย่อยทางซ้ายแบบโพสต์ออร์เดอร์
2) ท่องไปในทรีย่อยทางขวาแบบโพสต์ออร์เดอร์
3) เยือนโหนดราก

DTS-07 05/08/52

โครงสร้างข้อมูลของ Queue
เป็นโครงสร้างข้อมูลแบบเชิงเส้นหรือลิเนียร์ลิสต์
ซึ่งการเพิ่มข้อมูลจะทำการที่ปลายข้างหนึ่ง
เรียกว่าส่วนท้าย (rear) และการนำข้อมูลออก
จะกระทำที่ปลายอีกข้างหนึ่งซึ่งเรียกว่า ส่วนหน้า
หรือ (front)
ลักษณะการทำงานของคิวเป็นลักษณะของการเข้าก่อน
ออกก่อนหรือที่เรียกว่า FIFO (First In First Out)
--การนำข้อมูลที่อยู่ตอนต้นของคิวมาแสดง
เรียกว่า Queue Front แต่จะไม่ทำการเอาข้อมูลออกจากคิว
--การนำข้อมูลที่อยู่ตอนท้ายของคิวมาแสดง
จะเรียกว่า Queue Rear แต่ไม่ทำการเพิ่มข้อมูลเข้าไปในคิว
การแทนที่ข้อมูลของ Queue
สามารถทำได้มี 2 วิธี คือ
1. การแทนที่ข้อมูลของคิวแบบลิงค์ลิสต์
2. การแทนที่ข้อมูลของคิวแบบอะเรย์
การดำเนินการเกี่ยวกับคิว ได้แก่
1. Create Queue -- การจัดสรรหน่วยความจำให้แก่ Head Node
และค่า Pointer -- ทั้งสองตัวมีค่าเป็น null และค่าสมาชิกเป็น 0
2. Enqueue -- การเพิ่มข้อมูลเข้าไปในคิว
3. Dequeue -- การนำข้อมูลออกจากคิว
4. Queue Front -- การนำข้อมูลที่อยู่ตอนต้นของคิวมาแสดง
5. Queue Rear -- การนำข้อมูลที่อยู่ส่วนท้ายของคิวมาแสดง
6. Empty -- การตรวจสอบว่าคิวว่างหรือไม่
7. Full Queue -- การตรวจสอบว่าคิวเต็มหรือไม่
8. Queue Count -- การนับจำนวนสมาชิกที่อยู่ในคิว
9. Destroy Queue -- การลบข้อมูลทั้งหมดที่อยู่ในคิว
--การนำข้อมูลเข้าสู่คิว จะไม่นำเข้าในขณะที่คิวเต็มหรือไม่มีที่ว่าง
ถ้าพยายามนำข้อมูลเข้าจะเกิดการผิดพลาดที่เรียกว่า overflow
--การนำข้อมูลออกจากคิว จะไม่สามารถนำอะไรออกจากคิวที่ว่างได้
ถ้าพยายามจะเอาออกจะเกิดการผิดพลาดที่เรียกว่า underflow
--จุดเด่นของคิว
คิวสามารถจัดการการเข้า-ออกของข้อมูล
ใช้เก็บข้อมูลที่ต้องการจัดเรียงเป็นระบบ
โดยพิจารณาข้อมูลตามลำดับ
ในทำนอง ใครถึงก่อนมีสิทธิ์ได้ใช้ก่อน
จึงใช้ในการเรียงลำดับในการแบ่งปันทรัพยากร
ที่มีอยู่อย่างจำกัดในการทำงาน เช่น
การรอคิวการทำงานของเครื่องพิมพ์ในสำนักงาน เป็นต้น

DTS-06 29/07/52

การแทนที่ข้อมูลของสแตกแบบอะเรย์
คือการนำเอาอาร์เรย์เข้ามาใช้งานในการกำหนดโครงสร้าง
ซึ่งเป็นลักษณะเฉพาะตัวของอาร์เรย์เป็นโครงสร้างที่สามารถกำหนด
จองพื้นที่บนหน่วยความจำได้แน่นอนและสามารถเก็บข้อมูลที่เป็นชนิดเดียวกัน
ซึ่งจะเอาคุณสมบัตินี้มาใช้ในการกำหนดโครงสร้างและจัดเก็บข้อมูลในลักษณะ
สแตก
--โครงสร้างอาร์เรย์นั้นจะมีการจองพื้นที่ที่แน่นอน (stack) จึงจำเป็นต้องมีการ
กำหนดขนาดพื้นที่จัดเก็บข้อมูลสูงสุดให้เหมาะสมเมื่อมีการนำเอาข้อมูลเข้ามา
หลักการดำเนินการสำหรับแปลง infix เป็น postfix
1.พิจารณานิพจน์ infix หากเป็น operand ให้นำออกไปที่ผลลัพธ์
2.พิจารณานิพจน์ infix หากเป็น operator ให้นำมาเปรียบเทียบ
ความสำคัญ หากสแตกว่างไม่มีตัวดำเนินการให้ push ลงสแตก
ถ้ามีตัวดำเนินการอยู่ให้เปรียบเที่ยบความสำคัญ ถ้าตัวดำเนินการ
ที่เข้าไปใหม่มีความสำคัญน้อยกว่าให้ pop ตัวดำเนินการก่อนหน้า
ไปไว้ในผลลัพธ์แต่ถ้ามีความสำคัญมากกว่าก็ให้วางต่อไว้ในสแตก
สำหรับเครื่องหมาย +-*/ เรียกว่า operator
สำหรับตัวอักษร ABCD เรียกว่า operand