วันอาทิตย์ที่ 20 มกราคม พ.ศ. 2551

โครงสร้างข้อมูลแบบต้นไม้ (Tree)

*โครงสร้างข้อมูลแบบต้นไม้ (Tree)
-นิยามโครงสร้างของต้นไม้
-ต้นไม้ที่มีแบบแผน
-การแทนโครงสร้างต้นไม้ในคอมพิวเตอร์
-โครงสร้างข้อมูลต้นไม้ไบนารี (Binary Tree)
-การแทนต้นไม้ไบนารีในหน่วยความจำ

Data Structure and Algorithmโครงสร้างข้อมูลและอัลกอริทึม
โครงสร้างข้อมูลแบบต้นไม้
-เป็นโครงสร้างไม่เชิงเส้น (Non Linear) มีลักษณะคล้ายกิ่งก้านต้นไม้ แตกกิ่งก้านออกไป เช่นเดียวกับธรรมชาติของข่าวสารข้อมูล
-ต้นไม้แตกกิ่งจากล่างไปบน แต่โครงสร้างข้อมูลในคอมพิวเตอร์จะกลับหัว รากอยู่บน กิ่งอยู่ด้านล่าง
-จุดที่แตกกิ่งออกไป เรียกว่าโหนด (Node) ข่าวสารเก็บอยู่ที่โหนด
-จุดเชื่อมโหนดเรียกว่าลิงค์ (Link)

*นิยามโครงสร้างต้นไม้
-โหนดพิเศษเรียกว่า รากหรือรูต (root node), R
-โหนดอื่น ๆ ที่ไม่ใช่รูต ถูกแบ่งย่อยออกเป็น n กลุ่ม แต่ละกลุ่มไม่มีโหนดร่วมกันเลย แต่ละกลุ่มก็เป็นต้นไม้เหมือนกัน แต่เรียกว่าเป็นต้นไม้ย่อย (Sub tree)
โครงสร้างต้นไม้ R คือรูตโหนดของต้นไม้ ย่อย A,B,C,D A คือรูตโหนดของต้นไม้ ย่อย E, F, G F คือรูตโหนดของต้นไม้ ย่อย J B คือรูตโหนดของต้นไม้ย่อย H และ I

การเรียกชื่อส่วนต่าง ๆ ของต้นไม้
ลักษณะลำดับของโครงสร้างต้นไม้ จะเรียกเช่นเดียวกับการลำดับบรรพบุรุษ
เช่น Father, Son, Grandson
บางทีก็ลำดับอีกแบบเช่น Mother, Child, Grandchild
ระดับของโหนด (Level)
แสดงถึงระยะทางตามแนวดิ่งว่าโหนดนั้นห่างจากรูตโหนดเท่าไร
ถ้ากำหนดให้รูตโหนดเป็นระดับ 1 (บางที่กำหนดให้รูตโหนดเป็นระดับ 0)
ให้นับระยะห่างบวกระดับของรูตโหนด เช่น 3 + 1 (หรือ 3 + 0) เป็นต้น
ระดับของโหนด
R คือรูตโหนด ระดับ 1
A,B,C,D คือโหนดระดับ 2
E,F,G,H,I คือโหนดระดับ 3
J คือโหนดระดับ 4

ดีกรีของโหนด (Level Degree)

คือจำนวนต้นไม้ย่อยของโหนดนั้น
A มีดีกรี เป็น 3
B มีดีกรี เป็น 2
F มีดีกรีเป็น 1
C,D,E,G,H,I,J มีดีกรีเป็น 0

*ต้นไม้ที่มีแบบแผน (Ordered Tree)
คือต้นไม้ที่มีการกำหนดความสัมพันธ์ชัดเจน เช่น ก่อน, ไปทางซ้าย, ไปทางขวา
ต้นไม้ที่ไม่มีแบบแผน (Unordered Tree)
คือต้นไม้ที่ไม่กำหนดความสัมพันธ์ที่ชัดเจน จะดูจากจำนวนโหนด หรือลิงค์เป็นหลัก
*โครงสร้างข้อมูลต้นไม้ไบนารี (Binary Tree)
-ต้นไม้ไบนารี ประกอบด้วยรูตโหนดและต้นไม้ไบนารี 2 กลุ่ม ที่ไม่มีโหนดร่วมกัน หรืออาจเป็นต้นไม้ที่ว่างเปล่า
-ต้นไม้ย่อยด้านซ้าย เรียกว่า left subtree
-ต้นไม้ย่อยด้านขวา เรียกว่า right subtree
-ต้นไม้ที่ว่างเปล่า คือ ต้นไม้ที่มีแต่รูตโหนดเพียงโหนดเดียว ไม่มีต้นไม้ย่อย