Tree

Tree

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

องค์ประกอบของทรีประกอบด้วย

โหนดราก (Root Node) คือโหนด A ซึ่งโหนดรากหรือรูทโหนดถือเป็นโหนดแรกสำรับโครงสร้างทรีเป็นโหนดเริ่มต้นเพื่อขยายลูกหลานต่อไป
โหนดพ่อ (Parents) คือโหนด A,B และ F ก็คือโหนดที่มี Successor
โหนดลูก (Children) B,E,F,C,D,G,H และ I ซึ่งก็คือโหนดที่มี Predecessor
โหนดพี่น้อง (Siblings) คือโหนด {B,E,F},{C,D}และ {G,H,I}
โหนดใบ (Leaf Node) คือโหนด C,D,E,G,H และ I ซึ่งก็คือโหนดที่ไม่มี Successor
ดีกรี (Degree) ทั้งหมดของทรี มีค่าเท่ากับ 8
ดีกรี (Degree) ทั้งหมดของโหนด F มีค่าเท่ากับ 3
จำนวนของ Leaf โหนด มีค่าเท่ากับ 6
ระดับความสูงหรือความลึกของทรี

-คำนวนได้จากสูตร Height = 2+1+3

ซับทรี (Subtree)

Subtree หมายถึง โครงสร้างที่เชื่อมต่อกันภายใต้ Root โดย Node แรกของ Subtree จะเป็น Root ของ Subtree นั้น

Subtree สามารถแบ่งย่อยเป็น Subtree ได้อีกจนกว่าจะ Empty

ต้นไม้แบบไบนาทรี (Binary Tree)

ไบนาทรี หมายถึง ทรีที่มีโหนดลูกไม่เกินสองโหนดจะประกอบด้ายโหนดลูกทางซ้าย (Left child) และโหนดลูกทางขวา (Right child) โหนดลูกอ่าจเป็นที่ย่อยก็ได้ ซึ่งแบ่งออกเป็นทรีย่อยทางซ้ายและทรีย่อยทางขวา และโหนดลูกแต่ละโหนดอาจมีโหนดลูกเพี่ยงด้านซ้ายหรือด้านขวาด้านเดี่ยวก็ได้ สำรับโหนดของทรีที่มีจำนวนเป็น 0 เรี่ยกว่า ทรีว่าง (Empty Tree)

การแทนไบนารีทรีในหน่วยความจำ(Binary Tree Representtions)

การแทนไบนารีทรีด้วยอาร์เรย์
การแทนไบนารีทรีด้วยลิงก์ลิสต์

การท่องเข้าไปในไบนารีทรี(Tree Traversal)

Tree Traversal หมายถึง การไปยังโหนดเพื่อประมวลผลบางอย่างที่ต้องการกระทำกับโหนดนั้น เช่น หาข่าวสาร

Tree Traversal แบ่งออกเป็น 3 วิธี (ที่นิยมใช้)

1.Pre-Oeder Traversal

2.In-Oeder Traversal

3.Post-Oeder Traversal

การสร้าง Enpression Tree

เป็นต้นไม้ที่สร้างขึ้นจากตัวกระทำ (operand) และเคื่องหมาย (operators) ทางคณิตศาสตร์ของนิพจน์โดยการว่างตัวกระทำโหนดใบ(leave node) และว่างเครื่องหมายไว้ ที่โหนดภายใน

สำรับเครื่องหมายที่เป็นเครื่องหมายเดี่ยว (unary operator) จะมีกิ่งย่อยเพี่ยงต้นไม้เดี่ยว เรามักจะวาง เครื่องหมายเดี่ยวไว้ทางซ้ายของตัวกระทำ ซึ่งเครื่องหมายที่จัดเป็นเครื่องหมายเดี่ยว ได้แก่ Log() cos()และมีเครื่องหมายเดี่่ยว ที่ถูกจัดวางไหว้ทางขวาของตัวกระทำ ได้แก่ แฟกทอเรียล ฟังก์ชัน เลกยกกำหลังต่างๆ

จะได้ว่า