สรุปเนื้อหา
เรื่อง Tree และ Graph
เอ็กซ์เพรชชันทรี
เป็นการนำเอาโครงสร้างทรีไปใช้เก็บนิพจน์ทางคณิตศาสตร์โดยเป็นไบนารีทรี ซึ่งแต่ละโหนดเก็บตัวดำเนินการ (Operator) และตัวถูกดำเนินการ (Operand) ของนิพจน์คณิตศาสตร์นั้นๆไว้หรืออาจจะเก็บค่านิพจน์ทางตรรกะ (Logical Expression) นิพจน์เหล่านี้เมื่อแทนในทรต้องคำนึงลำดับขั้นตอนในการคำนวณตามความสำคัญของเครื่องหมายด้วยโดยมีความสำคัญตามลำดับดังนี้ฟังก์ชั่น,วงเล็บ,ยกกำลัง,เครื่องหมายหน้าเลขจำนวน Unary,คูณหรือหาร,บอกหรือลบ,ถ้ามีเครื่องหมายที่ระดับเดียวกันให้ทำจากซ้ายไปขวา
ไบนารีเซิร์ชทรี
เป็นไบนารีทรที่มีคุณสมบัติที่ว่าทุดๆโหนดในทรี ค่าของโหนดรากมีค่ามากกว่าค่าของทุกโหนดในทรีย่อยทางขวาและในแต่ละทรีย่อยก็มีคุณสมบัติเช่นเดียวกัน ปฎิบัติการในไบนารีทรี ปฎิบัติการเพิ่มโหนดเข้าหรือดึงโหนดออกจากไบนารีทรีค่อนข้างยุ่งยากกว่าปฎิบัติการในโครงสร้างอื่นๆเนื่องจากหลังปฎิบัติการเสร็จเรียบร้อยแล้วต้องคำนึงถึงความเป็นไบนารีเซิร์ชทรีของทรีนั้น
กราฟ (Graph)เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้นที่ประกอบด้วย
1. โหนด (N0des)
2. เส้นเชื่อมระหว่างโหนด
การแทนที่ในหน่วยความจำ
ในการปฎิบัติการกับโครงสร้างกราฟ สิ่งที่ต้องการจัดกเก็บจากกราๆโดยทั่วไปก็คือ เอ็จ ซึ่งเป็นเส้นเชื่อมระหว่างโหนดสองโหนด มีวิธีการจัดเก็บหลายวิธี วิธีที่ง่ายตรงไปตรงมาคือการเก็บเอ็จในแถวลำดับ 2 มิติ
การท่องไปในกราฟ
การท่องไปในกราฟ คือ กระบวนการเข้าไปเยือนในโหนดในกราฟ โดยมีหลักในการทำงานคือ แต่ละโหนดจะถูกเยือนเพียงครั้งเดียว สำหรับการท่องไปในทรีเพื่อเยือนแต่ละโหนดนั้นจะมีเส้นทางเดียว แต่ในกราฟระหว่างโหนดอาจมีหลายเส้นทาง
1. การท่องแบบกว้าง (Breadth First Traversal)วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนดอื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับจนกระทั่งเยือนหมดทุกโหนดในกราฟ
2. การท่องแบบลึก (Depth First Traversal)การทำงานคล้ายกับการท่องทีละระดับของทรี โดยกำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตามแนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น จากนั้นย้อนกลับ(backtrack) ตามแนววิถีเดิมนั้น จนกระทั่งสามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือนโหนดอื่น ๆ ต่อไปจนครบทุกโหนด
ไม่มีความคิดเห็น:
แสดงความคิดเห็น