Cornario สอน AI ตอน : non-binary tree traversal
posted on 18 Jul 2009 22:48 by dirofblue in Computer, Programming, Software
หลังจากถ่อสังขารไปดูช่างปั้นหม้อขนดก ก็ได้กลับมาทำที่(ใครไม่รู้)รีเควสไว้ ไม่พูดพล่ามทำเพลง เพราะเหนื่อยจนพล่ามไม่ออก ฮร่าๆ เริ่มกันเลย
เอโตะ เนื่องจากไม่เห็นโจทย์เต็มๆเช่นเคย ฟังจากกระรอกมาได้ความว่าให้สร้าง Tree และทำ traversal แบบ preorder,inorder และ postorder รวมทั้งแสดงผลเจ้า Tree นี่ออกมาด้วย และให้เขียนกับ java (อีกแล้วหรอวะ ยิ่งเอ๋อๆอยู่) อะ java ก็จัดไป ตอนแรกก็ตัดสินใจว่าจะใช้ Graph รึว่า JTree ดีแต่เห็นในโจทย์บอกให้ทำ tree ก็เลยตัดสินใจใช้ JTree ไปละกัน เอิ๊กๆ เมื่อเลือกคลาสได้แล้วก็เริ่มกันจริงๆซะที
ขั้นที่ 1 : สร้าง JTree
JTree เป็นคลาสที่อยู่ใน java.swing อย่าลืม import เข้ามาด้วยล่ะเน้อ การประกาศ Jtree ก็เหมือนกับการประกาศคลาสทั่วไปคือใช้ instance JTree name = new JTree(TreeNode) บางคนอาจจะเปิด doc ไปแล้วถามว่าก็เห็นมี new JTree(object[]) ทำไมไม่ใช้อันนั้นล่ะ? ถ้าใช้ object[] ยังงั้นก็ได้เหมือนกันเพียงแต่มันต้องประกาศตอนเริ่มไปเลยทีเดียว แล้วก็จัดการเรื่อง level ค่อนข้างยุ่งยาก เพราะฉะนั้นข้าพเจ้าขอใช้ TreeNode แทนละกัน ซึ่ง TreeNode นี่เป็น Interface อยู่ใน java.swing เช่นเดียวกันประกอบด้วย Interface ย่อย 3 ตัว แต่ในที่นี้เราจะเอาเฉพาะ DefaultMutableTreeNode มาใช้ล่ะนะ เพราะ Tree ของเราเก็บแค่ค่า Integer เท่านั้นเอง ไม่ต้องเอาอะไรมากมาย โฮ่ๆ
ขั้นที่ 2 : Constructor
อาจจะผิดหลักการออกแบบไปบ้าง เพราะเขียนแบบรีบๆ แต่ Constructor ของเราจะยัดทุกอย่างทั้งการสร้าง Tree และการสร้าง GUI มารวมไว้ในที่เดียวกัน ฮ่าๆๆ โดยจะแบ่งหน้าจอเป็นสองส่วนด้วย BorderLayout แล้วใส่ Tree ไว้ด้านเหนือ และปุ่มสำหรับทำ traversal ไว้ด้านใต้ หุๆ ซึ่งเราจะสร้าง Tree ของเราโดยการ instance DefaultMultableTreeNode ชื่อว่า top (ให้เป็น root ไว้ล่ะนะ) แล้วก็วนรับค่าจาก user มาจนกว่าทุก node จะไม่มี child_node (ใส่เลข 0 นั่นแล) แล้วก็ไปทำโครงสร้างของ tree โดยใช้createNodes() จากนั้นก็ instance JTree ขึ้นมาโลด
JTree tree = new JTree(top);
จากนั้นทำส่วนของการ traversal ใส่ปุ่มและ ActionListener ให้เรียบร้อย ก็เป็นอันเสร็จพิธี
ขั้นที่ 3 : actionPerformed();
ส่วนนี้ต้องอธิบายด้วยรึเนี่ย อย่างที่รู้คือจะทำการรับค่าปุ่มว่าจะให้ traverse แบบไหนแล้วเรียก method นั้นมาทำล่ะเนอะ
ขั้นที่ 4 : เตรียมการสำหรับการ traversal
หลังจาก user เลือกชนิดการ traversal แล้วก่อนที่จะเข้าสู่ method เราก็ต้องทำอะไรก่อนเล็กน้อย เนื่องจากการ traverse นั้นจะทำกับ JTree โดยตรงไม่ได้ (ก็ไม่รู้ทำไมล่ะนะ ก็มันไม่ได้อ้ะ) เราจะต้องแปลง tree ให้เป็น TreeModel ซะก่อน ซึ่งวิธีแปลงก็ง่ายๆ โดยใช้
TreeModel treeModel = tree.getModel();
ขั้นที่ 5 : preorder,inorder,postorder
ชื่อก็บอกอยู่แล้วว่าไว้ traverse ตามแบบที่ว่าไปล่ะนะ ส่วนอัลกอฯ ไปดูกันเอาเองละกัน (ฮร่าๆๆ) ไม่มีแรงละ ง่วงงง ไว้พรุ่งนี้(อาจจะ)มาอธิบายอีกที
ไฟล์ src ก็โหลดได้จาก ตรงนี้ เช่นเคย (เบื่อ exteen ใส่ไฟล์ไม่ล่าย T^T)

#1 By PolarHoney on 2009-07-18 23:32