حساب العمق ونسل الشجرة

Question

هل يمكنك أن تساعدني يا رفاق في الخوارزمية للقيام بهذه الأشياء؟ لديّ طلب مسبق ، و inorder ، و postorder ، وقد أعطيت التلميح لاجتياز الشجرة مع أحد هذه الطلبات. أنا أستخدم Dotty لتسمية (أو "زيارة") العقد.

العمق هو عدد الحواف من الجذر إلى الورقة السفلية ، لذلك في كل مرة أتحرك فيها ، أضيف +1 إلى العمق؟ شئ مثل هذا؟

لا فكرة عن الخوارزمية لأحفاد. إنهم يسألون عن عدد العقد التي تحتوي عليها عقدة معينة تحت حد ذاتها.

هذه أشجار طبيعية راجع للشغل.

Answer 1

depth(tree) = 1+ max(depth(tree.left), depth(tree.right));

descendants(tree) = descendants(tree.left) + descendants(tree.right);

لأي منهما ، فإن العودة 0 لمؤشر فارغ من شأنه أن ينهي العودة.

Answer 2

هل هذا سؤال للواجب المنزلي؟ إجابتي تفترض أنها هي الواجب المنزلي.

الأشجار هي بنية بيانات متكررة ، وبالتالي فإن الخوارزميات التي تعمل عليها غالبًا ما تكون متكررة. تحتاج الخوارزميات العودية إلى حالة قاعدة وحالة استقرائية. بالنسبة للأشجار ، ستكون الحالة الأساسية هي ما تفعله عندما تزور عقدة الورقة (أي عقدة بدون أطفال). ستكون الحالة الاستقرائية هي ما تفعله عندما تزور عقدة داخلية (أي عقدة مع طفل واحد على الأقل).

لحساب العمق (أو "ارتفاع" الشجرة):

• الحالة الأساسية: ما هو عمق العقدة بدون أطفال؟
• الحالة الاستقرائية: بالنظر إلى أن لديك أعماق جميع أطفالك (والتي يمكن أن تكون مختلفة) ، ما هو عمق العقدة الحالية التي تزورها؟

لحساب عدد النسل:

• الحالة الأساسية: كم عدد أحفاد العقدة بدون أطفال؟
• الحالة الاستقرائية: بالنظر إلى أنك تعرف عدد أحفاد جميع أطفالك ، ما هو عدد أحفاد العقدة الحالية التي تزورها؟

أشجعك على طرح أسئلة توضيح.