บทความ IT เจ๋งๆ

สำหรับ Computer Science แล้วเรื่องของ Tree ถูกใช้แพร่หลายใน Abstract Data Type (ADT) วันนี้เราจะมาดูกันว่า สิ่งที่คุณควรรู้เกี่ยวกับ Tree Traversal Algorithms (การแวะ/ท่องของต้นไม้) สำหรับการใช้งานใน Java นั้นมีอะไรบ้าง

ตามความหมายใน Wikipedia ระบุว่า “โครงสร้างข้อมูลแบบต้นไม้ (Tree Data Structure) สามารถถูกนิยามด้วยรูปแบบ Recursive ที่เป็นชุดของ Node (เริ่มต้นที่ Root Node) โดยที่แต่ละ Node เป็น Data Structure ที่ประกอบด้วย Value พร้อมกับ List ของการอ้างอิงหรือชี้ไปยัง Node ("Children") โดยมีข้อบังคับคือจะไม่มีการชี้ไปยัง Node ที่ซ้ำกันและไม่มีการชี้กลับไปที่ Root”

มีวิธีการแวะหรือท่อง Tree ด้วยวิธีต่างๆ ดังนี้:

• Pre Order Traversal: จะเริ่มจาก Root, Left, Right

จากตัวอย่างจะเรียงลำดับการเข้าถึงดังนี้: A B D H I E J C F G K

• In Order Traversal: จะเริ่มจาก Left, Root, Right

จากตัวอย่างจะเรียงลำดับการเข้าถึงดังนี้: H D I B J E A F C K G

• Post Order Traversal: จะเริ่มจาก Left, Right, Root

จากตัวอย่างจะเรียงลำดับการเข้าถึงดังนี้: H I D J E B F K G C A

• Level Order Traversal, หรือที่รู้จักกันใน Breadth-first search

จากตัวอย่างจะเรียงลำดับการเข้าถึงดังนี้:  A B C D E F G H I J K

ใน Tutorial นั้น คุณจะได้เรียนรู้วิธีการ Implement เกี่ยวกับ Tree Traversal Algorithms ใน Java ทั้งด้วยการ Recursion และไม่มีการ Recursion อย่างที่คุณเห็น Recursion Solutions นั้นง่ายกว่าการ Iteration แต่คุณต้องเข้าใจทั้ง 2 Solutions เนื่องจากการ Implement Algorithms เหล่านี้ มักจะถูกถามในการสัมภาษณ์งานด้วย

สำหรับตัวอย่างของเรา เราจะใช้ภาษา Java แต่ Logic ก็จะเหมือนๆ กันสำหรับการใช้งานในภาษาอื่น เช่น C++ หรือ Python

Tree ใช้เป็นตัวแทนสิ่งใด

ใน Step แรกจะเป็นการแสดงว่า Tree ใช้เป็นตัวแทนของสิ่งใดได้ เนื่องจาก Tree มี Node ดังนั้น เราจะเริ่มต้นด้วยการกำหนด Node class ซึ่ง Node จะมีคุณสมบัติดังต่อไปนี้:

• Data จะแสดงถึง Data ของ Node
• Left pointer จะชี้ไปที่ Node ด้านซ้าย
• Right pointer จะชี้ไปที่ Node ด้านขวา

ทำให้เรามี Node class ดังนี้

ในการใช้ Tree เป็นตัวแทนนั้น เราจะต้องเลือก Node instance เป็น Root ของ Tree ทำให้เราได้ Code ต่อไปนี้สำหรับการสร้าง Tree:

Tree Pre Order Traversal โดยการใช้ Recursion

เราเริ่มต้นด้วยการ Implement Tree Pre Order Traversal Algorithm โดยการใช้ Recursion เราต้องการแวะแต่ละ Node ของ Tree โดยแสดง Data สำหรับ Root, Left และ Right Node

ดังนั้น เราจำเป็นต้องกำหนด preOrderTraverse Method แบบ Recursive โดยใช้ Node ใน Parameter และดำเนินการดังต่อไปนี้:

• แสดง Data
• เรียกใช้ preOrderTraverse สำหรับ Left Node
• เรียกใช้ preOrderTraverse สำหรับ Right Node

ทำให้เราสามารถ Implement ออกมาได้ดังนี้:

คุณสามารถดูรายละเอียดการ Implementation และ Execution ของ Tree Pre Order Traversal Algorithm โดยการใช้ Recursion จาก Video บน YouTube ได้ ที่นี่

Tree Pre Order Traversal โดยการใช้ Iterative solution

สิ่งต่างๆ จะเริ่มมีความซับซ้อนเพิ่มขึ้นเล็กน้อย เนื่องจากเราจะ Implement Tree Pre Order Traversal Algorithm โดยการใช้ Iterative Solution ซึ่งในการทำสิ่งนั้น เราจะต้องใช้ Stack of Node

ก่อนอื่น เราจะทำการ Push Root ของ Tree เข้าไปใน Stack ก่อน จากนั้นเราจะทำการ Iteration ไปเรื่อยๆ ตราบใดที่ Stack ยังไม่ Empty เราจะ Pop Node ทั้งหมดทีละ Node ออกมา โดยเราจะทำขั้นตอนต่อไปนี้:

• แสดง Data
• Push ลูกทางด้านขวา (Right Child) ของมัน เข้าไปใน Stack
• Push ลูกทางด้านซ้าย (Left Child) ของมัน เข้าไปใน Stack

ทำให้เราสามารถ Implement ออกมาได้ดังนี้:

คุณสามารถดูรายละเอียดการ Implementation และ Execution ของ Tree Pre Order Traversal Algorithm โดยการใช้ Iterative Solution จาก Video บน YouTube ได้ ที่นี่

Tree In Order Traversal โดยการใช้ Recursion

เราจะทำการ Implement Tree In Order Traversal Algorithm โดยการใช้ Recursion เราต้องการแวะแต่ละ Node ของ Tree โดยเริ่มต้นด้วย Left Node, แสดง Data ของ Root และจบด้วย Right Node

ดังนั้น เราจำเป็นต้องกำหนด inOrderTraverse Method แบบ Recursive โดยใช้ Node ใน Parameter และดำเนินการดังต่อไปนี้:

• เรียกใช้ inOrderTraverse สำหรับ Left Node
• แสดง Data
• เรียกใช้ inOrderTraverse สำหรับ Right Node

ทำให้เราสามารถ Implement ออกมาได้ดังนี้:

คุณสามารถดูรายละเอียดการ Implementation และ Execution ของ Tree In Order Traversal Algorithm โดยการใช้ Recursion จาก Video บน YouTube ได้ ที่นี่

Tree In Order Traversal โดยการใช้ Iterative solution

เมื่อเราทำการ Implement Tree In Order Traversal Algorithm โดยการใช้ Iterative Solution แน่นอนว่าต้องมีความซับซ้อนขึ้นอีกเล็กน้อย โดยเราจะใช้ Stack of Node เราจะทำการแวะ Tree ในขณะที่ Node ปัจจุบันไม่เป็น Null หรือ Stack of Node ไม่เป็น Null นั่นเอง

การทำ Iteration แต่ละครั้ง เราจะพยายามเข้าถึง Node ที่อยู่ซ้ายสุด จาก Node ปัจจุบัน ในระหว่างที่ทำ Iteration ซ้อนกันไปเรื่อยๆ นั้น เราจะ Add แต่ละ Node ที่แวะแล้วเข้าไปใน Stack of Node และในตอนท้ายของการทำ Iteration นี้ Node ปัจจุบันจะเป็นค่า Null ดังนั้น เราจะทำการ Pop Node ออกจาก Stack และทำการแสดง Data จากนั้นเราก็จะไปแวะ Right Subtree ต่อไป

ทำให้เราสามารถ Implement ออกมาได้ดังนี้:

คุณสามารถดูรายละเอียดการ Implementation และ Execution ของ Tree In Order Traversal Algorithm โดยการใช้ Iterative Solution จาก Video บน YouTube ได้ ที่นี่

Tree Post Order Traversal โดยการใช้ Recursion

ต่อไปเรามาทำการ Implement Tree Post Order Traversal Algorithm โดยการใช้ Recursion กัน เราต้องการแวะแต่ละ Node ของ Tree ที่เริ่มต้นด้วย Left Node แล้วต่อด้วย Right Node จากนั้นก็แสดง Data ของ Root

ดังนั้น เราจำเป็นต้องกำหนด postOrderTraverse Method แบบ Recursive โดยใช้ Node ใน Parameter และดำเนินการดังต่อไปนี้:

• เรียกใช้ postOrderTraverse สำหรับ Left Node
• เรียกใช้ postOrderTraverse สำหรับ Right Node
• แสดง Data

ทำให้เราสามารถ Implement ออกมาได้ดังนี้:

คุณสามารถดูรายละเอียดการ Implementation และ Execution ของ Tree Post Order Traversal Algorithm โดยการใช้ Recursion จาก Video บน YouTube ได้ ที่นี่

Tree Post Order Traversal โดยการใช้ Iterative solution

พอมาถึงการ Implement Tree Post Order Traversal โดยการใช้ Iterative solution ก็ย่อมต้องซับซ้อนขึ้น เราจะเริ่มต้นด้วยการสร้าง Stack of Node ขึ้นมา 2 ตัว โดยจะตั้งชื่อว่า nodeStack1 และ nodeStack2

เราจะเริ่ม Push Root ของ Tree เข้าไปใน nodeStack1 จากนั้นจะทำ Iteration วนซ้ำไปเรื่อยๆ ตราบใดที่ Stack แรกยังไม่ Empty การทำ Iteration แต่ละครั้ง เราจะทำการ Pop Item ออกจาก nodeStack1 และเราจะ Push มันไปที่ nodeStack2 จากนั้นเราก็จะ Push ลูกทางด้านซ้ายและขวา (Left children และ Right children) ของ Item ที่ถูก Pop ออกมา ไปที่ nodeStack1

จากนั้น ใน Loop ที่ 2 เราจะทำการ Print Data ของ Element ทั้งหมดของ nodeStack2

ทำให้เราสามารถ Implement ออกมาได้ดังนี้:

คุณสามารถดูรายละเอียดการ Implementation และ Execution ของ Tree Post Order Traversal Algorithm โดยการใช้ Iterative Solution จาก Video บน YouTube ได้ ที่นี่

Tree Level Order Traversal

สุดท้ายนี้เราจะมา Implement Tree Level Order Traversal Algorithm กัน โดย Algorithm นี้เราจะรู้จักกันในชื่อ Breadth-First Search เราจึงจำเป็นต้องใช้วิธีของ Iterative Solution โดย Solution จะต้องใช้ Queue of Node

เราจะเริ่ม Push Root ของ Tree เข้าไปก่อน จากนั้นจะทำ Iteration วนซ้ำไปเรื่อยๆ ตราบใดที่ Queue ยังไม่ Empty จากนั้นเราจะทำการ Dequeue Node และ Print Data ต่อมาเราจะทำการ Add Children Nodes ในกรณีที่มันไม่ใช่ Null โดยเริ่มจากซ้ายก่อน แล้วตามด้วยขวา

ทำให้เราสามารถ Implement ออกมาได้ดังนี้:

คุณสามารถดูรายละเอียดการ Implementation และ Execution ของ Tree Level Order Traversal Algorithm จาก Video บน YouTube ได้ ที่นี่

สรุป

บทความนี้จะทำให้คุณได้ทราบถึง Algorithms หลักๆ ของ Tree Traversal ด้วยการ Implementation พวกมันในภาษา Java โดยคุณสามารถดู Source ที่ครบถ้วนทั้งหมดของ Tree Class พร้อมการเรียกใช้ Methods ต่าง ได้ ที่นี่

ที่มา: https://hackernoon.com/