โครงสร้างข้อมูลแบบต้นไม้ (Tree Data Structure)
โครงสร้างข้อมูลแบบต้นไม้ (Tree Data Structure)
โครงสร้างข้อมูลแบบต้นไม้เป็นโครงสร้างชนิดไม่เชิงเส้นที่สําคัญที่สุดของโครงสร้างข้อมูล โครงสร้างต้นไม้มีความสัมพันธ์อย่างใกล้ชิดกับธรรมชาติของข่าวสารและวิธีการแปลงข่าวสารมาก โครงสร้างต้นไม้มีลักษณะที่สมชื่อของตนเอง เพราะมีลักษณะคล้ายกิ่งก้านของต้นไม้ต้นไม้ตามธรรมชาติ จะงอกจากล่างไปบน ส่วนโครงสร้างข้อมูลที่มีลักษณะต้นไม้นั้นเราจะวาดหรือให้เจริญจากบนลงมาล่างดังรูป จุดที่มีการแตกกิ่งก้านสาขาออกไปจะเรียกว่าโหนด (node) โดยข่าวสารจะเก็บอยู่ที่โหนด กิ่งที่ต่อระหว่าง โหนด จะแสดงความสัมพันธ์ระหว่างโหนดเรียกว่าลิงค์(link)
โครงสร้างข้อมูลแบบต้นไม้
1. เป็นโครงสร้างไม่เชิงเส้น (Non Linear) มีลักษณะคล้ายกิ่งก้านต้นไม้แตกกิ่งก้านออกไป
2. ต้นไม้แตกกิ่งจากล่างไปบน แต่โครงสร้างข้อมูลในคอมพิวเตอร์จะกลับหัว รากอยู่บน กิ่งอยู่ด้านล่าง
3. จุดที่แตกกิ่งออกไป เรียกว่าโหนด (Node) ข่าวสารเก็บอยู่ที่โหนด
4. จุดเชื่อมโหนดเรียกว่าลิงค์(Link)
นิยามโครงสร้างต้นไม้
1. มีโหนดพิเศษเรียกว่า รากหรือรูต (root node), R
2. โหนดอื่น ๆ ที่ไม่ใช่รูต ถูกแบ่งย่อยออกเป็น n กลุ่ม แต่ละกลุ่มไม่มีโหนดร่วมกันเลย แต่ละกลุ่ม ก็เป็นต้นไม้เหมือนกัน แต่เรียกว่าเป็นต้นไม้ย่อย (Sub tree)
โครงสร้างต้นไม้
R คือรูตโหนดของต้นไม้ย่อย A,B,C,D
A คือรูตโหนดของต้นไม้ย่อย E, F, G
F คือรูตโหนดของต้นไม้ย่อย J
B คือรูตโหนดของต้นไม้ย่อย H และ I
ซับทรี (Subtree) หมายถึง โครงสร้างที่เชื่อมต่อกันภายใต้ Root โดย Node แรกของSubtree จะเป็น Root ของ Subtree นั้น
Subtree สามารถแบ่งย่อยเป็น Subtree ได้อีกจนกว่าจะ Empty
ต้นไม้แบบไบนาทรี (Binary Tree) หมายถึง ทรีที่มีโหนดลูกไม่เกินสองโหนดจะประกอบด้ายโหนดลูกทางซ้าย (Left child) และโหนดลูกทางขวา (Right child) โหนดลูกอ่าจเป็นที่ย่อยก็ได้ ซึ่งแบ่งออกเป็นทรีย่อยทางซ้ายและทรีย่อยทางขวา และโหนดลูกแต่ละโหนดอาจมีโหนดลูกเพี่ยงด้านซ้ายหรือด้านขวาด้านเดี่ยวก็ได้ สำรับโหนดของทรีที่มีจำนวนเป็น 0เรี่ยกว่า ทรีว่าง (Empty Tree)
การท่องเข้าไปในไบนารีทรี(Tree Traversal)
Tree Traversal หมายถึง การไปยังโหนดเพื่อประมวลผลบางอย่างที่ต้องการกระทำกับโหนดนั้น เช่น หาข่าวสาร
Tree Traversal แบ่งออกเป็น 3 วิธี (ที่นิยมใช้)
1. Pre-Order Traversal
2. In-Order Traversal
3 .Post-Order Traversal
การสร้าง Enpression Tree
เป็นต้นไม้ที่สร้างขึ้นจากตัวกระทำ (operand) และเคื่องหมาย (operators) ทางคณิตศาสตร์ของนิพจน์โดยการว่างตัวกระทำโหนดใบ(leave node) และว่างเครื่องหมายไว้ ที่โหนดภายใน
สำรับเครื่องหมายที่เป็นเครื่องหมายเดี่ยว (unary operator) จะมีกิ่งย่อยเพี่ยงต้นไม้เดี่ยว เรามักจะวาง เครื่องหมายเดี่ยวไว้ทางซ้ายของตัวกระทำ ซึ่งเครื่องหมายที่จัดเป็นเครื่องหมายเดี่ยว ได้แก่ Log() cos()และมีเครื่องหมายเดี่่ยว ที่ถูกจัดวางไหว้ทางขวาของตัวกระทำ ได้แก่ แฟกทอเรียล ฟังก์ชัน เลกยกกำหลังต่างๆ
จะได้ว่า
- การเยี่ยมโหนด แบบอินออเดอร์จะได้ X-Y/R*D ซึ่งอยู่ในรูปอินฟิกฟอร์ม
- การเยี่ยมโหนด แบบพรีออเดอร์จะได้ -X*/YRD ซึ่งอยู่ในรูปพรีฟิกฟอร์ม
- การเยี่ยมโหนดแบบโพสออเดอร์จะได้ XYR/D*- ซึ่งอยู่ในรูปโพสฟีกฟอร์ม
ความคิดเห็น
แสดงความคิดเห็น