Please enable JavaScript.

Coggle requires JavaScript to display documents.

UNIT 06 ต้นไม้(Trees) (Module 2 (Infix, Prefix, and Postfix Notation…

- - - - Inorder Traversal
        
        นิยามที่ 6.5
        
        ให้ T เป็นต้นไม้มีรากแบบลำดับที่มีราก คือ r
        
        ถ้า T มีแค่ r จะได้ว่า r คือ inorder traversal ของ T
        
        แต่ถ้ามี T1, T2, . . ., Tn เป็นต้นไม้ย่อยที่ต่ออยู่กับ r โดยเรียงจากซ้ายไปขวาของT จะได้ว่า inorder traversal จะเริ่มจากการทำ inorder traversal ที่ T1 แล้วจึงกลับมาแวะจุด r จากนั้นจึงแวะไปที่ T2 แบบ inorder และต่อไปเรื่อยๆ จนถึงTn
      - Postorder Traversal
        
        นิยามที่ 6.6
        
        ให้ T เป็นต้นไม้มีรากแบบลำดับที่มีราก คือ r
        
        ถ้า T มีแค่ r จะได้ว่า r คือ postorder traversal ของ T
        
        แต่ถ้ามี T1, T2, . . ., Tn เป็นต้นไม้ย่อยที่ต่ออยู่กับ r โดยเรียงจากซ้ายไปขวาของT จะได้ว่า postorder traversal จะเริ่มจากการทำ postorder traversal ที่ T1จากนั้นไปที่ T2 ในลักษณะ postorder ต่อไปเรื่อยๆ จนถึง Tn และปิดท้าpด้วย r
      - Preorder Traversal
        
        นิยามที่ 6.4
        
        ให้ T เป็นต้นไม้มีรากแบบลำดับที่มีราก คือ r
        
        ถ้า T มีแค่ r จะได้ว่า r คือ preorder traversal ของ T
        
        แต่ถ้ามี T1, T2, . . ., Tn เป็นต้นไม้ย่อยที่ต่ออยู่กับ r โดยเรียงจากซ้ายไปขวาของT จะได้ว่า preorder traversal จะเริ่มจากจุด r ไปยัง T1 ในลักษณะ preorderจากนั้นไปยัง T2 ในลักษณะ preorder และต่อไปเรื่อยๆ จนถึง Tn
- - - - ตัวอย่างของเส้นทางการขนส่งสินค้าของบริษัทแห่งหนึ่ง
        
        ทําอย่างไรจึงจะสามารถลดเส้นทางการขนส่งลงให้เหลือเส้นทางน้อยที่สุด โดย
        ยังคงเดินทางไปได้ทุกจังหวัด?
        
        ตัวอย่างต้นไม้แบบแผ่ของเส้นทางการขนส่ง
    - - Depth-First Search
        
        ตัวอย่างที่ 12 จงหาต้นไม้แบบแผ่ของกราฟต่อไปนี้ โดยใช้อัลกอริทึมแบบ
        Depth-First Search
      - Breadth-First Search
        
        ตัวอย่างที่ 13 จงหาต้นไม้แบบแผ่ของกราฟต่อไปนี้ โดยใช้อัลกอริทึมแบบ
        Breadth-First Search
  - - - Prim's Algorithm
      - Kruskal's Algorithm
- - - - ต้นไม้คือ กราฟแบบไม่มีทิศทางที่เชื่อมต่อกัน (connected undirected graph) ซึ่งไม่มีวงจรแบบ
        ง่าย
      - ต้นไม้ทุกต้นจะไม่มี
        :check:วงจรแบบง่าย
        :check:เส้นเชื่อมหลายเส้นระหว่างคู่ของจุด
        :check:ลูป
    - - ต้นไม้มีราก (Rooted tree) คือ ต้นไม้ที่มีการกำหนดจุดๆ หนึ่งเป็นรากและทุกๆ
        เส้นเชื่อมพุ่งไปในทิศทางที่ออกจากราก
      - เลขระดับ (Level number) คือ ความยาวของทางเดินจากรากไปยังจุดนั้นๆ
        :check:รากจะอยู่ในระดับ (level) ที่ 0
        :check:จุดที่ต่ออยู่กับรากจะอยู่ในระดับที่ 1
        :check:จุดที่ต่ออยู่กับจุดในระดับ 1 จะอยู่ในระดับที่ 2
      - ความสูง (Height) ของต้นไม้จะมีค่าเท่ากับเลขระดับที่มีค่ามากที่สุดของจุดในต้นไม้นั้น
    - - ต้นไม้มีรากจะเรียกว่าเป็น ต้นไม้แบบ m ภาค (m-ary tree) ถ้าทุกๆ จุดภายในมีลูกไม่เกิน m
        และจะเรียกว่าเป็น ต้นไม้แบบเต็ม m ภาค (full m-ary tree) ถ้าทุกๆ จุด
        ภายในมีลูกเท่ากับ m เท่านั้น
        
        ความสัมพันธ์ของจุดต่างๆ ในต้นไม้มีราก
        
        จุดพ่อ/แม่ (Parent) ของ v คือ จุด u ซึ่ง unique และมีเส้นเชื่อมโดยตรงจาก u
        มายัง v
        
        ถ้าจุด u เป็นจุดระดับพ่อ/แม่ของ v จะเรียกจุด v ว่าจุดลูก (Child) ของ u
        
        จุด 2 จุดใดๆ ที่มีพ่อ/แม่เดียวกันจะเป็นพี่น้องกัน (Siblings)
        
        บรรพบุรุษ (Ancestors) ของจุดหนึ่งที่ไม่ใช่ราก คือ จุดอื่นๆ ที่อยู่ในทางเดินจาก
        รากมายังจุดนั้นๆ (ยกเว้นจุดนั้นเองและราก)
        
        ลูกหลาน (Descendants) ของจุด v คือ จุดอื่นๆ ที่มี v เป็นบรรพบุรุษ
        
        ใบ (Leaf) คือ จุดใดๆ ในต้นไม้ที่ไม่มีลูก
        
        จุดภายใน (Internal vertices) คือ จุดใดๆ ในต้นไม้ที่มีลูก
        
        ต้นไม้ย่อย (Subtree) ที่มีจุด v เป็นราก คือ กราฟย่อยของต้นไม้ที่ประกอบด้วย
        จุด v และลูกหลานทั้งหมดของจุด v
      - กรณีที่ m = 2 จะเรียกว่า “ต้นไม้แบบทวิภาค (binary tree)”
    - - ทฤษฎีที่ 1 ต้นไม้ที่มีจำนวนจุด n จุดจะมีจำนวนเส้นเชื่อมเท่ากับ n-1 เส้น
      - ทฤษฎีที่ 2 ต้นไม้แบบเต็ม m ภาคซึ่งมีจุดภายในจำนวน i จุดจะมีจำนวนจุดทั้งหมด n = mi + 1 จุด
      - ทฤษฎีที่ 3 ต้นไม้แบบเต็ม m ภาคซึ่งมีจำนวนจุดทั้งหมดเท่ากับ n จำนวนจุดภายในเท่ากับ i และมีจำนวนจุดที่เป็นใบเท่ากับ l
      - ทฤษฎีที่ 4 ต้นไม้แบบ m ภาคซึ่งมีความสูง h จะเป็นต้นไม้แบบสมดุล
        (balanced tree) ถ้าทุกใบอยู่ที่ระดับ h หรือ h–1
      - ทฤษฎีที่ 5 ต้นไม้แบบ m ภาคซึ่งมีความสูง h จะมีจำนวนใบได้มากที่สุด mh ใบ