tree

tree

1. โครงสร้างข้อมูลแบบ ต้นไม้คืออะไร 

คือโครงส้างที่มีรนูปแบบลักษณะคล้ายต้าไม่คั้วมหัวลง

โหนด (Node) ที่ใช้สำหรับบรรจุข้อมูโดยจะมีกิ่งซึ่งเป็นเส้นที่โย่งโหนดเข้าด้วยกันที่เรียก ว่าบรานช์ (Branch) จำนวนของบรานช์ที่สัมพันธ์กับโหนดเรี่ยกว่า ดีกรี(Degree) และถ้าหากทรีนั้นเป็นทรีที่ไม่ใช่ทรีว่างโหนดแรกจะเรียก ว่ารูท(Root) โดยโหนดทุกๆ โหนดยกเว้น รูทโหนดจะมีเพียง 1 Predecessor ในขณะที่ Successor อาจเป็น 0 หรือ 1 หรือมากกว่า 1 ก็ได้สำหรับ Leaf ก็คือโหนดใบที่ไม่มีบรานช ์ เชื่อมโยงไปยังโหนดตัวถัดไปหรือโหนดที่ไม่มีตัวตามหลังหรือ Successor นั้นเองในขณะที่โหนดพ่อ (Parent) จะมีโหนดตามหลัง หรือมี โหนดลูก(Child) ต่อท้าย โหนดลูกตั้งแต่สองโหนดหรือ มากกว่าที่มาจากพ่อเดียวกันจะเรียกว่าโหนดพี่น้อง(Siblings) 

สิ่งที่ควลรู้เกียวกับทรี

•  Subtree หมายถึง โครงสร้างที่เชื่อมต่อกันภายใต ้Root โดย Node แรกของ Subtree จะเป็น Root ของ Subtree นั้นและใช ้ เป็นชื่อเรียก Subtree  Subtree สามารถแบ่งย่อยเป็น Subtree ได้อีกจนกว่าจะ Empty

• ไบนารี่ทรี หมายถึง ทรีที่มีโหนดลูกไม่เกินสองโหนด ประกอบด้วยโหนดลูกทางซ้าย (Left child) และโหนดลูกทางขวา (Right child) โหนดลูกอาจเป็นทรีย่อยก็ได้ ซึ่งแบ่งออกเป็นทรี ย่อยทางซ้ายและทรีย่อยทางขวา และโหนดลูกแต่ละโหนดอาจมี โหนดลูกเพียงด้านซ้ายหรือด้านขวาด้านเดียวก็ได้ ส าหรับโหนด ของทรีที่มีจ านวนเป็น 0 เรียกว่า ทรีว่าง (Empty Tree)

                                               

• ความสมดุลของไบนารีทรีจะสามารถทราบได้จากค่า Balance Factor เท่ากับ 0 ซึ่งค่าดังกล่าวค านวณได้จากการน าความสูงของซับทรีด้านซ้าย (HL ) มาหักลบกับความสูงของซับทรีด้านขวา (HR )  

    

               ต้นไม้ไบนารีแบบสมบูรณ์ที่มีโหนดใบอยู่ที่ระดับ n จะมีโหนดทั้งหมด เท่ากับ 2 n -1 

• ทรีที่ไม่ใช่ไบนารี่ทรี หรื ordinary tree ทรีที่มีโหนดลูกตั้งแต่สองโหนดขื่นไป หรือมี บรานช์ ที่มีการวนลูปขื้นลง 
  

ต้นไม้แบบออดินารี(ordinary) คือต้นไม้ที่มีดีกรีสูงสุดของแต่ละโหนดเป็นเท่าไรก็ได้ซื่งการเปลี่ยนให้เป็น binary tree เป็นการจัดให้แต่ละโหนดมีดีกรีสูงสุดเท่ากับสองมีขั้นตอนดั่งนี้ 1. พิจารณาทีกิ่งทางซ้ายสุดที่อยู่ใต้พ่อเดียวกัน 2. ต่อกิ่งของโหนดทางซ้ายยสุดในขั้นที่ 1 ไปทางขวาตามลำดับอาวุโสกับพี่น้องที่เกิดดจากพ่อเดียวกัน 3. ทำขั้นที 1และ2จนครบทุกโหนด 4. ปรับมุมของแต่ละกิ่ง ประมาณ 45องศา 

• Tree Traversal หมายถึงการไปยังโหนดเพื่อประมวลผลบางอย่างที่ ต้องการกระท ากับโหนดนั้น เช่น หาข่าวสาร แบ่งออกเป็น 3 วิธี (ที่นิยมใช้) 

                                                    1. Pre-Order Traversal (N. TL. TR )

                                                    2. In-Order Traversal (TL. N.TR ) 

                                                    3. Post-Order Traversal (TL. TR. N) 

ตัวอย่าง