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