สรุปผลเรียนเรื่อง ทรี (Tree)
ทรี (Tree) เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ระหว่า'
โหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับชั้น (Hierarchical Relationship)
เช่นแผนผังองค์ประกอบของหน่วยงานต่างๆ โครงสร้างสารบัญหนังสือ เป็นต้น
ความสัมพันธ์ของโหนดใน Tree
แต่ละโหนดจะมีความสัมพันธ์กับโหนดในระดับที่ต่ำลงมาหนึ่งระดับได้
หลายๆ โหนด เรียกโหนดดังกล่าวว่า โหนดแม่ (Parent or Mother Node)
โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่หนึ่งระดับ เรียกว่า โหนดลูก(Child Node)
โหนดทีอยู่ในระดับสูงสุดและไม่มีโหนดแม่ เรียกว่า โหนดราก(Root Node)
โหนดที่มีโหนดแม่เป็นโหนดเดียวกัน เรียกว่า โหนดพี่น้อง(Siblings)
โหนดที่ไม่มีโหนดลูก เรียกว่า โหนดใบ(Leave Node)
เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนด เรียกว่า กิ่ง(Branch)
นิยามของทรี(Tree)
ทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด(loop)ในโครงสร้าง โหนดสอง
โหนดใดๆ ในทรีต้องมีทางติดต่อกัน ทางเดียวเท่านั้น และทรีที่มี N โหนด
ต้องมีกิ่งทั้งหมด N-1เส้น
ทรีประกอบด้วยสมาชิกที่เรียกว่า โหนด โดยที่ว่าง ไม่มีโหนดใดๆ เรียกว่า
นัลทรี(Null Tree) และถ้ามีโหนดหนึ่งเป็นโหนดราก ส่วนที่เหลือจะแบ่ง
เป็นทรีย่อย (Sub Tree)
นิยามที่เกี่ยวกับทรี (Tree)
1.ฟอร์เรสต์ (Forest) หมายถึง กลุ่มของทรีที่เกิดจากการเอาโหนดราก
ของทรีออก หรือ เซตของทรีที่แยกออกจากกัน(Disjoint Trees)
2.ทรีที่มีแบบแผน (Ordered Tree) หมายถึง ทรีที่โหนดต่างๆในทรีนั้น
มีความสัมพันธ์ที่แน่นอน เช่น ไปทางขวา ไปทางซ้าย เป็นต้น
3.ทรีคล้าย (Similar Tree) คือ ทรีที่มีโครงสร้างเหมือนกัน หรือทรีที่มี
รูปร่างของทรีเหมือนกัน โดยไม่คำนึ่งถึงข้อมูลทีอยู่ในแต่ละโหนด
4.ทรีเหมือน (Equivalent Tree) คือ ทรีที่เหมือนกันโดยสมบูรณ์
โดยต้องเป็นทรีที่คล้ายกันและแต่ละโหนดในตำแหน่งเดียวกันมีข้อมูล เหมือนกัน
5.กำลัง (Degree) หมายถึง จำนวนทรีย่อยของในโหนดนั้นๆ
6.ระดับของโหนด (Level of Node) คือ ระยะทางในแนวดิ่งของโหนด
นั้นๆ ที่อยู่ห่างจากโหนดราก เมื่อกำหนดให้ โหนดรากของทรีนั้นอยู่
ระดับ 1และกิ่งแต่ละกิ่งมีความเท่ากันหมด คือยาวเท่ากับ 1 หน่วย
ซึ่งระดับของโหนดจะเท่ากับจำนวนกิ่งที่น้อยที่สุดจากโหนดรากไปยัง
โหนดใดบวกด้วย 1และจำนวนเส้นทางตามแนวดิ่งของโหนดใดๆ
ซึ่งห่างจากโหนดราก เรียกว่า ความสูง (Height) หรือความลึก (Depth)
การแทนที่ทรีในหน่วยความจำหลัก
การแทนที่โครงสร้างข้อมูลแบบทรีในความจำหลัก
จะมีพอยเตอร์เชื่อมโยงจากโหนดแม่ไปยังโหนดลูก
แต่ละโหนดต้องมีลิงค์ฟิลด์เพื่อเก็บที่อยู่ของโหนดลูกต่างๆ
นั่นคือจำนวน ลิงค์ฟิลด์ของแต่ละโหนดขึ้นอยู่
กับจำนวนของโหนดลูก โดยอาจใช้วิธีการต่อไปนี้
1.โหนดแต่ละโหนดเก็บพอยเตอร์ชี้ไปยังโหนดลูกทุกโหนด
การแทนที่ ด้วยวิธีนี้จะทำให้จำนวนฟิลด์ในแต่ละโหนดเท่ากัน
โดยกำหนดให้มีขนาดเท่ากับจำนวนโหนดลูกของโหนดที่มีลูกมากที่สุด
โหนดใดไม่มี ลูกโหนดลูกก็ให้ค่าในพอยเตอร์ในลิงค์ฟิลด์เป็น Null
2.แทนที่ด้วยไบนารีทรี เป็นวิธีแก้ปัญหาเพื่อลดการสิ้นเปลืองเนื้อที่
หน่วยความจำก็คือกำหนดลิงค์ฟิลด์ให้มีจำนวนน้อยที่สุดเท่าที่จำเป็น
เท่านั้นโดยกำหนดให้แต่ละโหนดมีจำนวนลิงค์ฟิลด์สองลิงค์ฟิลด์
-ลิงค์แรกเก็บที่อยู่ของโหนดลูกคนโต
-ลิงค์ฟิลด์ที่สองเก็บที่อยู่ของโหนดพี่น้องที่เป็นโหนดถัดไป
โหนดใดไม่มีโหนดลูกหรือไม่มีพี่น้องให้ค่าพอยน์เตอร์ในลิงค์ฟิลด์
มีค่าเป็นNull
สรุป ไบนารีทรีก็คือ โครงสร้างทรีที่แต่ละโหนดมีจำนวนโหนดลูก
ไม่เกินสองหรือแต่ละโหนดมีจำนวนทรีย่อยไม่เกินสอง
ไบนารีทรีที่สมบูรณ์ ไบนารีทรีที่ทุกๆโหนดมีทรีย่อยทางซ้าย
และทรีย่อยขวา ยกเว้นโหนดใบ และโหนดใบทุกโหนดจะต้อง
อยู่ที่ระดับเดียวกันสามารถคำนวณจำนวนโหนดทั้งหมดในไบนารีทรี
แบบสมบูรณ์ได้ ถ้ากำหนดให้ L คือระดับของโหนดใดๆ และ
N คือจำนวนโหนดทั้งหมด ทั้งหมดในทรีจะได้ว่า
ระดับ 1 มีจำนวนโหนด 1 โหนด
ระดับ 2 มีจำนวนโหนด 3 โหนด
ระดัย 3 มีจำนวนโหนด 7 โหนด
การแปลงทรีทั่วไปให้เป็นไบนารีทรี
1.ให้โหนดแม่ชี้ไปยังโหนดลูกคนโตแล้วลบความสัมพนธ์ ระหว่างโหนด
แม่และโหนดลูกอื่นๆ
2.ให้เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง
3.จับให้ทรีย่อยทางขวาเอียงลงมา 45 องศา
การท่องไปในไบนารีทรี
1.การท่องไปแบบพีออร์เดอร์(Preorder Traversal)
เป็นการเดินเข้าไปเยือนโหนดต่างๆใสทรีด้วยวิธี NLR มีขั้นตอนการเดิน
ดังต่อไปนี้
1.1เยื่อนโหนดราก
1.2ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
1.3ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์
2.การท่องไปอบบอินออร์เดอร์(Inorder Traversal) เป็นการเดินเข้าไปเยือนโหนดต่างๆ
ในทรีด้วยวิธี LNR มีขั้นตอนการเดินดังต่อไปนี้
2.1ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
2.2เยื่อนโหนดราก
2.3ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์
3.การท่องโพสออร์เดอร์(Postorder Traversal) เป็นการเดินเข้าไปเยื่อนโหนดต่างๆ
ในทรีด้วยวิธี LRN มีขั้นตอนการเดินดังต่อไปนี้
3.1ท่องไปในทรีย่อยทางซ้ายแบบโพสต์ออร์เดอร์
3.2ท่องไปในทรีย่อยทางขวาแบบโพสต์ออร์เดอร์
3.3เยือนโหนดราก
