ما هو الفرق بين عمق الشجرة والارتفاع؟

Question

هذا سؤال بسيط من نظرية الخوارزميات.
الفرق بينهما هو أنه في إحدى الحالات ، تحسب عدد العقد وعدد آخر من الحواف على أقصر مسار بين الجذر والعقدة الخرسانية.
أيها؟

Answer 1

علمت أن العمق والارتفاع هما خصائص أ العقدة:

• ال عمق من العقدة هو عدد الحواف من العقدة إلى عقدة جذر الشجرة.
  سيكون لعقدة الجذر عمق 0.

• ال ارتفاع من العقدة هو عدد الحواف على أطول مسار من العقدة إلى ورقة.
  سيكون لها عقدة ورقة ارتفاع 0.

خصائص أ شجرة:

• ال ارتفاع من الشجرة سيكون ارتفاع عقدة الجذر ،
  أو ما يعادل ، عمق أعمق عقدة.

• ال قطر الدائرة (أو العرض) من الشجرة هو عدد العقد على أطول مسار بين أي اثنين من العقد ورقة. الشجرة أدناه لها قطر من 6 عقد.

Answer 2

ارتفاع وعمق الشجرة متساوية ...

لكن الارتفاع وعمق العقدة ليسا متساوين لأن ...

يتم حساب الارتفاع عن طريق اجتياز العقدة المحددة إلى أعمق ورقة ممكنة.

يتم حساب العمق من اجتياز الجذر إلى العقدة المعطاة .....

Answer 3

وفقا لكورمين وآخرون. مقدمة إلى الخوارزميات (التذييل B.5.3) ، يتم تعريف عمق العقدة X في شجرة T على أنه طول المسار البسيط (عدد الحواف) من عقدة الجذر من T إلى X. ارتفاع العقدة Y عدد الحواف على أطول مسار بسيط لأسفل من y إلى ورقة. يتم تعريف ارتفاع الشجرة على أنها ارتفاع عقدة الجذر.

لاحظ أن المسار البسيط هو مسار بدون رؤوس تكرار.

ارتفاع أ شجرة يساوي عمق أقصى أ شجرة. عمق العقدة وارتفاع العقدة ليسوا بالضرورة متساوين. انظر الشكل B.6 من الطبعة الثالثة من Cormen et al. للحصول على توضيح لهذه المفاهيم.

لقد رأيت أحيانًا مشاكل تطلب من المرء حساب العقد (القمم) بدلاً من الحواف ، لذا اطلب توضيحًا إذا لم تكن متأكدًا من أنك يجب أن تحسب العقد أو الحواف أثناء امتحان أو مقابلة عمل.

Answer 4

إجابة بسيطة:
عمق:
1. شجرة: عدد الحواف/القوس من عقدة الجذر إلى عقدة الورقة للشجرة تسمى عمق الشجرة.
2. العقدة: عدد الحواف/القوس من عقدة الجذر إلى تلك العقدة تسمى عمق تلك العقدة.

Answer 5

هناك طريقة أخرى لفهم هذه المفهوم هي على النحو التالي: العمق: ارسم خطًا أفقيًا في الوضع الجذر وعلاج هذا الخط على أنه أرضية. لذا فإن عمق الجذر هو 0 ، وجميع أطفاله ينمو إلى أسفل ، لذا فإن كل مستوى من العقد لديه العمق الحالي + 1.

الارتفاع: نفس الخط الأفقي ولكن هذه المرة يكون الموضع الأرضي عقدًا خارجيًا ، وهي ورقة الشجرة وعد الأعلى.

Answer 6

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

من Opendsa هياكل بيانات ومكتب الطحالب:

إذا ن₁, ، ن₂،...،ن_ك هو تسلسل العقد في الشجرة بحيث ن_أنا هو والد ن_أنا+1 لـ 1 <= i₁ إلى ن_ك. طول المسار هو K - 1. إذا كان هناك مسار من العقدة R إلى Node M ، فإن R عبارة من جميع العقد. عمق العقدة M في الشجرة هو طول المسار من جذر الشجرة إلى M. ارتفاع الشجرة هو أكثر من عمق أعمق العقدة في الشجرة. جميع العقد من العمق د هي في المستوى د في الشجرة. الجذر هو العقدة الوحيدة في المستوى 0 ، وعمقها 0.

الشكل 7.2.1: شجرة ثنائية. العقدة A هي الجذر. العقد B و C من أطفال A. العقد B و D معا تشكل شجرة فرعية. العقدة B لديها طفلان: طفلها الأيسر هو الشجرة الفارغة وطفلها الأيمن هو D. العقد A و C و E هي أسلاف G. العقد D و E و F من المستوى 2 من الشجرة ؛ العقدة A عند المستوى 0. الحواف من A إلى C إلى E إلى G تشكل مسارًا من الطول 3. العقد D ، G ، H ، وأنا أوراق. العقد A و B و C و E و F هي العقد الداخلية. عمق I هو 3. ارتفاع هذه الشجرة هو 4.