บทที่ 5 Defination of a Tree Structure

Defination of a Tree Structure

·         ต้นไม้คือโครงสร้างที่ประกอบ ด้วยโหนด โดยโหนดเริ่มต้นเรียกว่ารากหรือรูท(Root Node) มีการเชื่อมโยงไปยังอื่นด้วยพอยเตอร์ แต่ละโหนดที่ถูกชี้โดยรูทมีพอยเตอน์ชี้ไปยังโหนดถัดไปเรื่อยๆหลายระดับ (Level) มองเป็นระดับชั้นเหมือนต้นไม้ เพราะแต่ละชั้นจะมีโหนดเชื่อมโยงไปยังชั้นลำดับถัดไปเรื่อยๆ จนกว่าจะถึงปลายโหนด

Tree

·         กราฟที่ต่อเนื่องโดยไม่มีวงจร ปิด (Loop) ในโครงสร้าง โหนดสองโหนดใดๆ ในทรีมีทางติดต่อกันทางเดียวเท่านั้น

·         ทรีที่มี N Nodes ต้องมีกิ่งทั้งหมด N-1 Branchs

·         การเขียนรูปแบบทรี เขียนได้ 4 แบบ

ก.) Tree แบบมีรากอยู่ด้านบน

ข.) Tree แบบมีรากอยู่ด้านล่าง

ค.) Tree แบบมีรากอยู่ด้านซ้าย

ง.) Tree แบบมีรากอยู่ด้านขวา

ทรี ที่มีแบบแผน (Ordered Tree) หมายถึง ทรีที่โหนดต่างๆในทรีนั้นมีความสัมพันธ์ที่แน่นอน เช่นไปทางขวาไปทางซ้าย

ทรี คล้าย (Similar Tree) คือ ทรีที่มีโครงสร้างเหมือนกัน หรือทรีที่มีรูปร่างของทรีเหมือนกัน โดยไม่คำนึงถึงข้อมูลที่อยู่ในแต่ละโหนด

การแทนที่ทรีใน หน่วยความจำหลัก

1. การแทนที่ทรีซึ่งแต่ละโหนดเก็บพอยเตอร์ชี้ไปยังโหนดลูก

2. แทนที่ด้วย Binary Tree โหนดทุกโหนดใน Binary Tree จะมีลูกไม่เกิน 2

การ เก็บโครงสร้างข้อมูลแบบไบนารี ทรีลงในหน่วยความจำมี 2 วิธี

1. การแทนที่ Tree ด้วย Stack Array

·         จะต้องเป็น Complete Binary Tree หรือ Almost Binary Tree

·         เหมาะสำหรับการใช้งานกรณี ข้อมูลไม่มีการ เปลี่ยนแปลง หรือมีการเปลี่ยนแปลงน้อยมาก

·         ไม่เหมาะกับข้อมูลที่มีการ เปลี่ยนแปลงอยู่ ตลอดเวลา

2. การแทนที่ Binary ด้วย Array

การ ท่องไปในทรี (Traversing Binary Tree)

N : root node เป็นโหนดเริ่มต้นของโครงสร้าง

L  : Sub node ไปทางซ้าย

R  : Sub node ไปทางขวา

NLR , LNR , LRN , NRL , RNL , RLN

Preorder Traversal (NLR)

ABDGCEHIF

Inorder Traversal (LNR)

DGBAHEICF

Postorder Traversal (LRN)

GDBHIEFCA

Expreesion Tree

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

นิพจน์ของทรี

·         ตัวดำเนินการ (Operator) คือ สัญลักษณ์ทางคณิตศาสตร์ เช่น +,-,*,/

·         ตัวถูกดำเนินการ (Operand) คือ ค่าต่างๆหรือตัวแปรนั่นเอง เช่น x,y,a,48

Expression Tree มีความสำคัญตามลำดับดังนี้

1.               วงเล็บ

2.               ยกกำลัง

3.               คูณ,หาร

4.               บวก,ลบ

5.               ถ้ามีเครื่องหมายระดับเดียวกัน ให้ทำจากซ้าย ไปขวา

ตัวอย่าง (2 × (a −1) + (3 × b))