ส่วนประกอบของต้นไม้
- ปม (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) หมายถึงต้นไม้ย่อยที่ใช้สมาชิกของต้นไม้ที่เราพิจารณา ไปเป็นรากส่งผลให้ ปมลูกปมหลานที่อยู่ใต้สมาชิกตัวนั้นกลายเป็นสมาชิกของต้นไม้ย่อยไปด้วย
ไม่มีความคิดเห็น:
แสดงความคิดเห็น