Data Structure Java

ไบนารีเสิร์ชทรี (ต่อ2)

การค้นหาในต้นไม้

หารค้นหาในต้นไม้อาศัยเรื่องโครงสร้างต้นไม้มาช่วยในการค้นหา ก็คือลูกทางซ้ายมีค่าน้อยกว่ารากและลูกทางขวามีค่ามากกว่าราก วิธารก็คือให้เปรียบเทียบข้อมูลตั้งแต่รากลงไปว่าข้อมูลที่ต้องการหามีค่ามากหรือน้อยกว่ารากหรือโหนด ไล่ไปเรื่อยๆจนเจอข้อมูล

รูป 6-13

บรรทัดที่ 176 : สร้างเมท็อด get สำหรับการค้นหา

บรรทัดที่ 178 : สร้างโหนด a โดยให้ a เรียกและเก็บข้อมูลที่ได้จาก getNode

บรรทัดที่ 179 : ถ้า a ไม่มีข้อมูลใหคืนค่าเป็น -1

บรรทัดที่ 180 : ถ้ามีข้อมูลให้คืนค่าเป็นข้อมูลที่อยู่ในโหนดนั้น

บรรทัดที่ 182 : : สร้างเมท็อด getNode สำหรับหาโหนดในต้นไม้

บรรทัดที่ 184 : ถ้ารากเป็น null ให้จบการทำงานคืนค่าเป็น null กลับไปให้ a

บรรทัดที่ 185-186 : ถ้ารากมีค่ามากกว่าข้อมูลที่เข้ามา ให้ไปหาข้อมูลจากโหนดทางซ้าย

บรรทัดที่ 189-191 : ถ้ารากมีค่าน้อยกว่าข้อมูลที่เข้ามา ให้ไปหาข้อมูลจากโหนดทางขวา

บรรทัดที่ 193 : คืนค่าออกไป

สรุปคือผู้ใช้เรียก get ส่วน get จะไปเรียก getNode เพื่อว่ามีโหนดที่เก็บข้อมูลที่ตรงกับข้อมูลที่เข้ามาหรือไม่ ถ้ามีก็คืนโหนดออกไป แล้ว get ก็จะคืนค่าเป็นข้อมูลที่อยู่ในโหนดนั้นออกมา

การค้นหาค่ามากและค่าสุดน้อยสุดในต้นไม้

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

รูป 6-14

จากรูปข้อมูลที่น้อยที่สุดก็คือ 3 เริ่มจาก 9 เลื่อนซ้าย ได้ 4 เลื่อนซ้ายได้ 3 ก็พบว่าไม่มีลูกทางซ้ายของ 3 อีก 3 จึงเป็นข้อมูลที่น้อยที่สุดแล้ว

ส่วนข้อมูลที่มากที่สุดคือ 22 เริ่มจาก 9 เลื่อนขวา ได้ 17 เลื่อนขวา ได้ 22 ไม่มีลูกทางขวาของ 22 แล้ว 22 จึงเป็นข้อมูลมากสุด

รูป 6-15

บรรทัดที่ 196 : สร้างเมท็อด getMin สำหรับหาค่าน้อยสุด

บรรทัดที่ 198-199 : สร้างตัวแปร n ให้เป็นราก ถ้ารากไม่มีข้อมูลให้คืนค่า -1 หมายถึงไม่มีข้อมูล

บรรทัดที่ 200-202 : ตรวจสอบลูปว่าถ้าด้านซ้ายของรากยังไม่พบว่าว่างให้เลื่อนไปทางซ้ายหนึ่งครั้ง

บรรทัดที่ 204 : หากไม่มีข้อมูลทางซ้ายแล้วให้คืนข้อมูลตัวล่าสุดออกไป

บรรทัดที่ 207 : สร้างเมท็อด getMax สำหรับหาค่ามากสุด

บรรทัดที่ 209-210 : สร้างตัวแปร n ให้เป็นราก ถ้ารากไม่มีข้อมูลให้คืนค่า -1 หมายถึงไม่มีข้อมูล

บรรทัดที่ 211-213 : ตรวจสอบลูปว่าถ้าด้านขวาของรากยังไม่พบว่าว่างให้เลื่อนไปทางขวาหนึ่งครั้ง

บรรทัดที่ 215 : หากไม่มีข้อมูลทางขวาแล้วให้คืนข้อมูลตัวล่าสุดออกไป

การผ่านต้นไม้(Tree traversal)

เป็นการดูข้อมูลในโหนดโดยเป็นการผ่านโหนดแบบเป็นลำดับ แต่ละโหนดนั้นจะถูกผ่านได้เพียงครั้งเดียว การผ่านต้นไม้แบบมาตรฐานทั่วไปมี 3 แบบได้แก่ ก่อนลำดับ(preorder) ตามลำดับ(inorder)และหลังลำดับ(postorder)

รูป 6-16