สรุปเรื่อง ทรี Tree (ต่อ) และเรื่อง กราฟ Graph
การท่องไปในไบนารีทรี
ปฏิบัติการที่สำคัญของในไบนารีทรี คือ
การท่องไปในไบนารีทรีเพื่อเข้าไปเยือนทุก ๆ
โหนดในทรี
ขั้นตอนการเยือนอย่างไรของโหนดที่ถูกเยือน
อาจเป็นโหนดแม่(แทนด้วย N)
ทรีย่อยทางซ้าย(แทนด้วย L)
หรือทรีย่อยทางขวา (แทนด้วย R)
1 การท่องไปแบบพรีออร์เดอร์
เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ
ในทรีด้วยวิธี NLR มีขั้นตอนการเดินดังต่อไปนี้
1 เยือนโหนดราก
2 ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
3 ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์
2 การท่องไปแบบอินออร์เดอร์
เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ
ในทรีด้วยวิธี LNR มีขั้นตอนการเดินดังต่อไปนี้
1 ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
2 เยือนโหนดราก
3 ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์
3 การท่องไปแบบโพสออร์เดอร์
เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ
ในทรีด้วยวิธี LRN มีขั้นตอนการเดินดังต่อไปนี้
1 ท่องไปในทรีย่อยทางซ้ายแบบโพสต์ออร์เดอร์
2 ท่องไปในทรีย่อยทางขวาแบบโพสต์ออร์เดอร์
3 เยือนโหนดราก
เอ็กซ์เพรสชั่นทรี (Expression Tree)
เป็นการนำเอาโครงสร้างทรีไปใช้เก็บนิพจน์
โดยแต่ละโหนดจะเก็บตัวดำเนินการ (Operator)
และตัวถูกดำเนินการ (Operand)
ซึ่งตัวถูกดำเนินการจะเก็บอยู่ที่โหนดใบ
ส่วนตัวดำเนินการจะเก็บอยู่ที่โหนดกิ่ง
แต่ต้องคำนึงถึงความสำคัญของเครื่องหมายตามลำดับด้วย คือ
-ฟังก์ชั่น
-วงเล็บ
-ยกกำลัง
-เครื่องหมายหน้าเลขจำนวน (unary)
-คูณ หรือ หาร
-บวก หรือ ลบ
-ถ้ามีเครื่องหมายที่ระดับเดียวกัน
ให้ทำจากซ้ายไปขวา
ไบนารีเซิร์ซทรี (Binary Search Tree)
เป็นไบนารี่ทรีที่มีคุณสมบัติที่ว่าทุก ๆ โหนด
ในทรี ค่าของโหนดรากมีค่ามากกว่าค่าของ
ทุกโหนดในทรีย่อยทางซ้าย และมีค่าน้อยกว่า
หรือเท่ากับค่าของทุกโหนดในทรีย่อยทางขวา
และในแต่ละทรีย่อยก็มี คุณสมบัติเช่นเดียวกัน
วิธีการดึงโหนดออก แยกได้ 3 วิธี
1 กรณีโหนดที่จะดึงออกเป็นโหนดใบ สามารถดึงได้เลย
เพราะไม่มีผลกระทบต่อโหนดอื่น ๆแล้วเป็นวิธีที่ง่ายที่สุด
2 กรณีโหนดที่ดึงออกมีเฉพาะทรีย่อยด้านซ้ายหรือ
ทรีย่อยด้านขวาเพียงด้านใดด้านหนึ่ง สามารถทำได้เหมือนวิธีแรก
เพียงให้โหนดแม่ของโหนดที่ต้องการดึงออกชี้ไปยังโหนดลูก
ของโหนดนั้นแทน
3 กรณีโหนดที่ต้องการดึงออกมีทั้งทรีย่อยด้านซ้ายและ
ทรีย่อยด้านขวา ต้องทำการเลือกว่าจะนำทรีย่อยด้านใด
มาแทนโหนดที่ถูกดึงออก
Graph (กราฟ)
เป็นโครงสร้างข้อมูลแบบไม่เชิงเส้น อีกชนิดหนึ่ง
กราฟเป็นโครงสร้างข้อมูลที่มีการนำไปใช้ในงาน
ที่เกี่ยวข้องกับการแก้ไขปัญหาที่ค่อนข้างซับซ้อน
จะประกอบไปด้วยกลุ่มของสิ่งสองสิ่ง คือ
1 โหนด (Node) หรือ เวอร์เทกซ์
2 เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (Edges)
โดยทั่ว ๆ ไป ในการเขียนกราฟเพื่อแสดง
ให้เห็นความสัมพันธ์ ของสิ่งที่เราสนใจแทนโหนด
ด้วย จุด หรือวงกลม ที่มีชื่อหรือข้อมูลกำกับ
เพื่อบอกความแตกต่างของแต่ละโหนด
ถ้าเป็นกราฟแบบมีทิศทางเส้นหรือเส้นโค้งต้องมี
หัวลูกศรกำกับทิศทางของความสัมพันธ์ด้วย
กราฟมี 2 ทิศทาง คือ
1 กราฟแบบไม่มีทิศทางเป็นเซตแบบจำกัด
ของโหนดและเอ็จ ลำดับของการเชื่อมต่อกัน
ไม่สำคัญ นั่นคือไม่มีโหนดใดเป็นโหนดแรก
หรือไม่ใมโหนดเริ่มต้น และไม่มีโหนดใดเป็นโหนดสิ้นสุด
2 กราฟแบบมีทิศทางเป็นเซตแบบจำกัดและเอ็จ
แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด
เอ็จมีทิศทางกำกับแสดงลำดับของการเชื่อมต่อกัน
โดยมีโหนดเริ่มต้น และโหนดสิ้นสุด
กราฟที่มีการเปลี่ยนแปลงตลอดเวลา
อาจจะใช้วิธีแอดจาเซนซีลิสต์
จัดเก็บกราฟด้วยการเก็บโหนดและพอยน์เตอร์
แต่ต่างกันตรงที่จะใช้ลิงค์ลิสต์แทนเพื่อความสะดวก
ในการเปลี่ยนแปลงและแก้ไข
การท่องไปในกราฟ
เป็นการไปเยือนโหนดในกราฟ ซึ่งแต่ละโหนดจะถูกเยือนเพียงครั้งเดียว
แต่กราฟนั้นมาหลายเส้นทางเมื่อเยือนแล้วต้องทำเครื่องหมายว่า
ได้เยือนเรียบร้อย
การท่องไปในกราฟมีด้วยกัน 2 แบบ คือ
1 การท่องแบบกว้าง เป็นการกำหนดโหนดที่จะเยือน
หรือโหนดเริ่มต้นแล้วทำการเยือนไปยังโหนดที่ใกล้เคียง
จนกระทั่งครบทุกโหนด
2 การท่องแบบลึก โดยกำหนดเริ่มต้นที่โหนดแรกแล้ว
เยือนโหนดถัดไปตามแนววิถีจนถึงปลายวิถี
แล้วย้อนกลับมาเพื่อเยือนโหนดอื่น ๆ ต่อไปจนครบทุกโหนด
ไม่มีความคิดเห็น:
แสดงความคิดเห็น