Please enable JavaScript.
Coggle requires JavaScript to display documents.
สรุปสาระสำคัญที่ 6 ต้นไม้ (Trees) (ความสัมพันธ์ของจุดต่างๆ ในต้นไม้มีราก…
สรุปสาระสำคัญที่ 6 ต้นไม้ (Trees)
กราฟแบบไม่มีทิศทางที่เชื่อมต่อกัน (connected
undirected graph) ซึ่งไม่มีวงจรแบบง่าย
ต้นไม้ทุกต้นจะไม่มี
วงจรแบบง่าย
เส้นเชื่อมหลายเส้นระหว่างคู่ของจุด
ลูป
การแวะผ่านจุดในต้นไม้
นิยามที่ 6.5
ให้ T เป็นต้นไม้มีรากแบบลําดับที่มีราก คือ r
ถ้า T มีแค่ r จะได้ว่า r คือ inorder traversal ของ T
แต่ถ้ามี T1, T2, . . ., Tn เป็นต้นไม้ย่อยที่ต่ออยู่กับ r โดยเรียงจากซ้ายไปขวาของT จะได้ว่า inorder traversal จะเริ่มจากการทํา inorder traversal ที่ T1 แล้วจึงกลับมาแวะจุด r จากนั้นจึงแวะไปที่ T2 แบบ inorder และต่อไปเรื่อยๆ จนถึง Tn
นิยามที่ 6.4
ให้ T เป็นต้นไม้มีรากแบบลําดับที่มีราก คือ r
ถ้า T มีแค่ r จะได้ว่า r คือ preorder traversal ของ T
แต่ถ้ามี T1, T2, . . ., Tn เป็นต้นไม้ย่อยที่ต่ออยู่กับ r โดยเรียงจากซ้ายไปขวาของT จะได้ว่า preorder traversal จะเริ่มจากจุด r ไปยัง T1 ในลักษณะ preorderจากนั้นไปยัง T2 ในลักษณะ preorder และต่อไปเรื่อยๆ จนถึง Tn
นิยามที่ 6.6
ให้ T เป็นต้นไม้มีรากแบบลําดับที่มีราก คือ r
ถ้า T มีแค่ r จะได้ว่า r คือ postorder traversal ของ T
แต่ถ้ามี T1, T2, . . ., Tn เป็นต้นไม้ย่อยที่ต่ออยู่กับ r โดยเรียงจากซ้ายไปขวาของT จะได้ว่า postorder traversal จะเริ่มจากการทํา postorder traversal ที่ T1จากนั้นไปที่ T2 ในลักษณะ postorder ต่อไปเรื่อยๆ จนถึง Tn และปิดท้ายด้วย r
ต้นไม้มีราก (Rooted tree)
ต้นไม้ที่มีการกําหนดจุดๆ หนึ่งเป็นราก
และทุกๆ เส้นเชื่อมพุ่งไปในทิศทางที่ออกจากราก
เลขระดับ (Level number)
ความยาวของทางเดินจากรากไปยังจุดนั้นๆ
รากจะอยู่ในระดับ (level) ที่ 0
จุดที่ต่ออยู่กับรากจะอยู่ในระดับที่ 1
จุดที่ต่ออยู่กับจุดในระดับ 1 จะอยู่ในระดับที่ 2
ความสูง (Height) ของต้นไม้
เลขระดับที่มีค่ามากที่สุดของจุดในต้นไม้นั้น
ความสัมพันธ์ของจุดต่างๆ ในต้นไม้มีราก
จุดพ่อ/แม่ (Parent) ของ v คือ จุด u ซึ่ง unique และมีเส้นเชื่อมโดยตรงจาก u
มายัง v
ถ้าจุด u เป็นจุดระดับพ่อ/แม่ของ v จะเรียกจุด v ว่าจุดลูก (Child) ของ u
จุด 2 จุดใดๆ ที่มีพ่อ/แม่เดียวกันจะเป็นพี่น้องกัน (Siblings)
บรรพบุรุษ (Ancestors) ของจุดหนึ่งที่ไม่ใช่ราก คือ จุดอื่นๆ ที่อยู่ในทางเดินจา
กรากมายังจุดนั้นๆ (ยกเว้นจุดนั้นเองและราก)
ความสัมพันธ์ของจุดต่างๆ ในต้นไม้มีราก
ลูกหลาน (Descendants) ของจุด v คือ จุดอื่นๆ ที่มี v เป็นบรรพบุรุษ
ใบ (Leaf) คือ จุดใดๆ ในต้นไม้ที่ไม่มีลูก
จุดภายใน (Internal vertices) คือ จุดใดๆ ในต้นไม้ที่มีลูก
ต้นไม้ย่อย (Subtree) ที่มีจุด v เป็นราก คือ กราฟย่อยของต้นไม้ที่ประกอ
บด้วยจุด v และลูกหลานทั้งหมดของจุด v
นิยามที่ 6.3
ต้นไม้มีรากจะเรียกว่าเป็น ต้นไม้แบบ m ภาค (m-ary tree) ถ้าทุกๆ จุดภายในมีลูกไม่เกิน m
และจะเรียกว่าเป็น ต้นไม้แบบเต็ม m ภาค (full m-ary tree) ถ้าทุกๆ จุดภายในมีลูกเท่ากับ m เท่านั้น
ในกรณีที่ m = 2 จะเรียกว่า “ต้นไม้แบบทวิภาค (binary tree)”
กรณีที่ลูกของแต่ละจุดภายใน เรียงลําดับจากซ้ายไปขวาดังรูป A จะเรียกต้น
ไม้ดังกล่าวว่า “ต้นไม้มีรากแบบลําดับ (Ordered Rooted Tree)”
Infix, Prefix, and Postfix Notation
รูปแบบการเขียนนิพจน์ทางคณิตศาสตร์โดยทั่วไปจะอยู่ในรูปของ infixnotation ซึ่งมีวงเล็บประกอบ เช่น (a+b) × c
Infix form สามารถแสดงโดยใช้ต้นไม้มีรากหนึ่งต้น เรียกว่า “ต้นไม้นิพจน์(Expression Tree)”
การแปลงจาก Infix form เป็น prefix และ postfix form
Infix ---> Prefix
Use preorder traversal
Infix ---> Postfix
Use postorder traversal
ต้นไม้แบบแผ่
ให้ G เป็นกราฟแบบง่าย ต้นไม้แบบแผ่ของ G คือ กราฟย่อย
ของ G ที่เป็นต้นไม้ซึ่งประกอบด้วยทุกๆ จุดของ G
อัลกอริทึมสําหรับการสร้างต้นไม้แบบแผ่
การค้นตามความลึก (Depth-First Search) หรือการย้อนรอย (Backtracking)
การค้นตามความกว้าง (Breadth-First Search)
ต้นไม้แบบแผ่ที่เล็กที่สุด
นิยามที่ 6.8 : ต้นไม้แบบแผ่ที่เล็กที่สุดในกราฟแบบมีน้ําหนักที่เชื่อมต่อกัน คือ ต้นไม้แบบแผ่ที่มีผลรวมของน้ําหนักของเส้นเชื่อมที่น้อยที่สุด
Prim's Algorithm
Kruskal's Algorithm
เปรียบเทียบระหว่าง Prim's algorithm และ Kruskal's algorithm
ในขณะที่ Kruskal's algorithm จะพิจารณาเลือกเส้นเชื่อมที่มีน้ําหนักน้อยที่สุดและไม่ทําให้เกิดวงจรแบบง่าย โดยไม่สนใจว่าจะเชื่อมต่ออยู่กับจุดในต้นไม้แบบแผ่หรือไม่
กรณีของ Prim's algorithm จะเลือกเส้นเชื่อมที่มีน้ําหนักน้อยที่สุดซึ่งเชื่อมต่อกับจุดที่อยู่ในต้นไม้แบบแผ่และไม่ทําให้เกิดวงจรแบบง่าย
