هل من المنطقي تنفيذ التكرار للحاويات التي لا تحتوي على نهاية واضحة - مثل الأشجار؟

Question

أنا أكتب قالب شجرة البحث الثنائي لسببين - تعلم C ++ وتعلم الخوارزميات الأكثر شيوعًا وهياكل البيانات.
لذلك ، هنا هو السؤال - طالما أرغب في تنفيذ المتكررين ، يبدو لي أنه لا يوجد تعريف صارم لمكان تنتهي الشجرة. ما هي اقتراحاتك؟ كيف أقوم بهذا العمل؟

Answer 1

بالنسبة للأشجار ، هناك معايير لاجتياز الشجرة ، أي تعداد العقد: اجتياز مسبق ، اجتياز inorder ، والتمرير postorder. بدلاً من وصف كل هذه هنا ، سأعيد توجيهك إلى http://en.wikipedia.org/wiki/tree_traversal. يتم تطبيق المفاهيم في الغالب على الأشجار الثنائية ، ولكن يمكنك تمديد الفكرة إلى الأشجار التعسفية عن طريق إضافة المزيد من الحالات: بشكل فعال ، معالجة عقدة ثم إعادة التكرار ، ثم تعامل مع عقدة ، والتعامل مع جميع الأطفال ثم يتكرر في كل ... إلخ. لا يوجد تصنيف قانوني لهذا النهج الذي أدركه.

Answer 2

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

ما يجب عليك فعله حقًا عند كتابة مؤلف لمجموعة مثل الشجرة هو معالجة المخاوف التالية:

1. أين يبدأ تكرار المجموعة (الجذر؟ الأوراق؟)
2. كيف يتقدم التكرار إلى العنصر التالي (Infix؟ postfix؟ لاحقة؟ اتساع؟)
3. متى ينتهي التكرار (يترك؟ الجذر؟ العقدة النهائية؟)

أيا كان ما تختاره ، يجب أن تكون واضحًا جدًا في كيفية تسمية (وتوثيق) Iterator لجعله واضحًا كيف ستزور العقد وينبعث منها.

قد تحتاج إلى كتابة العديد من التكرار لأنواع مختلفة من traverals التي تنوي دعمها. هناك بعض المقالات الجيدة هنا نماذج اجتياز الأشجار.

Answer 3

إذا كانت "صارمة" تعني: تعريف واحد شامل ، فأنت على حق ، ليس هناك واحد.

لكن "نهاية" للأشجار محددة جيدًا ، على الرغم من أنها تعتمد على طريقة اجتيازك التي تختارها.

• إذا قمت بعمل اجتياز (أو متماثل) end.
• في Preorder (أو العمق أولاً) ، سيكون أقصى اليمين هو end, ، إلخ.
• في Postorder ، سيكون عنصر الجذر end, ، إلخ.

الاكثر انتشارا اجتياز الأشجار طُرق.

Answer 4

تعريفك للتكرار خاطئ قليلاً. لا ينتقل التكرار بداية إلى إنهاء, ، ولا أمامي إلى الى الخلف. بدلا من ذلك يذهبون بجانب جميع أعضاء هذا الهيكل.

إذا طلبت التكرار على هيكل مرتبة ، أي صفيف وقائمة مرتبطة وما إلى ذلك ، فسوف (عادة) ستعيد أعضائك في الطلب.

بالنسبة للعناصر غير المرتبة ، على سبيل المثال ، ستحصل عليها والتي تريدها على أي وقت مضى أن تطلب مجموعة المجموعة أن تقدم لك ، لكنك ستحصل عليها جميعًا ومرحلة واحدة ، تمامًا كما تريد مع صفيف -تراتور.

أما بالنسبة للأشجار ، فقد ذكر الآخرين بالفعل: لديهم مفاهيم محددة جيدًا من الترتيب الكلي ، عليك فقط اختيار واحد :)

Answer 5

يعتمد ذلك على ما تريد القيام به مع الشجرة-ربما يكون من الجيد أن يكون لديك ، على سبيل المثال ، متكررًا في البحث الأول أو البحث عن العمق (أو كليهما).

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

Answer 6

يبدو الأمر معقولا خاصة في حالات كهذه ، نظرًا لأن مستخدمي الفصل الخاص بك وسيلة للسير بسهولة على جميع العناصر بطرق مختلفة كما يتطلب الموقف. بدونهم ، يحتاج المستخدمون إلى كتابة طرق معقدة ، وعادة ما تكون عودية بأنفسهم. بالمقارنة مع المتجهات على سبيل المثال ، حيث يكون التكرار أكثر من استخدام (i = 0 ؛ i

Answer 7

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