ความแตกต่างระหว่างต้นไม้ไบนารีสมบูรณ์และต้นไม้ไบนารีเต็ม

ต้นไม้ไบนารีทั้งหมดหรือต้นไม้เต็มรูปแบบไบนารี

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

Full Binary Tree คืออะไร?

ต้นไม้ไบนารีเต็มเป็นต้นไม้ไบนารีซึ่งทุกโหนดในต้นไม้มีลูกศรเท่ากับศูนย์หรือสองลูก กล่าวอีกนัยหนึ่งทุกโหนดในต้นไม้ยกเว้นใบมีลูกสองตัว รูปที่ 1 ด้านล่างแสดงโครงสร้างไบนารีเต็มรูปแบบ ในจำนวนไบต์เต็มจำนวนโหนด (n) จำนวน laves (l) และจำนวนโหนดภายใน (i) มีความสัมพันธ์กันในลักษณะพิเศษเช่นว่าถ้าคุณรู้จักคนใดคนหนึ่ง ค่าดังต่อไปนี้:

1 ถ้าต้นไม้ไบนารีเต็มมีโหนดภายใน:

- จำนวนใบ l = i + 1

- จำนวนโหนด n = 2 * i + 1

2. ถ้ามีต้นไม้ไบนารีเต็มมี n โหนด:

- จำนวนโหนดภายใน i = (n-1) / 2

- จำนวนใบ l = (n + 1) / 2

3. ถ้ามีต้นไม้ไบนารีเต็มใบ l:

- จำนวนโหนดทั้งหมด n = 2 * l-1

- จำนวนโหนดภายใน i = l-1

อะไรคือ Complete Binary Tree?

ดังแสดงในรูปที่ 2 ต้นไม้ไบนารีที่สมบูรณ์เป็นต้นไม้ไบนารีที่ทุกระดับของต้นไม้เต็มไปหมดยกเว้นระดับสุดท้าย นอกจากนี้ในระดับล่าสุดโหนดควรจะแนบมาจากด้านซ้ายสุด ต้นไม้ไบนารีที่สมบูรณ์ของความสูง h ตอบสนองต่อเงื่อนไขต่อไปนี้:

- จากโหนดรากระดับเหนือระดับสุดท้ายหมายถึงต้นไม้ไบนารีเต็มรูปแบบของความสูง h-1

- โหนดหนึ่งหรือหลายโหนดในระดับล่าสุดอาจมี 0 หรือ 1 เด็ก

- ถ้า a, b เป็นสองโหนดในระดับเหนือระดับสุดท้ายแล้ว a มีเด็กมากกว่า b ถ้าหาก a อยู่ทางซ้ายของ b

อะไรคือความแตกต่างระหว่าง Binary Tree และไบนารีเต็ม?

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