วันพฤหัสบดีที่ 20 เมษายน พ.ศ. 2560
บทที่ 6
โครงสร้างข้อมูลแบบต้นไม้ Tree
การเปลี่ยน Tree เป็น Bineeary 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
การสร้างต้นไม้แบบใบนาทรี (Binary Tree)
ใบน่าทรี หมายถึง ทรีที่มีโหนดลูกไม่เกินสองโหนดจะประกอบด้ายโหนดลูกทางซ้าย (Left child) และโหนดลูกทางขวา (Right child) โหนดลูกอ่าจเป็นที่ย่อยก็ได้ ซึ่งแบ่งออกเป็นทรีย่อยทางซ้ายและทรีย่อยทางขวา และโหนดลูกแต่ละโหนดอาจมีโหนดลูกเพี่ยงด้านซ้ายหรือด้านขวาด้านเดี่ยวก็ได้ สำรับโหนดของทรีที่มีจำนวนเป็น 0 เรี่ยกว่า ทรีว่าง (Empty Tree)
ตัวอย่าง
การสร้างใบนาทรีแบบสมบูรณ์
เป็นการสร้างต้นไม้ใบนารีแต่ละโหนดภายในมีโหนดย่อยซ้อยและขวา(มั่นคือแต่ละโหนดภายใน lett son และ right son) และโหนดใบ (leaf nodes) ทั้งหลายอยู่ในระดับที่ n รูป
ตัวอยู่างในนารีสมบูรณ์ที่มี 3 ระดับ
การเปลี่ยน Tree เป็น Bineeary Tree
- พิจารณากิ่งที่อยู่ทางซ้ายสุดที่อยู่ใต้พ่อเดี่ยวกัน
- ต่อกิ่งของโหนดทางซ้ายสุดในขั้นที่ 1 ไปทางขวาทางลำดัยอาวุโสกับพี่น้องที่เกิดจากพ่อเดี่ยวกัน
- ทำขั้นที่ 1 และ 2 จนครบทุกโหนด
- ปรับมุ่มของแต่ละกิ่ง ประมาณ 45 องศา
ตัวอย่าง
การท่องผ่าน Binary
เป็นการเข้าไปในโครงสร้างต้นไม้เพื่อสร้างข้อมูลในโหนดมาแสดง หรื่อเพื่อการค้นหา การประมวลผลและการเดินเยี่ยมโหนดจะมี 3 ขั้นตอนดั่งนี้- Inorder traversel หรือ smmyetrit order จะทำการเยี่ยมโหนดในต้นไม้ย่อยทางซ้ายแบบอินออเดอร์ กอนเยี่ยมโหนดรากและเยี่ยมโหนดในต้นไม้ย่อยทางขวาแบบอินออเดอร์ (Root/Left/Right)
- Preorder traversel จะทำการเยี่ยมโหนดรากก่อนเยี่ยใโหนดในต้นไม้ย่อยทางซ้ายแบบพรีออเดอร์ และเยี่ยมโหนดในต้นไม้ย่อมทางขวาแบบพรี(Root/Left/Right)
- postorder traversel หรือ Enorder จะทำการเยี่ยมโหนดในต้นไม้ย่อยทางซ้ายแบบ โพสออเดอร์ กอนเยี่ยมโหนดต้นไม้ย่อยทางขวาแบบ โพสออเดอร์ และเยี่ยมโหนดราก(Left/Right/Root)
ตัวอย่าง
- แบบอินออเดอร์ (Root/Left/Right) DB A EG C HFI
- แบบอินออเดอร์ (Root/Left/Right) ABD CEG FHI
- แบบอินออเดอร์ (Left/Right/Root) DB GE HIE
การสร้าง Enpression Tree
เป็นต้นไม้ที่สร้างขึ้นจากตัวกระทำ (operand) และเคื่องหมาย (operators) ทางคณิตศาสตร์ของนิพจน์โดยการว่างตัวกระทำโหนดใบ(leave node) และว่างเครื่องหมายไว้ ที่โหนดภายใน
สำรับเครื่องหมายที่เป็นเครื่องหมายเดี่ยว (unary operator) จะมีกิ่งย่อยเพี่ยงต้นไม้เดี่ยว เรามักจะวาง เครื่องหมายเดี่ยวไว้ทางซ้ายของตัวกระทำ ซึ่งเครื่องหมายที่จัดเป็นเครื่องหมายเดี่ยว ได้แก่ Log() cos()
และมีเครื่องหมายเดี่่ยว ที่ถูกจัดวางไหว้ทางขวาของตัวกระทำ ได้แก่ แฟกทอเรียล ฟังก์ชัน เลกยกกำหลังต่างๆ
ตัวอย่าง แสดงการสร้างเอ็กเพรสชันทรีจากนิพจท์ (x-((Y/R)*D))
จะได้ว่า
- การเยี่ยมโหนด แบบอินออเดอร์จะได้ X-Y/R*D ซึ่งอยู่ในรูปอินฟิกฟอร์ม
- การเยี่ยมโหนด แบบพรีออเดอร์จะได้ -X*/YRD ซึ่งอยู่ในรูปพรีฟิกฟอร์ม
- การเยี่ยมโหนดแบบโพสออเดอร์จะได้ XYR/D*- ซึ่งอยู่ในรูปโพสฟีกฟอร์ม
