ทรี หรือโครงสร้างข้อมูลแบบต้นไม้ ประกอบด้วยโหนด (node) ซึ่งเป็นส่วนที่เก็บข้อมูล ในทรีหนึ่งทรีจะประกอบไปด้วยรูทโหนด (root node) เพียงหนึ่งโหนด แล้วรูทโหนดสามารถแตกโหนดออกเป็นโหนดย่อยๆ ได้อีกหลายโหนดเรียกว่าโหนดลูก (Child node) เมื่อมีโหนดลูกแล้ว โหนดลูกก็ยังสามารถแสดงเป็นโหนดพ่อแม่ (Parent Node) โดยการแตกโหนดออกเป็นโหนดย่อยๆได้อีก
นิยามของทรี
1. นิยามทรีด้วยนิยามกราฟ
ทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด(loopในโครงสร้าง โหนด 2 โหนดในทรีต้องมีทางติดต่อกันทางเดียวเท่านั้น และทรีที่มี N โหนด ต้องมีกิ่งทั้งหมด N-1 เส้น
2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟ
ทรี ประกอบด้วยสมาชิก เรียกว่า โหนด โดยถ้าโหนดว่าง เรียกว่า นัลทรี(Null Tree)และถ้ามีโหนดหนึ่งเป็นโหนดราก ส่วนที่เหลือเป็นทรีย่อย(Sub Tree)
นิยามที่เกี่ยวข้องกับทรี
1. ฟอร์เรสต์(Forest) กลุ่มของทรีที่เกิดจากการเอาโหนดรากของทรีออก
2. ทรีมีแบบแผน(Ordered Tree) ทรีที่โนดต่างๆในทรีมีความสัมพันธ์ที่แน่นอน เช่น ไปทางซ้าย ไปทางขวา เป็นต้น
3. ทรีคล้าย(Similar Tree)ทรีที่มีโครงสร้างเหมือนกัน หรือทรีที่มีรูปร่างเหมือนกัน โดยไม่คำนึงถึงข้อมูลที่อยู่แต่ละโหนด
4. ทรีเหมือน(Equivalent Tree) ทรีที่เหมือนกันโดนสมบูรณ์ โดยต้องเป็นทรีที่คล้ายกันและแต่ละโหนดเดียวกันมีข้อมูลเหมือนกัน
5. กำลัง(Degree) จำนวนทรีย่อยของโหนดนั้นๆ
6. ระดับของโหนด(Level of Node) ระยะในแนวดิ่งของโหนดนั้นๆที่อยู่ห่างจากโหนดราก และจำนวนเส้นทางตามแนวดิ่งของโหนดใดๆ ซึ่งห่างจากโหนดราก เรียกว่า ความสูง หรือความลึก
การแทนที่ทรีในหน่วยความจำหลัก
การแทนที่ต้องมีพอยเตอร์เชื่อมโยงจากโหนดแม่ไปยังโหนดลูก แต่ละโหนดต้องมีลิงค์ฟิลด์ เพื่อเก็บที่อยู่ของโหนดลูกต่างๆ นั่นคือ จำนวนลิงค์ฟิลด์ของแต่ละโหนดขึ้นอยู่กับจำนวนของโหนดลูก การแทนที่ทรีมีวิธีการ ดังต่อไปนี้
1. โหนดแต่ละโหนดเก็บพอยเตอร์ไปยังโหนดลูกทุกโหนด การแทนที่วิธีนี้ ทำให้จำนวนฟิลด์แต่ละโหนดเท่ากัน และให้ลิงค์ฟิลด์แรกเก็บค่าพอยเตอร์ชี้ไปยังโหนดลูกลำดับที่หนึ่ง ลิงค์ฟิลด์สองเก็บค่าพอยเตอร์ชี้ไปยังโหนดลูกที่สอง และลิงค์ฟิลด์อื่นเก็บค่าพอยเตอร์ของโหนดลูกลำดับถัดไปเรื่อยๆ
2. แทนที่ด้วยไบนารีทรี เป็นการแก้ปัญหาเพื่อลดการสิ้นเปลืองเนื้อที่ในหน่วยความจำหลัก คือกำหนดลิงค์ฟิลด์ให้มีจำนวนน้อยที่สุดเท่าที่จำเป็นเท่านั้น โดยกำหนดให้แต่ละโหนดมีจำนวนลิงค์ฟิลด์สองลิงค์ฟิลด์
- ลิงค์ฟิลด์แรกเก็บที่อยู่โหนดลูกคนโต
- ลิงค์ฟิลด์ทีสองเก็บที่อยู่ของโหนดพี่น้องที่เป็นโหนดถัดไป โหนดใดไม่มีลูกหรือพี่น้อง ลิงค์ฟิลด์จะมีค่าเป็น Null
การแปลงทรีทั่วไปให้เป็นไบนารีทรี
1. ให้โหนดแม่ชี้ไปยังโหนดลูกคนโต แล้วลบความสัมพันธ์ระหว่างแม่และโหนดลูกอื่นๆ
2. ให้เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง
3. จับให้ทรีย่อยทางขวาเอียงลงมา 45 องศา
การท่องไปในไบนารีทรี
1. การท่องแบบพรีออร์เดอร์(Preorder Traversal) เป็นการเดินเข้าไปเยือนโหนดต่างๆด้วยวิธี NLR มีขั้นตอน ดังนี้
- เยือนโหนดราก
- ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
- ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์
2. การท่องไปแบบอินออร์เดอร์(Inorder Traversal)เป็นการเยือนโหนดต่างๆด้วยวิธี LNR มีขั้นตอน ดังนี้- ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
- เยือนโหนดราก
- ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์
3. การท่องไปแบบโพสออร์เดอร์(Postorder Traversal) เป็นการเยือนโหนดต่างๆด้วยวิธี LRN มีขั้นตอน ดังนี้- ท่องไปในทรีย่อยทางซ้ายแบบโพสต์ออร์เดอร์
- ท่องไปในทรีย่อยทางขวาแบบโพสต์ออร์เดอร์
- เยือนโหนดราก
การทำงานของคิว
- การนำสมาชิกออกจากคิว เรียกว่า dequeue คือ การนำออกจากส่วนหน้าของคิว และให้ข้อมูลนั้นกับ element 