ทรี (Tree)
เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ระหว่างโหนดจะมีความสัมพันธ์
ลดหลั่นกันเป็นลำดับชั้น(Hierarchical Relationship)
แต่ละโหนดจะมีความสัมพันธ์กับโหนดในระดับที่ต่ำลงมา
หนึ่งระดับได้หลายๆโหนดเรียกโหนดดังกล่าวว่า โหนดแม่
(Parent orMother Node) โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่หนึ่งระดับ
เรียกว่า โหนดลูก(Child or Son Node)
โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่เรียกว่าโหนดราก(Root Node)
-โหนดที่มีโหนดแม่เป็นโหนดเดียวกันเรียกว่า โหนดพี่น้อง (Siblings)
โหนดที่ไม่มีโหนดลูก เรียกว่าโหนดใบ (Leave Node) เส้นเชื่อมแสดง
ความสัมพันธ์ระหว่าง โหนดสองโหนดเรียกว่า กิ่ง (Branch)
นิยามของทรี
1. นิยามทรีด้วยนิยามของกราฟทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด
(loop) ในโครงสร้าง โหนดสองโหนดใด ๆ ในทรีต้องมีทางติดต่อกัน
ทางเดียว เท่านั้น และทรีที่มี N โหนด ต้องมีกิ่งทั้งหมด N-1 เส้น
2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟทรีประกอบด้วยสมาชิกที่เรียกว่าโหนด
โดยที่ ถ้าว่าง ไม่มีโหนดใด ๆ เรียกว่านัลทรี (Null Tree) และถ้ามี
โหนดหนึ่งเป็นโหนดราก ส่วนที่เหลือจะแบ่งเป็นทรีย่อย
(Sub Tree) T1, T2, T3,…,Tk
โดยที่ k>=0 และทรีย่อยต้องมีคุณสมบัติเป็นทรี
นิยามที่เกี่ยวข้องกับทรี
1. ฟอร์เรสต์ (Forest)หมายถึง กลุ่มของทรีที่เกิดจากการเอาโหนดราก
ของทรีออกหรือ เซตของทรีที่แยกจากกัน(Disjoint Trees)
2. ทรีที่มีแบบแผน (Ordered Tree)หมายถึง ทรีที่โหนดต่าง ๆ
ในทรีนั้นมีความสัมพันธ์ที่แน่นอน เช่น ไปทางขวาไปทางซ้าย เป็นต้น
3. ทรีคล้าย (Similar Tree) คือทรีที่มีโครงสร้างเหมือนกัน หรือทรีที่มี
รูปร่างของทรีเหมือนกัน โดยไม่คำนึงถึงข้อมูลที่อยู่ในแต่ละโหนด
4. ทรีเหมือน (Equivalent Tree) คือทรีที่เหมือนกันโดยสมบูรณ์
โดยต้องเป็นทรีที่ คล้ายกันและแต่ละโหนดในตำแหน่งเดียวกันมี
ข้อมูลเหมือนกัน
5. กำลัง (Degree) หมายถึงจำนวนทรีย่อยของโหนด นั้น ๆ
-การแทนทรีด้วย โหนดขนาดเท่ากันค่อนข้างใช้เนื้อที่จำนวนมาก
เนื่องจากแต่ละโหนดมีจำนวนโหนดลูกไม่เท่ากันหรือบาง
โหนดไม่มีโหนดลูกเลยถ้าเป็นทรีที่แต่ละโหนดมีจำนวนโหนดลูกที่แตกต่าง
กันมากจะเป็นการสิ้นเปลืองเนื้อที่ในหน่วยความจำโดยเปล่าประโยชน์
-โครงสร้างทรีที่แต่ละโหนดมีลิงค์ฟิลด์แค่สองลิงค์ฟิลด์ ซึ่งช่วยให้ประหยัด
เนื้อที่ ในการจัดเก็บได้มาก เรียกโครงสร้างทรีที่แต่ละโหนดมีจำนวนโหนดลูก
ไม่เกินสอง หรือแต่ละโหนดมีจำนวนทรีย่อยไม่เกินสองนี้ว่า ไบนารีทรี
(Binary Tree) มีวิธีการท่องเข้าไปในทรี 6 วิธี
คือ NLR LNR LRN NRL RNL และ RLN
แต่วิธีการท่องเข้าไปไบนารีทรีที่นิยมใช้กันมากเป็นการท่องจากซ้ายไปขวา
3 แบบแรกเท่านั้นคือ NLR LNR และ LRN ซึ่งลักษณะการเป็นนิยามแบบ
รีเคอร์ซีฟ(Recursive) ซึ่งขั้นตอนการท่องไปในแต่ละแบบมีดังนี้
1. การท่องไปแบบพรีออร์เดอร์(Preorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ
ในทรีด้วยวิธีNLR มีขั้นตอนการเดินดังต่อไปนี้
(1) เยือนโหนดราก
(2) ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
(3) ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์
2.การท่องไปแบบอินออร์เดอร์(Inorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่าง
ๆในทรีด้วยวิธี LNRมีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
(2) เยือนโหนดราก
(3) ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์
3. การท่องไปแบบโพสออร์เดอร์(Postorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ
ในทรีด้วยวิธี LRN มีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบโพสต์ออร์เดอร์
(2) ท่องไปในทรีย่อยทางขวาแบบโพสต์ออร์เดอร์
(3) เยือนโหนดราก
DTS:08-28-08-2552
ไม่มีความคิดเห็น:
แสดงความคิดเห็น