Threaded Binary Tree โครงสร้างข้อมูล Binary Tree โหนดมีได้สูงสุด 2 ลูก แต่ถ้ามี 1 ลูกหรือไม่มี ลิงก์ใน Linked List Representation จะเป็น Null ใช้ Threaded Binary Tree นำลิงก์ว่างมาใช้เป็น Threads
ถ้าโหนดมี Left/Right Child ว่าง ใช้เป็น Thread มี 2 ประเภท: Single Threaded (Left/Right) และ Fully Threaded
- Left Threaded: ไม่มี Left Child → Left Pointer ชี้ Inorder Predecessor
- Right Threaded: ไม่มี Right Child → Right Pointer ชี้ Inorder Successor
- ถ้าไม่มี Predecessor/Successor → ชี้ Header Node
Fully Threaded Binary Tree: โหนดมี 5 Fields: Left Thread Flag, Left Link, Data, Right Link, Right Thread Flag (Boolean บอกว่า Link นั้นเป็น Thread หรือ Real Link)
| Left Thread Flag | Left Link | Data | Right Link | Right Thread Flag |
ตัวอย่าง Left และ Right Threaded Tree:
Fully Threaded Binary Tree:
