ในวิทยาการคอมพิวเตอร์ต้นไม้เป็นชนิดข้อมูลนามธรรมที่ ใช้กันอย่างแพร่หลาย ซึ่งแสดงถึงโครงสร้างต้นไม้ แบบลำดับชั้น ที่มีชุดของโหนด ที่เชื่อมต่อกัน แต่ละโหนดในต้นไม้สามารถเชื่อมต่อกับลูกได้หลายตัว (ขึ้นอยู่กับชนิดของต้นไม้) แต่ต้องเชื่อมต่อกับผู้ปกครองเพียงตัวเดียวเท่านั้น^{[ 1 ] [ 2 ]}ยกเว้น โหนด รากซึ่งไม่มีผู้ปกครอง (กล่าวคือ โหนดรากเป็นโหนดบนสุดในลำดับชั้นของต้นไม้) ข้อจำกัดเหล่านี้หมายความว่าไม่มีวงจรหรือ "วงวน" (ไม่มีโหนดใดสามารถเป็นบรรพบุรุษของตัวเองได้) และยังหมายความว่าลูกแต่ละตัวสามารถถือได้ว่าเป็นโหนดรากของต้นไม้ย่อยของตัวเอง ทำให้การเรียกซ้ำเป็นเทคนิคที่มีประโยชน์สำหรับการท่องต้นไม้ในทางตรงกันข้ามกับโครงสร้างข้อมูลเชิงเส้นต้นไม้หลายต้นไม่สามารถแสดงด้วยความสัมพันธ์ระหว่างโหนดที่อยู่ติดกัน (โหนดผู้ปกครองและลูกของโหนดที่กำลังพิจารณา หากมีอยู่) ในเส้นตรงเส้นเดียว (เรียกว่าขอบหรือลิงก์ระหว่างสองโหนดที่อยู่ติดกัน)

ต้นไม้ไบนารีเป็นชนิดข้อมูลที่ใช้กันทั่วไป ซึ่งจำกัดจำนวนลูกของแต่ละโหนดแม่ไว้ไม่เกินสองโหนด เมื่อระบุลำดับของลูกแล้ว โครงสร้างข้อมูลนี้จะสอดคล้องกับต้นไม้เรียงลำดับในทฤษฎีกราฟค่าหรือตัวชี้ไปยังข้อมูลอื่นอาจเชื่อมโยงกับทุกโหนดในต้นไม้ หรือบางครั้งอาจเชื่อมโยงกับโหนดใบ เท่านั้น ซึ่งไม่มีโหนดลูก

ประเภทข้อมูลนามธรรม ( ADT) สามารถแสดงได้หลายวิธี รวมถึงรายการของโหนดแม่ที่มีตัวชี้ไปยังโหนดลูก รายการของโหนดลูกที่มีตัวชี้ไปยังโหนดแม่ หรือรายการของโหนดและรายการความสัมพันธ์ระหว่างโหนดแม่และโหนดลูกแยกต่างหาก ( รายการความสัมพันธ์แบบประชิด ชนิดพิเศษ ) นอกจากนี้ การแสดงผลอาจซับซ้อนกว่านั้นได้ เช่น การใช้ดัชนีหรือรายการบรรพบุรุษเพื่อเพิ่มประสิทธิภาพ

ต้นไม้ที่ใช้ในทางด้านคอมพิวเตอร์นั้นมีความคล้ายคลึงกัน แต่ก็อาจแตกต่างจากโครงสร้างทางคณิตศาสตร์ของต้นไม้ในทฤษฎีกราฟต้นไม้ในทฤษฎีเซตและต้นไม้ในทฤษฎีเซตเชิงพรรณนาได้

โหนดคือโครงสร้างที่อาจประกอบด้วยข้อมูลและการเชื่อมต่อกับโหนดอื่นๆ ซึ่งบางครั้งเรียกว่าขอบหรือลิงก์แต่ละโหนดในต้นไม้จะมีโหนดลูก ตั้งแต่ศูนย์โหนดขึ้นไป ซึ่งอยู่ด้านล่างของ โหนดนั้นในต้นไม้ (ตามธรรมเนียม ต้นไม้จะถูกวาดโดยให้ลูกหลานอยู่ด้านล่าง) โหนดที่มีโหนดลูกเรียกว่าโหนดแม่ ของโหนดลูกนั้น (หรือโหนดเหนือกว่า ) โหนดทั้งหมดมีโหนดแม่เพียงหนึ่งเดียว ยกเว้นโหนดราก บนสุด ซึ่งไม่มีโหนดแม่ โหนดอาจมีโหนดบรรพบุรุษ หลายโหนด เช่น โหนดแม่ของโหนดแม่ โหนดลูกที่มีโหนดแม่เดียวกันเรียก ว่า โหนดพี่น้องโดยทั่วไปแล้ว โหนดพี่น้องจะมีลำดับ โดยโหนดแรกมักจะถูกวาดไว้ทางซ้าย บางนิยามอนุญาตให้ต้นไม้ไม่มีโหนดเลย ซึ่งในกรณีนี้เรียกว่าต้นไม้ว่างเปล่า

โหนดภายใน ( หรือเรียก สั้นๆ ว่า โหนดในหรือโหนดสาขา ) คือโหนดใดๆ ในต้นไม้ที่มีโหนดลูก ในทำนองเดียวกันโหนดภายนอก (หรือเรียกสั้นๆ ว่าโหนดนอกโหนดใบหรือโหนดปลาย ) คือโหนดใดๆ ที่ไม่มีโหนดลูก

ความสูงของโหนดคือความยาวของเส้นทางที่ยาวที่สุดจากโหนดนั้นลงไปยังโหนดใบ ความสูงของโหนดรากคือความสูงของต้นไม้ ความลึกของโหนดคือความยาวของเส้นทางไปยังโหนดราก (เช่นเส้นทางราก ) ดังนั้น โหนดรากจึงมีความลึกเป็นศูนย์ โหนดใบมีความสูงเป็นศูนย์ และต้นไม้ที่มีเพียงโหนดเดียว (จึงมีทั้งโหนดรากและโหนดใบ) จะมีความลึกและความสูงเป็นศูนย์ ตามธรรมเนียมแล้ว ต้นไม้ว่างเปล่า (ต้นไม้ที่ไม่มีโหนด หากอนุญาต) จะมีความสูงเท่ากับ -1

แต่ละโหนดที่ไม่ใช่โหนดรากสามารถถือเป็นโหนดรากของซับทรี ของตัวเอง ซึ่งรวมถึงโหนดนั้นและลูกหลานทั้งหมด^{[ a ] ​​[ 3 ]}

คำศัพท์อื่นๆ ที่ใช้เกี่ยวกับต้นไม้:

เพื่อนบ้าน

พ่อแม่หรือลูก

บรรพบุรุษ

โหนดที่สามารถเข้าถึงได้โดยการดำเนินการซ้ำๆ จากโหนดลูกไปยังโหนดแม่

ลูกหลาน

โหนดที่สามารถเข้าถึงได้โดยการดำเนินการซ้ำๆ จากโหนดแม่ไปยังโหนดลูก เรียกอีกอย่างว่าโหนดลูกย่อย (subchild )

ระดับ

สำหรับโหนดที่กำหนด จำนวนลูกของโหนดนั้น โหนดใบตามนิยามจะมีดีกรีเป็นศูนย์

ระดับของต้นไม้

ระดับของต้นไม้ คือ ระดับสูงสุดของโหนดในต้นไม้นั้น

ระยะทาง

จำนวนขอบตามเส้นทางที่สั้นที่สุดระหว่างสองโหนด

ระดับ

ระดับของโหนดคือจำนวนขอบตามเส้นทางเฉพาะระหว่างโหนดนั้นกับโหนดราก^{[ 4 ]}ซึ่งเหมือนกับระดับความลึก

ความกว้าง

จำนวนโหนดในแต่ละระดับ

ความกว้าง

จำนวนใบไม้

ต้นไม้สมบูรณ์

ต้นไม้ที่มีทุกชั้นสมบูรณ์ ยกเว้นชั้นสุดท้าย

ป่า

กลุ่มของต้นไม้ที่ไม่เกี่ยวข้องกันหนึ่งต้นขึ้นไป

ต้นไม้ที่เรียงลำดับ

โครงสร้างต้นไม้แบบมีราก ซึ่งมีการกำหนดลำดับสำหรับลูกของแต่ละจุดยอด

ขนาดของต้นไม้

จำนวนโหนดในต้นไม้

• การระบุรายการทั้งหมด
• การแจกแจงส่วนต่างๆ ของต้นไม้
• กำลังค้นหาสินค้า
• การเพิ่มรายการใหม่ในตำแหน่งที่กำหนดบนโครงสร้างต้นไม้
• การลบรายการ
• การตัดแต่งกิ่ง : การตัดส่วนใดส่วนหนึ่งของต้นไม้ทิ้งไป
• การต่อกิ่ง : การเพิ่มส่วนทั้งกิ่งให้กับต้นไม้
• การค้นหารากของโหนดใดๆ
• การค้นหาบรรพบุรุษร่วมที่ต่ำที่สุดของโหนดสองโหนด

การก้าวผ่านรายการต่างๆ ในโครงสร้างต้นไม้ โดยอาศัยการเชื่อมต่อระหว่างโหนดแม่และโหนดลูก เรียกว่าการเดินในต้นไม้ (walking the tree) และการกระทำนั้นเรียกว่าการเดินในต้นไม้ (walk of the tree) บ่อยครั้งที่อาจมีการดำเนินการบางอย่างเกิดขึ้นเมื่อตัวชี้มาถึงโหนดใดโหนดหนึ่ง การเดินที่ผ่านโหนดแม่แต่ละโหนดก่อนโหนดลูก เรียกว่า การเดิน แบบพรีออร์เดอร์ (pre-order walk) การเดินที่ผ่านโหนดลูกก่อนโหนดแม่ เรียกว่า การเดิน แบบโพสต์ออร์เดอร์ (post-order walk) การเดินที่ผ่านซับทรีด้านซ้ายของโหนด จากนั้นผ่านตัวโหนดเอง และสุดท้ายผ่านซับทรีด้านขวา เรียกว่า การเดินแบบอินออร์เดอร์ ( in-order traversal) (สถานการณ์สุดท้ายนี้ หมายถึงซับทรีสองอัน คือ ซับทรีด้านซ้ายและซับทรีด้านขวา โดยสมมติว่าเป็นต้นไม้ไบนารี ) การเดินแบบเลเวลออร์เดอร์ (level-order walk) จะทำการค้นหาแบบกว้าง (breadth-first search ) ทั่วทั้งต้นไม้ โหนดต่างๆ จะถูกสำรวจทีละระดับ โดยเริ่มจากโหนดรากก่อน ตามด้วยโหนดลูกโดยตรงและโหนดพี่น้องของโหนดเหล่านั้น จากนั้นก็ตามด้วยโหนดหลานและโหนดพี่น้องของโหนดเหล่านั้นไปเรื่อยๆ จนกว่าจะสำรวจทุกโหนดในต้นไม้เสร็จสิ้น

มีหลายวิธีในการแสดงโครงสร้างต้นไม้ ในหน่วยความจำใช้งาน (working memory) โหนดมักจะเป็น ระเบียน ที่จัดสรรแบบไดนามิกพร้อมตัวชี้ไปยังโหนดลูก โหนดแม่ หรือทั้งสองอย่าง รวมถึงข้อมูลที่เกี่ยวข้องใดๆ หากมีขนาดคงที่ โหนดอาจถูกจัดเก็บไว้ในรายการ (list) โหนดและความสัมพันธ์ระหว่างโหนดอาจถูกจัดเก็บไว้ในรายการประชิด (adjacency list ) ชนิดพิเศษที่แยกต่างหาก ในฐานข้อมูลเชิงสัมพันธ์ (relational databases ) โหนดมักจะแสดงเป็นแถวในตาราง โดยมีรหัสแถว (row ID) ที่มีดัชนีเพื่ออำนวยความสะดวกในการชี้ระหว่างโหนดแม่และโหนดลูก

นอกจากนี้ โหนดต่างๆ ยังสามารถจัดเก็บเป็นรายการในอาร์เรย์ได้ โดยความสัมพันธ์ระหว่างโหนดเหล่านั้นจะถูกกำหนดโดยตำแหน่งของโหนดในอาร์เรย์ (เช่นเดียวกับในฮีปแบบไบนารี )

โครงสร้าง ต้นไม้ไบนารีสามารถสร้างขึ้นได้โดยใช้ลิสต์ของลิสต์: ส่วนหัวของลิสต์ (ค่าของพจน์แรก) คือโหนดลูกซ้าย (ซับทรี) ในขณะที่ส่วนหาง (ลิสต์ของพจน์ที่สองและพจน์ต่อๆ ไป) คือโหนดลูกขวา (ซับทรี) นอกจากนี้ยังสามารถปรับเปลี่ยนให้มีค่าได้เช่นกัน ดังเช่นในนิพจน์ S ของ ภาษา Lisp ซึ่งส่วนหัว (ค่าของพจน์แรก) คือค่าของโหนด ส่วนหัวของส่วนหาง (ค่าของพจน์ที่สอง) คือโหนดลูกซ้าย และส่วนหางของส่วนหาง (ลิสต์ของพจน์ที่สามและพจน์ต่อๆ ไป) คือโหนดลูกขวา

ต้นไม้เรียงลำดับสามารถเข้ารหัสได้ตามธรรมชาติด้วยลำดับจำกัด เช่น ด้วยจำนวนธรรมชาติ^{[ 5 ]}

ไม่ใช่ต้นไม้ : มีสองส่วนที่ไม่เชื่อมต่อกันคือ A→B และ C→D→E มีรากมากกว่าหนึ่งราก

ไม่ใช่โครงสร้างต้นไม้ : วงจรแบบไม่มีทิศทาง 1-2-4-3 โดยที่ 4 มีโหนดแม่มากกว่าหนึ่งโหนด (เส้นเชื่อมขาเข้า)

ไม่ใช่โครงสร้างต้นไม้ : วงจร B→C→E→D→B โดยที่ B มีผู้ปกครองมากกว่าหนึ่งราย (เส้นเชื่อมขาเข้า)

ไม่ใช่โครงสร้างแบบต้นไม้ : เป็นวัฏจักร A→A โดยที่ A เป็นราก แต่ก็มีรากแม่ด้วย

รายการเชิงเส้นแต่ละรายการเป็นโครงสร้างต้นไม้โดย ปริยาย

ในฐานะที่เป็นชนิดข้อมูลนามธรรมชนิดต้นไม้แบบนามธรรมT ที่มีค่าเป็นชนิดข้อมูล Eบางประเภทจะถูกกำหนดโดยใช้ชนิดป่าแบบนามธรรมF (รายการของต้นไม้) โดยใช้ฟังก์ชันดังต่อไปนี้:

ค่า: T → E

เด็ก: T → F

nil: () → F

โหนด: E × F → T

โดยมีสัจพจน์ดังนี้:

ค่า(โหนด( e , f )) = e

children(node( e , f )) = f

ในแง่ของทฤษฎีประเภทต้นไม้เป็นประเภทอุปนัยที่นิยามโดยตัวสร้างnil (ป่าว่างเปล่า) และnode (ต้นไม้ที่มีโหนดรากซึ่งมีค่าที่กำหนดและโหนดลูก)

โดยรวมแล้ว โครงสร้างข้อมูลแบบต้นไม้คือต้นไม้ที่มีลำดับโดยทั่วไปจะมีค่าแนบอยู่กับแต่ละโหนด ในทางรูปธรรม (หากจำเป็นต้องไม่ว่างเปล่า) จะมีลักษณะดังนี้:

• ต้นไม้ที่มีรากหยั่งลึกโดยรากจะงอกออกไปในทิศทาง "ห่างจากราก" (คำที่ใช้ในความหมายแคบกว่าคือ " กลุ่มต้นไม้ ") ซึ่งหมายความว่า:
  • กราฟแบบมีทิศทาง
  • ซึ่งกราฟที่ไม่มีทิศทาง พื้นฐาน เป็นต้นไม้ (จุดยอดสองจุดใดๆ เชื่อมต่อกันด้วยเส้นทางง่ายๆ เพียงเส้นเดียว) ^{[ 6 ]}
  • โดยมีจุดยอดที่โดดเด่น (จุดยอดหนึ่งถูกกำหนดให้เป็นจุดยอดหลัก)
  • ซึ่งเป็นตัวกำหนดทิศทางบนขอบ (ลูกศรชี้ออกจากราก; เมื่อกำหนดขอบแล้ว โหนดที่ขอบชี้ออกไปเรียกว่าโหนดแม่และโหนดที่ขอบชี้ไปเรียกว่าโหนดลูก ) พร้อมด้วย:
• การจัดลำดับบนโหนดลูกของโหนดที่กำหนด และ
• ค่า (ของชนิดข้อมูลบางอย่าง) ที่แต่ละโหนด

โดยทั่วไป ต้นไม้จะมี ปัจจัยการแตกกิ่งที่คงที่ (หรือที่ถูกต้องกว่าคือ มีขอบเขตจำกัด) ( จำนวนกิ่ง ขาออก ) โดยเฉพาะอย่างยิ่งจะมีโหนดลูกสองโหนดเสมอ (อาจเป็นโหนดว่างก็ได้ ดังนั้น จึงมีโหนดลูก ที่ไม่ว่างได้มากที่สุดสองโหนด) จึงเรียกว่า "ต้นไม้ไบนารี"

การอนุญาตให้มีต้นไม้ว่างทำให้คำจำกัดความบางอย่างง่ายขึ้น บางอย่างซับซ้อนขึ้น: ต้นไม้ที่มีรากต้องไม่ว่าง ดังนั้นหากอนุญาตให้มีต้นไม้ว่าง คำจำกัดความข้างต้นจะกลายเป็น "ต้นไม้ว่างหรือต้นไม้ที่มีรากซึ่ง..." ในทางกลับกัน ต้นไม้ว่างทำให้การกำหนดปัจจัยการแตกกิ่งคงที่ง่ายขึ้น: เมื่ออนุญาตให้มีต้นไม้ว่าง ต้นไม้ไบนารีคือต้นไม้ที่แต่ละโหนดมีลูกสองตัวพอดี ซึ่งแต่ละตัวเป็นต้นไม้ (อาจว่างก็ได้)

โครงสร้างแบบต้นไม้ (Trees) มักใช้ในการแสดงหรือจัดการ ข้อมูล แบบลำดับชั้นในแอปพลิเคชันต่างๆ เช่น:

• ระบบไฟล์สำหรับ:
  • โครงสร้างไดเร็กทอรีที่ใช้ในการจัดระเบียบไดเร็กทอรีย่อยและไฟล์ ( ลิงก์สัญลักษณ์สร้างกราฟที่ไม่ใช่โครงสร้างแบบต้นไม้ เช่นเดียวกับฮาร์ดลิงก์ หลายรายการ ไปยังไฟล์หรือไดเร็กทอรีเดียวกัน)
  • กลไกที่ใช้ในการจัดสรรและเชื่อมโยงบล็อกข้อมูลบนอุปกรณ์จัดเก็บข้อมูล
• ลำดับชั้นของคลาสหรือ "แผนผังการสืบทอด" แสดงความสัมพันธ์ระหว่างคลาสในการเขียนโปรแกรมเชิงวัตถุการสืบทอดแบบหลายทางจะสร้างกราฟที่ไม่ใช่แผนผัง
• แผนผังไวยากรณ์นามธรรมสำหรับภาษาคอมพิวเตอร์
• การประมวลผลภาษาธรรมชาติ :
  • ต้นไม้วิเคราะห์
  • การสร้างแบบจำลองคำพูดในไวยากรณ์เชิงกำเนิด
  • โครงสร้างบทสนทนาแบบต้นไม้สำหรับการสร้างบทสนทนา
• แบบจำลองออบเจ็กต์เอกสาร ("โครงสร้าง DOM") ของเอกสารXMLและHTML
• โครงสร้างข้อมูล แบบต้นไม้ค้นหา (Search tree)จัดเก็บข้อมูลในลักษณะที่ทำให้ สามารถใช้ อัลกอริธึมการค้นหา ที่มีประสิทธิภาพ ผ่านการท่องไปในต้นไม้ ได้
  • ต้นไม้ค้นหาแบบไบนารี (Binary Search Tree) เป็น ต้นไม้ไบนารีชนิดหนึ่ง
• แสดงรายการข้อมูล ที่เรียงลำดับแล้ว
• ภาพที่สร้างขึ้นด้วยคอมพิวเตอร์ :
  • การแบ่งพื้นที่รวมถึงการแบ่งพื้นที่แบบไบนารี
  • การจัดองค์ประกอบภาพดิจิทัล
• การจัดเก็บ ต้นไม้ Barnes–Hutที่ใช้จำลองกาแล็กซี
• การนำ ฮีปมาใช้
• คอลเลกชันชุดซ้อน
• ระบบการจัดหมวดหมู่แบบลำดับชั้นเช่น ระบบการจัดหมวด หมู่แบบดิวอี้ (Dewey Decimal Classification)ที่มีส่วนต่างๆ ที่ระบุรายละเอียดเพิ่มขึ้นเรื่อยๆ
• หน่วยความจำเชิงเวลาแบบลำดับชั้น
• การโปรแกรมทางพันธุกรรม
• การจัดกลุ่มแบบลำดับชั้น

ต้นไม้สามารถใช้ในการแสดงและจัดการโครงสร้างทางคณิตศาสตร์ต่างๆ ได้ เช่น:

• สร้างเส้นทางผ่านกราฟโหนดและขอบ ใดๆ (รวมถึงมัลติกราฟ ) โดยการสร้างโหนดหลายโหนดในต้นไม้สำหรับแต่ละโหนดกราฟที่ใช้ในหลายเส้นทาง
• ลำดับชั้นทางคณิตศาสตร์ใดๆ

โครงสร้างแบบต้นไม้ มักใช้ในการแสดงความสัมพันธ์ระหว่างสิ่งต่างๆ เช่น:

• ส่วนประกอบและส่วนประกอบย่อยที่สามารถมองเห็นได้ในภาพร่างแสดงชิ้นส่วนแยกส่วน
• การเรียกซับรูทีนใช้เพื่อระบุว่าซับรูทีนใดในโปรแกรมเรียกซับรูทีนอื่นโดยไม่ใช้การเรียกซ้ำ
• การถ่ายทอดทางพันธุกรรมของดีเอ็นเอระหว่างสายพันธุ์โดยวิวัฒนาการการถ่ายทอดรหัสต้นฉบับโดยโครงการซอฟต์แวร์ (เช่นลำดับเวลาของการแจกจ่ายลินุกซ์ ) การถ่ายทอดการออกแบบในรถยนต์ประเภทต่างๆ เป็นต้น
• เนื้อหาของเนมสเปซ แบบลำดับชั้น

เอกสาร JSONและYAMLสามารถมองได้ว่าเป็นโครงสร้างแบบต้นไม้ แต่โดยทั่วไปแล้วจะถูกแสดงด้วยรายการและพจนานุกรม ที่ซ้อน กัน

• การค้นหาต้นไม้แบบกระจาย
• หมวดหมู่: ต้นไม้ (โครงสร้างข้อมูล) (แคตตาล็อกประเภทของต้นไม้คำนวณ)

• โดนัลด์ คนูธ . ศิลปะแห่งการเขียนโปรแกรมคอมพิวเตอร์ : อัลกอริทึมพื้นฐาน , ฉบับพิมพ์ครั้งที่ 3. แอดดิสัน-เวสลีย์, 1997. ISBN 0-201-89683-4ส่วนที่ 2.3: ต้นไม้, หน้า 308–423.
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. RivestและClifford Stein . Introduction to Algorithms , ฉบับพิมพ์ครั้งที่สอง. MIT Press และ McGraw-Hill, 2001. ISBN 0-262-03293-7ส่วนที่ 10.4: การแสดงต้นไม้แบบมีราก หน้า 214–217 บทที่ 12–14 (ต้นไม้ค้นหาแบบไบนารี ต้นไม้แดง-ดำ โครงสร้างข้อมูลเสริม) หน้า 253–320

วิกิมีเดียคอมมอนส์มีสื่อที่เกี่ยวข้องกับโครงสร้างของต้นไม้

• คำอธิบายจากพจนานุกรมอัลกอริทึมและโครงสร้างข้อมูล