© NicoElNino/Shutterstock.com
ในวิทยาการคอมพิวเตอร์ ข้อมูลสามารถจัดโครงสร้างและสำรวจได้หลายวิธี ไบนารีทรีเป็นรูปแบบหนึ่งของการจัดเก็บข้อมูลแบบลำดับชั้นที่ใช้การข้ามผ่านของต้นไม้เป็นวิธีการหลักในการเยี่ยมชมโหนดที่เป็นส่วนประกอบทั้งหมดสำหรับการค้นหา การเรียงลำดับ และวัตถุประสงค์อื่นๆ การทำความเข้าใจวิธีการต่างๆ ที่ใช้สำหรับการข้ามผ่านต้นไม้สามารถช่วยให้คุณดำเนินการขั้นพื้นฐานบนไบนารีทรีได้ ในบทความนี้ เราจะอธิบายว่าการข้ามผ่านต้นไม้คืออะไร ซึ่งรวมถึงการข้ามผ่านตามลำดับ การสั่งซื้อล่วงหน้า และการสั่งซื้อภายหลัง พร้อมตัวอย่างที่จะช่วยให้คุณเริ่มต้นได้
การข้ามผ่านต้นไม้คืออะไร
การข้ามผ่านต้นไม้คืออะไร วิธีการที่นักวิทยาศาสตร์คอมพิวเตอร์ นักพัฒนา และวิศวกรซอฟต์แวร์ใช้ในการสำรวจไบนารีทรี เรียกอีกอย่างว่า:
การเดินบนต้นไม้ การค้นหาแบบต้นไม้
วิธีการเหล่านี้เกี่ยวข้องกับการเยี่ยมชมแต่ละโหนดตามลำดับภายในต้นไม้ไบนารี ตรงกันข้ามกับโครงสร้างข้อมูลเชิงเส้น เช่น รายการหรือคิวที่เชื่อมโยง การข้ามผ่านเหล่านี้สามารถทำได้หลายวิธี วิธีการหลักที่อธิบายด้านล่างใช้สำหรับการปรับปรุง ลบ ค้นหา จัดเรียง และดึงข้อมูลอย่างมีประสิทธิภาพ
เกี่ยวกับไบนารีทรี
ไบนารีทรีเป็นรูปแบบของทรีที่ใช้บ่อยที่สุด ซึ่งเป็นโครงสร้างข้อมูลแบบลำดับชั้นที่ประกอบด้วยโหนดที่เชื่อมต่อถึงกัน แต่ละโหนดประกอบด้วยการอ้างอิงทางซ้ายและขวาและองค์ประกอบข้อมูล แต่ละโหนดในไบนารีทรีเชื่อมต่อกับพาเรนต์หนึ่งพาเรนต์ แต่โหนดพาเรนต์แต่ละโหนดสามารถมีลูกได้สูงสุด 2 ตัวเท่านั้น โหนดที่ไม่มีลูกเรียกว่าลีฟ โหนดที่ใช้โหนดหลักร่วมกันเรียกว่าโหนดพี่น้อง โหนดที่อยู่บนสุดของไบนารีทรีเรียกว่ารูท
หากไบนารีทรีถูกเติมอย่างสมบูรณ์ จะเรียกว่าทรีสมบูรณ์ ต้นไม้เต็มไปด้วยโหนดจากซ้ายไปขวา คุณสามารถวางตำแหน่งโหนดตามความสูง ซึ่งเป็นจำนวนขอบระหว่างรูทและโหนดดัชนี หรือความลึก ซึ่งเป็นจำนวนขอบระหว่างโหนดและโหนดปลายสุด
ใช้ Tree Traversals เพื่อเยี่ยมชมทุก ๆ โหนดใน Tree
คุณลักษณะที่สำคัญของ Traversals เหล่านี้คือทุก ๆ โหนดใน Tree จะถูกเยี่ยมชม เนื่องจากทรีเป็นโครงสร้างข้อมูลที่ไม่ใช่เชิงเส้น จึงมีหลายวิธีและลำดับที่คุณสามารถมั่นใจได้ว่าแต่ละโหนดจะถูกเยี่ยมชมตามลำดับ ไม่มีการส่งผ่านเพียงครั้งเดียว แต่มีอัลกอริทึมการผ่านหลายรายการที่คุณสามารถใช้ได้
การข้ามผ่านต้นไม้มีความสำคัญ
การควบคุมการข้ามผ่านต้นไม้เป็นทักษะสำคัญสำหรับการจัดระเบียบและทำงานกับข้อมูล นี่เป็นเพราะต้นไม้เป็นโครงสร้างข้อมูลทั่วไปและมีการใช้กันอย่างแพร่หลายเนื่องจากการแสดงความสัมพันธ์ของข้อมูลและลำดับชั้นที่ชัดเจน
คุณสามารถใช้วิธีการสำรวจและตัวอย่างเหล่านี้เพื่อการค้นหาหรือการแทรกข้อมูลที่มีประสิทธิภาพมากขึ้น มาดูวิธีการหลักๆ ด้านล่าง:
นี่คือต้นไม้ตัวอย่าง:
ภาพประกอบโครงสร้างต้นไม้
©”TNGD”.com
1. PreOrder Traversal
นี่คือประเภทของการแวะผ่านเชิงลึกแบบแรก โดยไปที่โหนดหลักก่อน จากนั้นจึงไปที่โหนดลูกด้านซ้าย และโหนดลูกด้านขวา ถ้าต้นไม้ถูกสำรวจโดยใช้วิธี preOrder โหนดรูทจะถูกเยี่ยมชมก่อน จากนั้นทรีย่อยทางซ้ายและขวาตามลำดับพาเรนต์-เฟิร์ส จนกระทั่งทรีทั้งหมดถูกสำรวจ การผ่านคำสั่งซื้อล่วงหน้าให้วิธีการที่มีประสิทธิภาพในการคัดลอกต้นไม้
นี่คือตัวอย่างการส่งผ่านคำสั่งซื้อล่วงหน้าสำหรับต้นไม้ด้านบน: A > B > D > E > C > F > G
และ นี่คืออัลกอริทึมการสั่งซื้อล่วงหน้า:
อัลกอริทึมสำหรับ preOrder Traversal ของโครงสร้างแบบต้นไม้
©”TNGD”.com
2. InOrder traversal
นี่คือประเภทของการแวะผ่านเชิงลึกประเภทแรก ที่โหนดลูกด้านซ้ายถูกเยี่ยมชม จากนั้นพาเรนต์ และโหนดลูกด้านขวา InOrder traversals ดำเนินการผ่าน subtree ซ้ายสุดและสิ้นสุดที่ subtree ขวาสุด ประเภทของการสำรวจนี้สร้างข้อมูลที่จัดเรียงจากน้อยไปหามาก
นี่คือตัวอย่าง inOrder traversal สำหรับทรีด้านบน: D > B > E > A > F > C > G
และนี่คืออัลกอริทึม inOrder:
อัลกอริทึมสำหรับ inOrder Traversal ของโครงสร้างต้นไม้.
©”TNGD”.com
3. การแวะผ่านของ PostOrder
การแวะผ่านเชิงลึกก่อนอื่นประเภทที่สามนี้จะไปที่โหนดลูกด้านซ้าย จากนั้นไปที่โหนดลูกด้านขวา จากนั้นไปที่พาเรนต์ ด้วยการแวะผ่านทรีของ postOrder ต้นไม้ย่อยทั้งหมดจะถูกเยี่ยมชมก่อน (จากซ้ายล่างสุด) โดยมีการเข้าชมรูทสุดท้าย การแวะผ่าน PostOrder เป็นวิธีที่มีประสิทธิภาพในการลบแผนผัง
นี่คือตัวอย่างการผ่านคำสั่งของ postOrder สำหรับต้นไม้ด้านบน: D > E > B > F > G > C > A
และนี่คืออัลกอริทึมของ postOrder:
อัลกอริทึมสำหรับ postOrder Traversal ของโครงสร้างต้นไม้.
©”TNGD”.com
นอกจากนี้ยังมีการสำรวจเส้นทางแบบกว้าง-แรกที่เยี่ยมชมโหนดจากบนลงล่างและจากซ้ายไปขวา นี่เป็นรูปแบบเดียวของการเคลื่อนผ่านแนวขวางก่อน
การปัดเศษขึ้น
อย่างที่คุณเห็น การเคลื่อนที่แนวต้นไม้ทำให้การจัดการของ ข้อมูลลำดับชั้น ง่ายมาก อัลกอริทึมนั้นตรงไปตรงมาและหากคุณหลงทาง คุณสามารถวาดแผนผังพื้นฐานเพื่อกำหนดทิศทางของคุณเองได้ วิธีการเหล่านี้มีประสิทธิภาพมากจนคุณสามารถสร้างไบนารีทรีเต็มรูปแบบจากการแวะผ่านก่อนและหลังการสั่งซื้อที่ให้มา ฝึกฝนวิธีการเหล่านี้เพื่อให้เชี่ยวชาญและเพิ่มพูนความรู้ของคุณ
Tree Traversals (Inorder, Preorder และ Postorder) คืออะไร – พร้อมตัวอย่าง FAQs (คำถามที่พบบ่อย)
โครงสร้างข้อมูลคืออะไร
โครงสร้างข้อมูลเป็นรูปแบบเฉพาะที่ใช้ในการจัดระเบียบข้อมูล จึงสามารถจัดเก็บอย่างปลอดภัยและจัดการและเข้าถึงได้อย่างมีประสิทธิภาพ
ต้นไม้ประเภทหลักคืออะไร
นอกเหนือจากต้นไม้ไบนารีแล้ว ต้นไม้ประเภทหลักยังรวมถึง:
ต้นไม้ Heap ต้นไม้ไวยากรณ์ Tries B-trees T-trees
binary tree ที่สมบูรณ์แบบคืออะไร
binary tree ที่สมบูรณ์แบบมี leaf nodes ทั้งหมดที่ความลึกเท่ากัน และ parent node ทั้งหมดมีลูก 2 คน นี่เป็นอีกวิธีหนึ่งในการอธิบายถึงต้นไม้ที่สมบูรณ์และปราศจากช่องว่าง
ตัวอย่างโครงสร้างข้อมูลที่ไม่ใช่แผนผังคืออะไร
โครงสร้างข้อมูลที่ไม่ใช่แผนผังคือโครงสร้างข้อมูลเชิงเส้นโดยส่วนใหญ่ประกอบด้วย:
อาร์เรย์ A บิตแมป เมทริกซ์ อาร์เรย์คู่ขนาน รายการที่เชื่อมโยงเป็นสองเท่า รายการที่จัดระเบียบตัวเอง
ประเภทข้อมูลนามธรรมคืออะไร
ประเภทข้อมูลนามธรรม (ADT) เป็นแบบจำลองทางคณิตศาสตร์ที่สามารถใช้เพื่อจัดโครงสร้างข้อมูล และอำนวยความสะดวกในการเขียนโปรแกรมขนาดใหญ่ ในวิทยาการคอมพิวเตอร์ สามารถใช้ ADT เพื่อจัดแพคเกจและจัดการข้อมูลสำหรับแอปพลิเคชันคอมพิวเตอร์ที่หลากหลาย