ผู้เขียน หัวข้อ: ต้นไม้ สัตว์เลี้ยง :P  (อ่าน 7 ครั้ง)

0 สมาชิก และ 1 บุคคลทั่วไป กำลังดูหัวข้อนี้

ตุลาคม 06, 2018, 08:37:45 AM
  • Hero Member
  • *****
  • กระทู้: 1038
    • ดูรายละเอียด

ต้นไม้ (อังกฤษ: Tree) เป็น แบบจำ พวกข้อมูลนามธรรม ชนิดหนึ่ง มีลักษณะการจัดเรียงเป็นแขนงแตกกิ่งก้านสาขาออกไป จะไม่มีวงวน (loop) โยงในสมาชิกตัวต่างๆโดยสมาชิกจะถูกเก็บเอาไว้ในจำพวกข้อมูลจำพวกวัตถุ (Object) หรือองค์ประกอบ (Structure) เรียกว่าเงื่อน (node) ซึ่งจะมีตัวแปรซึ่งเก็บเนื้อเก็บตัวชี้ (Pointer) ไปยังเงื่อนอื่นๆได้ต้นไม้ถูกใช้เพื่อการจัดแจงข้อมูลที่เทียบกันได้ (comparable) อย่างเร็วเป็นต้นว่า จำนวน หรือ การจัดเรียงลำดับความสำคัญของข้อมูล ตัวอย่างเช่น การคำนวณที่มีวงเล็บ เป็นต้นเงื่อน (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) เป็นต้นไม้ย่อยที่ใช้สมาชิกของต้นไม้ที่พวกเราพินิจ ไปเป็นรากทำให้ เงื่อนลูกเงื่อนหลานที่อยู่ใต้สมาชิกตัวนั้นเปลี่ยนเป็นสมาชิกของต้นไม้ย่อยไปด้วย