การแสดงไบนารีทรีในโครงสร้างข้อมูล

ที่นี่เราจะมาดูวิธีการแสดงต้นไม้ไบนารีในหน่วยความจำของคอมพิวเตอร์ มีสองวิธีที่แตกต่างกันสำหรับการแสดง กำลังใช้อาร์เรย์และใช้รายการที่เชื่อมโยง

สมมติว่าเรามีต้นไม้ต้นหนึ่งแบบนี้ -

การแสดงอาร์เรย์จัดเก็บข้อมูลทรีโดยการสแกนองค์ประกอบโดยใช้ลำดับระดับ ดังนั้นมันจึงเก็บโหนดไว้ทีละระดับ หากองค์ประกอบบางอย่างหายไป จะเว้นช่องว่างไว้ การเป็นตัวแทนของต้นไม้ด้านบนเป็นเหมือนด้านล่าง −

ดัชนี 1 ถือราก มีลูกสองคน 5 และ 16 พวกเขาถูกวางไว้ที่ตำแหน่ง 2 และ 3 เด็กบางคนหายไป ดังนั้นที่ของพวกเขาจึงเว้นว่างไว้

ในการเป็นตัวแทนนี้ เราสามารถรับตำแหน่งของลูกสองคนของโหนดเดียวได้อย่างง่ายดายโดยใช้สูตรนี้ -

$$child_{1}=2*ผู้ปกครอง$$

$$child_{2}=\lgroup2*parent\rgroup+1$$

ในการรับดัชนีหลักจากลูก เราต้องทำตามสูตรนี้ -

$$parent=\begin{bmatrix}\frac{child}{2} \end{bmatrix}$$

วิธีนี้เป็นวิธีที่ดี และเราสามารถค้นหาดัชนีของ parent และ child ได้อย่างง่ายดาย แต่หน่วยความจำไม่มีประสิทธิภาพ มันจะใช้พื้นที่จำนวนมากที่ไม่มีประโยชน์ การนำเสนอนี้เหมาะสำหรับไบนารีทรีแบบสมบูรณ์หรือแบบไบนารีแบบเต็ม

อีกวิธีหนึ่งคือการใช้รายการที่เชื่อมโยง เราสร้างโหนดสำหรับแต่ละองค์ประกอบ ซึ่งจะมีลักษณะดังนี้ -