Please enable JavaScript.

Coggle requires JavaScript to display documents.

ต้นไม้ (Trees) (บทนำ (คุณสมบัติของต้นไม้ (ทฤษฎีที่ 3 ต้นไม้แบบเต็ม m…

- - - - หรืออาจจะกล่าวว่า กราฟแบบไม่มีทิศทางใดๆ จะเป็นต้นไม้เมื่อมีทางเดินเพียง 1 ทาง ระหว่างคู่ของจุดใดๆ ในกราฟ
  - - - เช่นรากจะอยู่ในระดับ (level) ที่ 0, จุดที่ต่ออยู่กับรากจะอยู่ในระดับที่ 1, จุดที่ต่ออยู่กับจุดในระดับ 1 จะอยู่ในระดับที่ 2
    - - จุดพ่อ/แม่ (Parent) ของ v คือ จุด u ซึ่ง unique และมีเส้นเชื่อมโดยตรงจาก u มายัง v
      - ถ้าจุด u เป็นจุดระดับพ่อ/แม่ของ v จะเรียกจุด v ว่าจุดลูก (Child) ของ u
      - จุด 2 จุดใดๆ ที่มีพ่อ/แม่เดียวกันจะเป็นพี่น้องกัน (Siblings)
      - ลูกหลาน (Descendants) ของจุด v คือ จุดอื่นๆ ที่มี v เป็นบรรพบุรุษ
      - ใบ (Leaf) คือ จุดใดๆ ในต้นไม้ที่ไม่มีลูก
      - จุดภายใน (Internal vertices) คือ จุดใดๆ ในต้นไม้ที่มีลูก
      - ต้นไม้ย่อย (Subtree) ที่มีจุด v เป็นราก คือ กราฟย่อยของต้นไม้ที่ประกอบด้วยจุด v และลูกหลานทั้งหมดของจุด v
  - - - ต้นไม้ที่มีจำนวนจุดทั้งหมดเท่ากับ n จะมี i = (n-1)/m และ
        l = [(m-1)n + 1]/m
      - ต้นไม้ที่มีจำนวนจุดภายในเท่ากับ i จะมี n = mi + 1 และ l = (m-1)i + 1
      - ต้นไม้ที่มีจำนวนใบเท่ากับ l จะมี n = (ml – 1)/(m – 1) และ i = (l -1)/(m -1)
- - - - Prim's algorithm จะเลือกเส้นเชื่อมที่มีน้ำหนักน้อยที่สุดซึ่งเชื่อมต่อ กับจุดที่อยู่ในต้นไม้แบบแผ่และไม่ทำให้เกิดวงจรแบบง่าย
      - Kruskal's algorithm จะเลือกเส้นเชื่อมที่มีน้ำหนักน้อยที่สุดและไม่ทำให้เกิดวงจรแบบง่าย โดยไม่สนใจว่าจะเชื่อมต่ออยู่กับจุดในต้นไม้แบบแผ่หรือไม่
- - - - เนื่องจากการแสดงด้วย prefix notation จะทำให้
        เกิดความสับสนน้อยกว่าและสามารถที่จะประมวลผลได้ง่ายเพราะไม่ต้อง สแกนกลับไปกลับมา นิยมใช้กันมากในสาขาวิทยาการคอมพิวเตอร์ เช่นเดียวกับpostfix notation
        
        prefix form : × + abc
      - การแปลงจาก Infix form เป็น prefix form
        
        Use preorder traversal
    - - เนื่องจากการแสดงด้วย postfix notation จะทำให้
        เกิดความสับสนน้อยกว่าและสามารถที่จะประมวลผลได้ง่ายเพราะไม่ต้อง สแกนกลับไปกลับมา นิยมใช้กันมากในสาขาวิทยาการคอมพิวเตอร์ เช่นเดียวกับ prefix notation
        
        postfix form : ab + c ×
      - การแปลงจาก Infix form เป็น postfix form
        
        Use postorder traversal
    - - รูปแบบการเขียนนิพจน์ทางคณิตศาสตร์โดยทั่วไปจะอยู่ในรูปของ infix notation ซึ่งมีวงเล็บประกอบ เช่น (a+b) × c
      - Infix form สามารถแสดงโดยใช้ต้นไม้มีรากหนึ่งต้น เรียกว่า “ต้นไม้นิพจน์ (Expression Tree)”
  - - - นิยามที่ 6.4
        
        ให้ T เป็นต้นไม้มีรากแบบลำดับที่มีราก คือ r
        
        ถ้า T มีแค่ r จะได้ว่า r คือ preorder traversal ของ T
        
        แต่ถ้ามี T1, T2, . . ., Tn เป็นต้นไม้ย่อยที่ต่ออยู่กับ r โดยเรียงจากซ้ายไปขวาของ T จะได้ว่า preorder traversal จะเริ่มจากจุด r ไปยัง T1 ในลักษณะ preorder จากนั้นไปยัง T2 ในลักษณะ preorder และต่อไปเรื่อยๆ จนถึง Tn
    - - นิยามที่ 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.6
        
        ให้ T เป็นต้นไม้มีรากแบบลำดับที่มีราก คือ r
        
        ถ้า T มีแค่ r จะได้ว่า r คือ postorder traversal ของ T
        
        แต่ถ้ามี T1, T2, . . ., Tn เป็นต้นไม้ย่อยที่ต่ออยู่กับ r โดยเรียงจากซ้ายไปขวาของ T จะได้ว่า postorder traversal จะเริ่มจากการทำ postorder traversal ที่ T1 จากนั้นไปที่ T2 ในลักษณะ postorder ต่อไปเรื่อยๆ จนถึง Tn และปิดท้ายด้วย r