โหนด
โหนด (อังกฤษ: node) เป็นหน่วยพื้นฐานของโครงสร้างข้อมูลหลายชนิด เช่น รายการโยง ต้นไม้ และกราฟ โหนดมักใช้แทนวัตถุหนึ่งหน่วยในโครงสร้างข้อมูล โดยอาจเก็บข้อมูล ค่า สถานะ หรือข้อมูลอ้างอิงไปยังโหนดอื่น[1][2] ในโครงสร้างข้อมูลที่มีความเชื่อมโยงกัน เช่น รายการโยงหรือต้นไม้ การเชื่อมโยงระหว่างโหนดมักทำด้วยพอยน์เตอร์ (pointer) การอ้างอิง หรือเขตข้อมูลที่บอกตำแหน่งของโหนดถัดไป[3]
คำว่าโหนดใช้ในหลายบริบทของวิทยาการคอมพิวเตอร์ ในบริบทของโครงสร้างข้อมูล โหนดหมายถึงหน่วยข้อมูลที่อยู่ในโครงสร้าง เช่น โหนดของรายการโยงหรือโหนดของต้นไม้ ในบริบทของทฤษฎีกราฟ โหนดมักมีความหมายใกล้เคียงกับจุดยอด ส่วนในบริบทของแบบจำลองอ็อบเจกต์เอกสาร (Document Object Model หรือ DOM) โหนดหมายถึงจุดหนึ่งในต้นไม้ของเอกสาร เช่น เอกสาร องค์ประกอบ ข้อความ หรือความคิดเห็น[4][5]
ในโครงสร้างข้อมูล
[แก้]โหนดในโครงสร้างข้อมูลมักประกอบด้วยอย่างน้อยสองส่วน ได้แก่ ส่วนที่เก็บข้อมูล และส่วนที่ใช้เชื่อมโยงกับโหนดอื่น ตัวอย่างเช่น โหนดของรายการโยงแบบเดี่ยวอาจมีเขตข้อมูลหนึ่งสำหรับเก็บค่า และอีกเขตข้อมูลหนึ่งสำหรับเก็บพอยน์เตอร์ไปยังโหนดถัดไป[3] ในรายการโยงแบบสองทาง โหนดมักมีลิงก์ไปยังทั้งโหนดก่อนหน้าและโหนดถัดไป ทำให้สามารถเดินทางผ่านรายการได้ทั้งสองทิศทาง[1]
ในต้นไม้ โหนดถูกจัดลำดับเป็นความสัมพันธ์แบบลำดับชั้น โหนดหนึ่งอาจมีโหนดลูกหลายโหนด แต่โดยทั่วไปมีโหนดพ่อแม่เพียงหนึ่งโหนด ยกเว้นโหนดรากซึ่งไม่มีโหนดพ่อแม่[2] โครงสร้างต้นไม้ใช้กันมากในการแทนข้อมูลที่มีลำดับชั้น เช่น ระบบแฟ้ม นิพจน์ทางคณิตศาสตร์ โครงสร้างเอกสาร และดัชนีสำหรับค้นหาข้อมูล[6]
ในกราฟ โหนดใช้แทนวัตถุหรือจุดหนึ่งในระบบ ส่วนเส้นเชื่อมระหว่างโหนดเรียกว่าเอจหรือขอบ กราฟจึงเหมาะสำหรับแทนความสัมพันธ์ที่ไม่จำเป็นต้องเป็นลำดับชั้น เช่น เครือข่ายสังคม เส้นทางคมนาคม โครงข่ายคอมพิวเตอร์ และความสัมพันธ์ระหว่างวัตถุในฐานข้อมูล[1]
โหนดและต้นไม้
[แก้]ในโครงสร้างต้นไม้ โหนดหนึ่งตัวแทนข้อมูลหนึ่งหน่วยในโครงสร้างข้อมูล โหนดอาจเก็บค่า เงื่อนไข สถานะ หรืออาจทำหน้าที่เป็นโครงสร้างข้อมูลย่อยที่มีโหนดอื่นอยู่ภายใน[2] โหนดที่อยู่บนสุดของต้นไม้เรียกว่าโหนดราก (root node) ซึ่งไม่มีโหนดพ่อแม่ แต่เป็นจุดเริ่มต้นสำหรับเข้าถึงโหนดอื่นในต้นไม้[2]
ความลึกของโหนดคือจำนวนขอบบนเส้นทางจากโหนดนั้นไปยังโหนดราก โดยโหนดรากมีความลึกเท่ากับ 0[3] ส่วนความสูงของโหนดคือความยาวของเส้นทางที่ยาวที่สุดจากโหนดนั้นลงไปยังโหนดใบ และความสูงของต้นไม้เท่ากับความสูงของโหนดราก[2] ในภาพต้นไม้ที่นิยมใช้ในวิทยาการคอมพิวเตอร์ โหนดรากมักวาดไว้ด้านบน ส่วนโหนดใบมักวาดไว้ด้านล่าง แม้คำว่า “ต้นไม้” จะตรงข้ามกับภาพต้นไม้ในธรรมชาติก็ตาม[1]
การเดินทางผ่านโหนดในต้นไม้เรียกว่าการท่องผ่านต้นไม้ (tree traversal) ซึ่งมีหลายแบบ เช่น การท่องแบบก่อนลำดับ (preorder) การท่องแบบในลำดับ (inorder) การท่องแบบหลังลำดับ (postorder) และการท่องแบบตามระดับ (level-order traversal)[1] วิธีท่องผ่านต้นไม้มีความสำคัญต่อการค้นหา การเรียงลำดับ การประมวลผลนิพจน์ และการจัดการข้อมูลที่มีลำดับชั้น[6]
คำนิยามสำคัญ
[แก้]- โหนดลูก (child node) คือโหนดที่ขยายออกมาจากโหนดอื่น ถ้าโหนด C เป็นโหนดลูกของโหนด A โหนด A จะเป็นโหนดพ่อแม่ของโหนด C[3]
- โหนดพ่อแม่ (parent node) คือโหนดที่มีโหนดลูกอย่างน้อยหนึ่งโหนด[2]
- ดีกรี (degree) ของโหนด คือจำนวนโหนดลูกของโหนดนั้น[3]
- ความลึก (depth) ของโหนด คือจำนวนขอบบนเส้นทางจากโหนดนั้นไปยังโหนดราก โดยโหนดรากมีความลึกเท่ากับ 0[3]
- ขอบ หรือ เอจ (edge) คือการเชื่อมต่อระหว่างโหนดสองโหนด[1]
- ป่า (forest) คือกลุ่มของต้นไม้ตั้งแต่หนึ่งต้นขึ้นไป หรือโครงสร้างที่ประกอบด้วยต้นไม้หลายต้นแยกกัน[2]
- ความสูง (height) ของโหนด คือความยาวของเส้นทางที่ยาวที่สุดจากโหนดนั้นไปยังโหนดใบ ส่วนความสูงของต้นไม้คือความสูงของโหนดราก[2]
- โหนดภายใน (internal node) คือโหนดที่มีโหนดลูกอย่างน้อยหนึ่งโหนด[2]
- โหนดใบ (leaf node) คือโหนดที่ไม่มีโหนดลูก[2]
- โหนดราก (root node) คือโหนดที่ไม่มีโหนดพ่อแม่และเป็นจุดเริ่มต้นของต้นไม้[2]
- โหนดพี่น้อง (sibling nodes) คือโหนดที่มีโหนดพ่อแม่เดียวกัน[3]
ตัวอย่างในรายการโยง
[แก้]ในรายการโยง โหนดแต่ละตัวเรียงต่อกันเป็นลำดับ โดยโหนดหนึ่งมักเก็บข้อมูลและลิงก์ไปยังโหนดถัดไป โครงสร้างแบบนี้ช่วยให้สามารถเพิ่มหรือลบโหนดได้โดยปรับลิงก์ระหว่างโหนด แทนที่จะต้องย้ายข้อมูลจำนวนมากเหมือนในอาร์เรย์บางกรณี[1] อย่างไรก็ตาม การเข้าถึงสมาชิกตำแหน่งใดตำแหน่งหนึ่งในรายการโยงมักต้องเริ่มจากโหนดแรกแล้วเดินผ่านลิงก์ทีละโหนด จึงไม่เหมือนอาร์เรย์ที่สามารถเข้าถึงสมาชิกด้วยดัชนีได้โดยตรง[3]
ตัวอย่างโครงสร้างโหนดของรายการโยงแบบเดี่ยวในเชิงแนวคิดอาจเขียนได้ดังนี้
struct Node {
int data;
struct Node *next;
};
ในตัวอย่างนี้ data เป็นส่วนที่เก็บข้อมูล ส่วน next เป็นพอยน์เตอร์ที่เชื่อมไปยังโหนดถัดไป หาก next ไม่มีค่าอ้างอิงไปยังโหนดอื่น มักถือว่าโหนดนั้นเป็นโหนดสุดท้ายของรายการ[3]
ภาษาเครื่องหมายและ DOM
[แก้]การใช้คำว่าโหนดอีกบริบทหนึ่งที่พบมากคือในภาษาเครื่องหมายและการพัฒนาเว็บ โดยเฉพาะในDocument Object Model หรือ DOM ซึ่งแทนเอกสาร HTML และ XML เป็นโครงสร้างแบบต้นไม้[4][7] ใน DOM วัตถุทุกชนิดที่อยู่ในเอกสารถือเป็นโหนดบางประเภท เช่น เอกสารทั้งฉบับ องค์ประกอบ ข้อความ และความคิดเห็น[5]
DOM ทำหน้าที่เป็นแบบจำลองมาตรฐานที่ช่วยให้โปรแกรมหรือสคริปต์เข้าถึง อ่าน แก้ไข เพิ่ม หรือลบส่วนต่าง ๆ ของเอกสารได้โดยใช้ส่วนต่อประสานโปรแกรมประยุกต์หรือ API[8] ในการพัฒนาเว็บ ภาษาหลักอย่าง HTML และ XML ให้โครงสร้างของเอกสาร ส่วน DOM ให้มุมมองเชิงวัตถุของโครงสร้างนั้น เพื่อให้ภาษาอย่างจาวาสคริปต์สามารถจัดการเอกสารในเบราว์เซอร์ได้[7]
ประเภทของโหนดใน DOM
[แก้]ใน DOM อินเทอร์เฟซ Node เป็นฐานนามธรรมของวัตถุหลายชนิด เช่น Document, Element, DocumentFragment, Text และ Comment[9] มาตรฐาน DOM ของ WHATWG ระบุว่าโหนดเป็นวัตถุที่เข้าร่วมอยู่ใน “ต้นไม้โหนด” และวัตถุที่ใช้อินเทอร์เฟซ Node มักใช้อินเทอร์เฟซสืบทอดที่เฉพาะเจาะจงกว่า เช่น Document, Element หรือ CharacterData[4]
คุณสมบัติ nodeType ของ Node เป็นจำนวนเต็มแบบอ่านอย่างเดียวที่ใช้ระบุชนิดของโหนด เช่น โหนดองค์ประกอบ โหนดข้อความ และโหนดความคิดเห็น[10] ตัวอย่างค่าที่ใช้กันทั่วไปใน DOM ได้แก่
ค่า nodeType |
ค่าคงที่ | ความหมาย |
|---|---|---|
| 1 | ELEMENT_NODE |
โหนดองค์ประกอบ เช่น <p> หรือ <div> |
| 3 | TEXT_NODE |
โหนดข้อความภายในเอกสาร |
| 7 | PROCESSING_INSTRUCTION_NODE |
คำสั่งประมวลผล |
| 8 | COMMENT_NODE |
โหนดความคิดเห็น |
| 9 | DOCUMENT_NODE |
โหนดเอกสารทั้งฉบับ |
| 10 | DOCUMENT_TYPE_NODE |
ชนิดเอกสารหรือ doctype |
| 11 | DOCUMENT_FRAGMENT_NODE |
ชิ้นส่วนเอกสาร |
มาตรฐานและเอกสารสมัยใหม่ยังคงกล่าวถึงค่าบางชนิดในประวัติศาสตร์ เช่น ATTRIBUTE_NODE, ENTITY_REFERENCE_NODE, ENTITY_NODE และ NOTATION_NODE แต่บางค่าเป็นของ DOM รุ่นเก่าหรือไม่ได้ใช้ในเอกสาร HTML สมัยใหม่ตามปกติ[10][4]
วัตถุโหนด
[แก้]วัตถุโหนดใน DOM แทนโหนดหนึ่งจุดในต้นไม้เอกสาร โหนดบางชนิดสามารถมีโหนดลูกได้ เช่น Document, DocumentFragment และ Element ส่วนโหนดบางชนิด เช่น Text และ Comment มักใช้แทนข้อมูลอักขระและไม่มีโหนดลูกในลักษณะเดียวกับองค์ประกอบ[9][11][12]
โปรแกรมสามารถเข้าถึงและปรับเปลี่ยนวัตถุในต้นไม้ DOM ได้ด้วยเมท็อดและคุณสมบัติ เช่น การเลือกองค์ประกอบ การอ่านหรือแก้ไขข้อความ การเพิ่มโหนดลูก การลบโหนด และการเดินผ่านต้นไม้เอกสาร[7] ประวัติของ DOM เกี่ยวข้องกับประวัติของเว็บเบราว์เซอร์และจาวาสคริปต์ เพราะ DOM เป็นหนึ่งในกลไกสำคัญที่ทำให้เอกสารเว็บเปลี่ยนแปลงแบบโต้ตอบได้หลังจากโหลดหน้าเว็บแล้ว[8][7]
ความแตกต่างจากคำใกล้เคียง
[แก้]ในบริบทของทฤษฎีกราฟ คำว่าโหนดมักใช้แทนคำว่าจุดยอด (vertex) ได้ในหลายกรณี แต่ในคณิตศาสตร์เชิงกราฟ คำว่า “จุดยอด” เป็นศัพท์เทคนิคที่แม่นยำกว่า ส่วน “โหนด” มักใช้ในบริบทเชิงคอมพิวเตอร์ เครือข่าย หรือการประยุกต์[1] ในโครงข่ายคอมพิวเตอร์ คำว่าโหนดยังอาจหมายถึงอุปกรณ์ที่เชื่อมต่อกับเครือข่าย เช่น คอมพิวเตอร์ เราเตอร์ หรืออุปกรณ์ปลายทาง ซึ่งเป็นความหมายที่ต่างจากโหนดในโครงสร้างข้อมูล แม้จะใช้แนวคิดจุดเชื่อมต่อคล้ายกัน[1]
ดูเพิ่ม
[แก้]อ้างอิง
[แก้]- 1 2 3 4 5 6 7 8 9 Black, Paul E. (2020). "Dictionary of Algorithms and Data Structures". National Institute of Standards and Technology (ภาษาอังกฤษ). สืบค้นเมื่อ 18 มิถุนายน 2026.
{{cite web}}: CS1 maint: date auto-translated (ลิงก์) - 1 2 3 4 5 6 7 8 9 10 11 "tree". Dictionary of Algorithms and Data Structures (ภาษาอังกฤษ). National Institute of Standards and Technology. ข้อมูลเก่าจากต้นฉบับ เมื่อ 24 พฤศจิกายน 2014. สืบค้นเมื่อ 18 มิถุนายน 2026.
{{cite web}}: CS1 maint: date auto-translated (ลิงก์) - 1 2 3 4 5 6 7 8 9 Teukolsky, Roselyn (2013). Barron's AP Computer Science A. Barron's. ISBN 978-1-4380-0152-4.
- 1 2 3 4 "DOM Standard". WHATWG (ภาษาอังกฤษ). 15 มีนาคม 2026. สืบค้นเมื่อ 18 มิถุนายน 2026.
{{cite web}}: CS1 maint: date auto-translated (ลิงก์) - 1 2 "Node (DOM)". MDN Web Docs (ภาษาอังกฤษ). 11 กรกฎาคม 2025. สืบค้นเมื่อ 18 มิถุนายน 2026.
{{cite web}}: CS1 maint: date auto-translated (ลิงก์) - 1 2 "Simply Scheme: Introducing Computer Science, Chapter 18: Trees". University of California, Berkeley (ภาษาอังกฤษ). ข้อมูลเก่าจากต้นฉบับ เมื่อ 22 ธันวาคม 2013. สืบค้นเมื่อ 18 มิถุนายน 2026.
{{cite web}}: CS1 maint: date auto-translated (ลิงก์) - 1 2 3 4 "Document Object Model (DOM)". MDN Web Docs (ภาษาอังกฤษ). 8 เมษายน 2026. สืบค้นเมื่อ 18 มิถุนายน 2026.
{{cite web}}: CS1 maint: date auto-translated (ลิงก์) - 1 2 "Document Object Model (DOM) Requirements". World Wide Web Consortium (ภาษาอังกฤษ). 3 พฤศจิกายน 2020. สืบค้นเมื่อ 18 มิถุนายน 2026.
{{cite web}}: CS1 maint: date auto-translated (ลิงก์) - 1 2 "Node". MDN Web Docs (ภาษาอังกฤษ). 18 สิงหาคม 2025. สืบค้นเมื่อ 18 มิถุนายน 2026.
{{cite web}}: CS1 maint: date auto-translated (ลิงก์) - 1 2 "Node: nodeType property". MDN Web Docs (ภาษาอังกฤษ). 26 ตุลาคม 2025. สืบค้นเมื่อ 18 มิถุนายน 2026.
{{cite web}}: CS1 maint: date auto-translated (ลิงก์) - ↑ "Text". MDN Web Docs (ภาษาอังกฤษ). 19 กุมภาพันธ์ 2023. สืบค้นเมื่อ 18 มิถุนายน 2026.
{{cite web}}: CS1 maint: date auto-translated (ลิงก์) - ↑ "Comment". MDN Web Docs (ภาษาอังกฤษ). 24 กันยายน 2024. สืบค้นเมื่อ 18 มิถุนายน 2026.
{{cite web}}: CS1 maint: date auto-translated (ลิงก์)
แหล่งข้อมูลอื่น
[แก้]- Dictionary of Algorithms and Data Structures โดย National Institute of Standards and Technology
- DOM Standard โดย WHATWG
- Node ที่ MDN Web Docs
- Document Object Model ที่ MDN Web Docs