สรุปการเรียนLecture 6 เรื่องTree

Tree เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ระหว่างโหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับชั้นแต่ละโหนดจะมีความสัมพันธ์กับโหนดในระดับที่ต่ำลงมาหนึ่งระดับได้หลายๆโหนดเรียกโหนดดังกล่าวว่า โหนดแม่ โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่หนึ่งระดับเรียกว่า โหนดลูก โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่เรียกว่าโหนดราก
-โหนดที่มีโหนดแม่เป็นโหนดเดียวกัน เรียกว่าโหนดพี่น้อง
-โหนดทีไม่มีโหนดลูกจะเรียกว่าโหนดใบ
-เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนดเรียกว่า กิ่ง
นิยามที่เกี่ยวข้องกับทรี
1. ฟอร์เรสต์ (Forest)หมายถึง กลุ่มของทรีที่เกิดจากการเอาโหนดรากของทรีออกหรือ เซตของทรีที่แยกจากกัน(Disjoint Trees)
2. ทรีที่มีแบบแผน (Ordered Tree)หมายถึง ทรีที่โหนดต่าง ๆในทรีนั้นมีความสัมพันธ์ที่แน่นอน เช่น ไปทางขวาไปทางซ้าย
3. ทรีคล้าย (Similar Tree) คือทรีที่มีโครงสร้างเหมือนกัน หรือทรีที่มีรูปร่างของทรีเหมือนกัน โดยไม่คำนึงถึงข้อมูลที่อยู่ในแต่ละโหนด
4. ทรีเหมือน (Equivalent Tree) คือทรีที่เหมือนกันโดยสมบูรณ์โดยต้องเป็นทรีที่ คล้ายกันและแต่ละโหนดในตำแหน่งเดียวกันมีข้อมูลเหมือนกัน
5. กำลัง (Degree) หมายถึงจำนวนทรีย่อยของโหนด นั้น ๆ
-โหนดที่ถูกเยือนอาจเป็นโหนดแม่ แทนด้วย N
-ทรีย่อยทางซ้าย แทนด้วย L
-ทรีย่อยทางขวา แทนด้วย R มีวิธีการท่องดังนี้
1. การท่องไปแบบพรีออร์เดอร์ เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี NLR หรือกลาง ซ้าย ขวา มีขั้นตอนการเดินดังนี้
1.1 เยือนโหนดราก
1.2 ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
1.3 ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์
2 การท่องไปแบบอินออร์เดอร์ เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี LNR หรือ ซ้าย กลาง ขวา มีขั้นตอนดังนี้
2.1 ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
2.2 เยือนโหนดราก
2.3 ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์
3. การท่องไปแบบโพสออร์เดอร์ เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี LRN หรือซ้าย ขวา กลาง มีขั้นตอนดังนี้
3.1 ท่องไปในทรีย่อยทางซ้ายแบบโพสออร์เดอร์
3.2 ท่องไปในทรีย่อยทางขวาแบบโพสออร์เดอร์
3.3 เยือนโหนดราก
-เอ็กซ์เพรสชันทรี (Expression Tree)
เป็นการนำเอาโครงสร้างของทรีไปใช้เก็บนิพจน์ทางคณิตศาสตร์โดยเป็นไบนารีทรี
-ได้รู้การแทนนิพจน์ในExpression Tree ตัวถูกดำเนินการจะอยู่ที่โหนดใบ ส่วนตัวดำเนินการจะเก็บที่โหนดกิ่งหรือโหนดที่ไม่ใช่โหนดใบ
-ได้ทราบว่าไบนารีเซิร์ชทรี(Binary Search Tree) ค่าของโหนดรากมีค่ามากกว่าค่าของทุกโหนดในทรีย่อยทางซ้าย และมีค่าน้อยกว่าหรือเท่ากับค่าของทุกโหนดในทรีย่อยทางขวา

DTS08-26-08-09