شجرة ثنائية كاملة مقابل شجرة ثنائية كاملة
الشجرة الثنائية عبارة عن شجرة تحتوي كل عقدة على طفل أو طفلين. في الشجرة الثنائية ، لا يمكن أن تحتوي العقدة على أكثر من فرعين. في الشجرة الثنائية ، يتم تسمية الأطفال كأطفال "يسار" و "يمين". تحتوي العقد الفرعية على مرجع إلى أصلها. الشجرة الثنائية الكاملة هي شجرة ثنائية يتم فيها ملء كل مستوى من مستويات الشجرة الثنائية بالكامل باستثناء المستوى الأخير. في المستوى الشاغر ، يتم إرفاق العقد بدءًا من أقصى موضع لليسار. الشجرة الثنائية الكاملة هي شجرة يكون فيها لكل عقدة في الشجرة طفلان باستثناء أوراق الشجرة.
ما هي الشجرة الثنائية الكاملة؟
الشجرة الثنائية الكاملة عبارة عن شجرة ثنائية تحتوي فيها كل عقدة في الشجرة على صفر أو طفلين بالضبط. بمعنى آخر ، كل عقدة في الشجرة باستثناء الأوراق لها طفلان بالضبط. الشكل 1 أدناه يصور شجرة ثنائية كاملة. في الشجرة الثنائية الكاملة ، يرتبط عدد العقد (n) وعدد الحمم (l) وعدد العقد الداخلية (i) بطريقة خاصة بحيث إذا كنت تعرف أيًا منها يمكنك تحديد الاثنين الآخرين القيم على النحو التالي:
1. إذا كانت الشجرة الثنائية الكاملة تحتوي على عقد داخلية:
- عدد الأوراق l=i + 1
- العدد الإجمالي للعقد n=2i + 1
2. إذا كانت الشجرة الثنائية الكاملة تحتوي على عدد n من العقد:
- عدد العقد الداخلية i=(n-1) / 2
- عدد الأوراق l=(n + 1) / 2
3. إذا كانت الشجرة الثنائية الكاملة بها أوراق l:
- إجمالي عدد العقد n=2l-1
- عدد العقد الداخلية i=l-1
ما هي الشجرة الثنائية الكاملة؟
كما هو موضح في الشكل 2 ، الشجرة الثنائية الكاملة هي شجرة ثنائية يتم فيها ملء كل مستوى من مستويات الشجرة بالكامل باستثناء المستوى الأخير. أيضًا ، في المستوى الأخير ، يجب إرفاق العقد بدءًا من أقصى موضع لليسار. شجرة ثنائية كاملة بارتفاع h تستوفي الشروط التالية:
- من عقدة الجذر ، يمثل المستوى فوق المستوى الأخير شجرة ثنائية كاملة من الارتفاع h-1
- قد تحتوي عقدة واحدة أو أكثر في المستوى الأخير على 0 أو 1 أطفال
- إذا كانت a ، b عبارة عن عقدتين في المستوى فوق المستوى الأخير ، فعندئذٍ يكون لدى a عدد أطفال أكثر من b إذا وفقط إذا كانت a تقع على يسار b
ما هو الفرق بين الشجرة الثنائية الكاملة والشجرة الثنائية الكاملة؟
الأشجار الثنائية الكاملة والأشجار الثنائية الكاملة لها فرق واضح. في حين أن الشجرة الثنائية الكاملة عبارة عن شجرة ثنائية تحتوي كل عقدة فيها على صفر أو طفلين ، فإن الشجرة الثنائية الكاملة هي شجرة ثنائية يتم فيها ملء كل مستوى من مستويات الشجرة الثنائية بالكامل باستثناء المستوى الأخير. يجب أن تكون بعض هياكل البيانات الخاصة مثل الأكوام عبارة عن أشجار ثنائية كاملة بينما لا يلزم أن تكون أشجارًا ثنائية كاملة. في الشجرة الثنائية الكاملة ، إذا كنت تعرف العدد الإجمالي للعقد أو عدد الحمم أو عدد العقد الداخلية ، يمكنك العثور على العقدتين الأخريين بسهولة بالغة. لكن الشجرة الثنائية الكاملة لا تحتوي على خاصية خاصة تتعلق بهذه السمات الثلاث.
