วันพฤหัสบดีที่ 31 มกราคม พ.ศ. 2556



ส่วนประกอบของต้นไม้

  • ปม (node) หมายถึงสิ่งที่เก็บสมาชิกของต้นไม้
  • ราก (root) หมายถึงปมที่เราใช้เริ่มค้นหาภายในต้นไม้ ถ้าเป็น null หมายถึงต้นไม้ว่าง (empty tree)
  • ปมลูก (child node) หมายถึงปมที่แตกออกมาจากของปมดังกล่าว ส่วนปมที่ปมดังกล่าวแตกมาเรียกว่า ปมพ่อ (parent node) และเรียกปมพ่อของปมพ่อว่า ปมปู่ (grandparent node) และเรียกตามลำดับการนับญาติฝ่ายพ่อไปเรื่อยๆ ส่วนปมลูกของปมลูกก็จะเป็นปมหลาน (grandchild node) ไปเรื่อยๆ ตามลำดับการเรียกญาติฝ่ายลูก
  • ปมที่มีปมพ่อเป็นปมเดียวกันเรียกว่า ปมพี่น้อง (sibling node)
  • ปมที่มี m ลูก เราจะเรียกว่า ปมแบบ m (m-type node)
  • ใบ (leaf node) หมายถึงปมที่ไม่มีปมลูก
  • การเขียนต้นไม้มักเขียนปมรากอยู่ข้างบน และเขียนแตกแขนงลงมาให้ปมใบอยู่ข้างล่าง
  • ความลึกของปม (node depth) หมายถึงจำนวนครั้งของความสัมพันธ์เชิงพ่อ-ลูก ระหว่าง ปมรากถึงปมใดๆ
  • ความสูง (tree height) หมายถึงความลึกของใบที่ลึกที่สุด สำหรับต้นไม้ที่มีแต่รากจะสูง 0 และต้นไม้ว่างอาจตั้งได้ว่าสูง -1
  • ต้นไม้ย่อย (subtree) หมายถึงต้นไม้ย่อยที่ใช้สมาชิกของต้นไม้ที่เราพิจารณา ไปเป็นรากส่งผลให้ ปมลูกปมหลานที่อยู่ใต้สมาชิกตัวนั้นกลายเป็นสมาชิกของต้นไม้ย่อยไปด้ว



ไม่มีความคิดเห็น:

แสดงความคิดเห็น

แสดงความคิดเห็น