โครงสร้างข้อมูลแบบ tree

ทรี (Tree)ป็นโครงสร้างข้อมูลที่ความสัมพันธ์ ระหว่าง โหนดจะมัความสัมพันธ์ลดหลั่นกันเป็นลำดับ เช่น (Hierarchical Relationship) ได้มีการนำรูปแบบทรีไปประยุกต์ใช้ในงาน ต่าง ๆ อย่างแพร่หลาย สวนมากจะใชสำหรับแสดง ความสัมพันธ์ระหว่างข้อมูล เช่น แผนผังองค์ประกอบของหน่วยงานต่าง ๆ โครงสร้างสารบัญหนังสือ เป็นต้นแต่ละโหนดจะมีความสัมพันธ์กับ โหนดในระดับที่ต่ำลงมา หนึ่งระดับได้หลาย ๆโหนด เรียกโหนดดั้งกล่าวว่า โหนดแม่(Parent orMother Node)โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่หนึ่งระดับเรียกว่า โหนดลูก (Child or Son Node)โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่เรียกว่า โหดราก (Root Node) Data Structure โหนดที่มีโหนดแม่เป็นโหนดเดียวกัน รียกว่า โหนดพี่น้อง (Siblings)โหนดที่ไม่มีโหนดลูก เรียกว่า โหนดใบ (Leave Node)เส้นเชื่อมแสดงความสัมพันธ์ระหว่าง โหนดสองโหนดเรียกว่า กิ่ง (Branch)

นิยามของทรี1. นิยามทรีด้วยนิยามของกราฟ ทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด (loop)ในโครงสร้าง โหนดสองโหนด ใดๆในทรีต้องมีทางตัดต่อกันทางเดียวเท่านั้น และทรีที่มี N โหนด ต้องมีกิ่ง ทั้งหมด N-1 เส้น การเขียนรูปแบบทรี อาจเขียนได้ 4

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) หมายถึงจำนวนทรีย่อยของโหนด นั้น ๆ เช่นในรูปโหนด “B” มีกำลังเป็น 1 เพราะมีทรีย่อย คือ {“D”}ส่วนโหนด “C” มีค่ากำลังเป็นสองเพราะมีทรีย่อย คือ {“E”, “G”, “H”, “I”} และ {“F”}

6.ระดับของโหนด (Level of Node) คือ ระยะทางในแนวดิ่งของโหนดนั้น ๆ ที่อยู่ห่างจากโหนดราก เมื่อกำหนดให้ โหนดรากของทรีนั้นอยู่ระดับ 1 และกิ่งแต่ละกิ่งมีความเท่ากันหมด คือ ยาวเท่ากับ 1หน่วยซึ่งระดับของโหนดจะเท่ากับจำนวนกิ่งที่น้อยที่สุดจากโหนดรากไปยังโหนดใด ๆ บวกด้วย 1และจำนวนเส้นทางตามแนวดิ่งของโหนดใด ๆ ซึ่งห่างจากโหนดราก เรียกวา ความสูง (Height)หรือความ ลึก (Depth)

1.โครงสร้างข้อมูลแบบต้นไม้เป็นโครงสร้างชนิดใด

  ก. ชนิดเชิงเส้น

  ข. ชนิดไม่เชิงเส้น

  ค. ชนิดตัดสินใจเลือก

  ง. ชนิดทำงานซ้ำ

2. โหนดพิเศษโหนดหนึ่งที่อยู่บนสุดแรกเรียกว่าอะไร

  ก. Father

  ข. Subtree

  ค. Leat Node

  ง. Root Node

3. Level มีความหมายตรงกับข้อใด

  ก. รูท

  ข. ดีกรีของโหนด

  ค. โหนดที่เป็นใบ

  ง. ระดับของโหนด

4. ดีกรีของโหนดคืออะไร

  ก. รูทโหนด

  ข. จำนวนต้นไม้ 1 ต้น

  ค. ต้นไม้แบบพรีออเดอร์

  ง. จำนวนต้นไม้ย่อยของโหนดนั้น

5. ป่าไม้ในโครงสร้างข้อมูลแบบต้นไม้ หมายถึงสิ่งใด

  ก. กลุ่มของต้นไม้

  ข. ต้นไม้ย่อยซ้าย

  ค. ต้นไม้ย่อยขวา

  ง. การดูแลต้นไม้

6. โครงสร้างข้อมูลแบบต้นไม้ มีลักษณะคล้ายสิ่งใด

  ก. ใบไม้

  ข. รากของต้นไม้

  ค. ลำต้นของต้นไม้

  ง. กิ่งก้านของต้นไม้

7. ต้นไม้ธรรมชาติจะงอกจากล่างขึ้นบน ส่วนโครงสร้างข้อมูลแบบต้นไม้นั้นจะเจริญเติบโตอย่างไร

  ก.จากล่างไปบน

  ข. จากบนลงล่าง

  ค. จากซ้ายไปขวา

  ง. จากขวาไปซ้าย

8. ต้นไม้ Binary ที่แต่ละโหนดภายในจะมีโหนดย่อยซ้ายโหนดย่อยขวาและโหนดใบหมายถึงต้นไม้แบบใด

  ก. ต้นไม้ไบนารีคู่

  ข. ต้นไม้ไบนารีเดี่ยว

  ค. ต้นไม้ไบนารีแบบสมบูรณ์

  ง. ต้นไม้ไบนารีแบบไม่สมบูรณ์

9. ข้อใดไม่ใช่การแทนต้นไม้ไบนารีในหน่วยความจำ

  ก. การแทนโดยอาศัยพอยน์เตอร์

  ข การแทนโดยอาศัยแอดเดรสของโหนด

  ค. การแทนแบบวีแควนเชียล

  ง. การแทนแบบลำดับชั้น

10. LVR คือวิธีการเดินเข้าแบบใด

  ก. แบบพรีออร์เดอร์

  ข. แบบอินออร์เดอร์

  ค. แบบโพสต์ออร์เดอร์

  ง. ไม่มีข้อใดถูก