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

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

รูป 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

                  ก่อนลำดับได้ 9 4 3 6 5 7 17 22 20

                  ตามลำดับได้ 3 4 5 6 7 9 17 20 22

                  หลังลำดับได้ 3 5 7 6 4 20 22 17 9

                  จะสังเกตว่า 9 ซึ่งเป็นโหนดรากจะอยู่ในตำแหน่งตามชื่อของลำดับ ก่อนลำดับอยู่หน้าสุด ตามก็อยู่ตรงกลาง หลังก็อยู่หลังสุด

รูป6-17

บรรทัดที่ 289 : สร้างเมท็อด inOrder รับอินพุทเป็น VisitTree (อินเตร์เฟส จะกล่าวต่อไป)

บรรทัดที่ 291 : ตรวจสอบว่าถ้ารากเป็น null ให้คืนค่าออกไป

บรรทัดที่ 292 : ถ้าไม่ null ให้เรียกเมท็อด inOrder

บรรทัดที่ 295 : สร้างเมท็อด inOrder

บรรทัดที่ 297 : ตรวจสอบซ้ำว่าถ้ารากเป็น null ให้คืนค่าออกไป

บรรทัดที่ 298 : ไล่โหนดทางซ้ายให้หมด

บรรทัดที่ 299:จากนั้นให้ผ่านข้อมูลของ n ตรงกลางด้วยเมท็อด visit ของอินเตอร์เฟส VisitTree

บรรทัดที่ 300 : ไล่โหนดทางขวาให้หมด

รูป6-18

                  เปลี่ยนจากโค๊ดข้างบนมาเป็นให้ผ่านข้อมูลของ n ก่อน

รูป6-19

                  ผ่านข้อมูลของ n ทีหลังสุด

รูป 6-20

                  สร้างอินเตอร์เฟสข  VisitTreeI

รูป 6-21