สรุป ทรี
โครงสร้างข้อมูลแบบทรี เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ ระหว่างโหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับชั้น ได้มีการนำรูปแบบทรีไปประยุกต์ใช้งานต่างๆอย่างแพร่หลาย
ทรี หรือโครงสร้างข้อมูลแบบต้นไม้ ประกอบด้วยโหนด (node) ซึ่งเป็นส่วนที่เก็บข้อมูล ในทรีหนึ่งทรีจะประกอบไปด้วยรูทโหนด (root node) เพียงหนึ่งโหนด แล้วรูทโหนดสามารถแตกโหนดออกเป็นโหนดย่อยๆ ได้อีกหลายโหนดเรียกว่าโหนดลูก (Child node) เมื่อมีโหนดลูกแล้ว โหนดลูกก็ยังสามารถแสดงเป็นโหนด
พ่อแม่ (Parent Node) โดยการแตกโหนดออกเป็นโหนดย่อยๆได้อีก
Binary TreeBinary Tree
มีลักษณะเหมือนกับ Tree ปกติแต่มีคุณสมบัติพิเศษ คือ “แต่ละโหนดจะมีโหนดลูกได้ไม่เกิน 2 โหนด” หรือพูดอีกนัยหนึ่งก็คือ แต่ละโหนดใน binary tree จะมีดีกรีได้ไม่เกิน2
การแปลงทรีทั่วไปให้เป็นไบนารีทรี
ขั้นตอนการแปลงทรีทั่วๆไป1.ให้โหนดแม่ชี้ไปยังโหนดลูกคนโต แล้วลบความสัมพันธ์ระหว่างโหนดแม่และดหนดลูกอื่นๆ2.ให้เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง3.จับให้ทรีย่อยทางขวาเอียงลงมา 45 องศา
การท่องไปในทรีเพื่อเข้าไปเยือนทุกๆโหนดในทรี ซึ่งวิธีการท่องเข้าไปต้องเป็นไปอย่างมีระบบแผน สามารถเยือนโหนดทุกๆโหนดๆละนึ่งครั้ง
1.การท่องไปแบบพรีออร์เดอร์ การเดินเข้าไปเยือนโหนดต่างๆในทรีด้วยวิธี NLR
1. เยือนดหนดราก
2. ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
3. ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์
2.การท่องไปแบบอินออร์เดอร์ เป็นการเดินไปเยือนโหนดต่างๆในทรีด้วยวิธี LNR
1.ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
2.เยือนโหนดราก
3.ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์
3.การท่องไปแบบโพสออร์เดอร์ เป็นการเดินไปเยือนโหนดต่างๆ ในทรีด้วยวิธี LRN
1.ท่องไปในทรีย่อยซ้ายแบบโพสออร์เดอร์
2.ท่องไปในทรีย่อยขวาแบบโพสออร์เดอร์
3.เยือนโหนดราก
ไม่มีความคิดเห็น:
แสดงความคิดเห็น