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