الفرق بين شجرة ثنائية كاملة وشجرة ثنائية كاملة

شجرة ثنائية كاملة مقابل شجرة ثنائية كاملة

شجرة ثنائية هي شجرة حيث يكون لكل عقدة طفل واحد أو طفلان. في شجرة ثنائية، عقدة لا يمكن أن يكون أكثر من طفلين. في شجرة ثنائية، يطلق على الأطفال اسم "اليسار" و "الحق" الأطفال. تحتوي العقد الفرعية على إشارة إلى والديهم. شجرة ثنائية كاملة هي شجرة ثنائية في كل مستوى من الشجرة الثنائية مليئة تماما باستثناء المستوى الأخير. في مستوى غير ملئ، يتم إرفاق العقد بدءا من اليسار معظم موقف. شجرة ثنائية كاملة هي شجرة فيها كل عقدة في شجرة لديها طفلان باستثناء أوراق الشجرة.

ما هي شجرة ثنائي كامل؟

شجرة ثنائية كاملة هي شجرة ثنائية فيها كل عقدة في شجرة لديها بالضبط الصفر أو طفلين. وبعبارة أخرى، كل عقدة في شجرة باستثناء الأوراق لديها طفلين بالضبط. الشكل 1 أدناه يصور شجرة ثنائية كاملة. في شجرة ثنائية كاملة، يرتبط عدد العقد (n) وعدد من اللافتات (l) وعدد العقد الداخلية (i) بطريقة خاصة بحيث إذا كنت تعرف أي واحد منهم يمكنك تحديد اثنين آخرين القيم على النحو التالي:

1. إذا كان للشجرة الثنائية كاملة العقد الداخلية:

- عدد الأوراق l = i + 1

- إجمالي عدد العقد n = 2 * i + 1

2. إذا كانت شجرة ثنائية كاملة لها ن العقد:

- عدد العقد الداخلية i = (n-1) / 2

- عدد الأوراق l = (n + 1) / 2

3. إذا تركت شجرة ثنائية كاملة لتر:

- إجمالي عدد العقد n = 2 * l-1

- عدد العقد الداخلية i = l-1

ما هي شجرة الثنائي الكاملة؟

كما هو مبين في الشكل 2، شجرة ثنائية كاملة هي شجرة ثنائية يتم فيها ملء كل مستوى من الشجرة بالكامل باستثناء المستوى الأخير. أيضا، في المستوى الأخير، يجب أن تعلق العقد بدءا من اليسار معظم موقف. إن الشجرة الثنائية الكاملة للارتفاع h تستوفي الشروط التالية:

- من العقدة الجذرية، يمثل المستوى فوق المستوى الأخير شجرة ثنائية كاملة الارتفاع h-1

- قد يكون لعقد واحد أو أكثر في المستوى الأخير 0 أو طفل واحد

- إذا كانت a، b عقدتان في المستوى فوق المستوى الأخير، عندها عدد أكبر من الأطفال من b إذا وفقط إذا كان هناك يسار ب

ما هو الفرق بين شجرة ثنائية كاملة والشجرة الثنائية الكاملة؟

الأشجار الثنائية الكاملة والأشجار الثنائية الكاملة لها فرق واضح. في حين أن شجرة ثنائية كاملة هي شجرة ثنائية فيها كل عقدة لديها صفر أو طفلين، وشجرة ثنائية كاملة هي شجرة الثنائية التي يتم فيها ملء كل مستوى من شجرة ثنائية تماما باستثناء المستوى الأخير. بعض هياكل البيانات الخاصة مثل أكوام تحتاج إلى أن تكون أشجار ثنائية كاملة في حين أنها لا تحتاج إلى أن تكون الأشجار الثنائية الكاملة. في شجرة ثنائية كاملة، إذا كنت تعرف عدد العقد الإجمالية أو عدد من الحزم أو عدد من العقد الداخلية، يمكنك العثور على اثنين آخرين بسهولة جدا.ولكن شجرة ثنائية كاملة ليس لديها خاصية خاصة تتعلق أطروحات ثلاث سمات.