บทที่ 5 โครงสร้างแบบทรี

โครงสรา้ งข้อมูล แบบทรี (Tree)

เป็นโครงสร้างข้อมูลแบบต้นไม้ ประกอบไปด้วย Root Node เพียง Node เดยี ว Root node Child node Leaf child node Root node คอื node ราก มีเพยี ง node เดียว Child node คือ node ลูก ทมี่ ลี ูกไดต้ ้ังแต่ 0- N node Leaf child node คือ node สุดท้ายที่ไม่มีลูกต่อ หรือ node ใบ การเดินทางเข้าไปในทรมี ี 3 แบบ คคอื

การเดนิ เข้าไปในทรี มี 3 แบบ ดงั น้ี 1. Pre Order 2. In Order 3. Post Order Pre Order เรมิ่ ตน้ จาก Root node ไปยัง Left child node แลว้ ไปยงั Right child node จนครบ (Root - Left - Righ ) ABDECFI

In Order เรม่ิ ตน้ จาก Left child node ไปยงั Root node แล้วไปยงั Right child node จนครบ (Left - Root - Righ ) D BEAFCI

Post Order เรมิ่ ตน้ จาก Left child node ไปยงั Right child node e แลว้ ไปยงั Root nodจนครบ (Left - Righ - Root) DEBFICA

ตวั อยา่ ง 1 A F B G DC E HI Pre J In Post

ตวั อยา่ ง 2 T G H o RF HJ PM Pre In W Post

ตวั อย่าง 3 B A U C J M W W K N D EG QH Pre In A Post

สรา้ งทรี การเพม่ิ ขอ้ มลู ในทรี 1. ถา้ ไบนารว่ี า่ ง ขอ้ มลู ทจี่ ะเขา้ เปน็ Root node 2. ถา้ ไบนาร่ไี มว่ า่ ง ใหท้ าการเพม่ิ ขอ้ มลู ดงั นี้ - ถา้ node ทเี่ ขา้ มาใหมม่ ากกวา่ Root node ใหเ้ พม่ิ node ใหมล่ งในไบ นารขี่ า้ งขวา - ถา้ node ทเี่ ขา้ มาคา่ นอ้ ยกวา่ Root node ให้เพมิ่ node ใหมล่ งในไบ นารข่ี า้ งซา้ ย ตัวอยา่ ง 1 5 5 8 2 7 11 10 28 7 11 10

ตวั อย่าง 2 58 94 51 26 35 9 11 57