المشي شجرة الأم الأولى

Question

ما هي أفضل طريقة لزيارة جميع العقد مرتبط شجرة (كل عقد إشارات إلى الوالد و جميع الأطفال ، الجذرية العقد يكون باطلا كما الأم) ، بحيث لا عقدة زار من قبل أي من الأجداد ؟ نقاط براوني غير متكررة.

Answer 1

البرمجية الزائفة:

NodesToVisit = some stack or some list
NodesToVisit.Push(RootNode)

While NodesToVisit.Length > 0
{
   CurNode = NodesToVisit.Pop()
   For each Child C in CurNode
        NodesToVisit.Push(C)
   Visit(CurNode) (i.e. do whatever needs to be done)
}

تحرير:العودية أو لا ؟
أن تكون صحيحة من الناحية الفنية ، كما أشار AndreyT وغيرهم في هذا المنصب ، وهذا النهج هو شكل عودي الخوارزمية ، حيث صريحة تمكنت كومة يستخدم بدلا من وحدة المعالجة المركزية كومة حيث العودية يقام على مستوى أثناء الحلقة.قال هذا ، فهو يختلف من تنفيذ العودية في حد ذاته في بضع خفية بعد نواح هامة:

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

Answer 2

اتساع البحث الأول

Answer 3

أنت تبحث عن اجتياز بلاي. أعتقد أنك تستطيع أن تفعل ذلك غير متكرر مع طابور:. في شبة الكود:

إنشاء قائمة انتظار فارغة، ثم دفع عقدة الجذر.

while nonempty(q)
  node = pop(q)
  visit(node)
  foreach child(node)
    push(q,child)

Answer 4

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

Answer 5

استخدم مجموعة من العقد. وضع الجذر في مجموعة للبدء. ثم في حلقة، وسحب عقدة من مجموعة، أزوره، ثم وضع الأطفال في المجموعة. عندما مجموعة فارغ، انت القيام به.

Answer 6

في شبة الكود:

currentList = list( root )
nextList = list()
while currentList.count > 0:
    foreach node in currentList:
        nextList.add(node.children)
    currentList = nextList

Answer 7

إذا كنت تبدأ في عقدة الجذر، وإلا زيارة الأهل / الأطفال من العقد لديك بالفعل زار، هناك <م> بأي حال من الأحوال لاجتياز الشجرة مثل التي تزورها عقدة قبل زيارة أجداده .

وأي نوع من اجتياز، وعمق أولا (عودي / كومة القائم)، واتساع أولا (طابور القائم)، أو مجرد سحبهم من مجموعة غير مرتبة، محدودة عمق ستعمل.

وأسلوب "أفضل" يعتمد على الشجرة. اتساع أولا أن تعمل بشكل جيد لشجرة طويلة جدا مع قليل من الفروع. عمق أولا أن تعمل بشكل جيد للأشجار مع العديد من الفروع.

ومنذ العقد فعلا مؤشرات لآبائهم، وهناك أيضا خوارزمية ثابتة الذاكرة، لكنه أبطأ بكثير.

Answer 8

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

والمرجعي: http://en.wikipedia.org/wiki/Iterative_deepening

Answer 9

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

def walkTree(root, visit_func):
    cur  = root
    nextChildIndex = 0

    while True:
        visit_func(cur)

        while nextChildIndex >= len(cur.children) and cur is not root:
            nextChildIndex = cur.parent.children.index(cur) + 1
            cur  = cur.parent

        if nextChildIndex >= len(cur.children):
            break

        cur = cur.children[nextChildIndex]
        nextChildIndex = 0

وأنا متأكد من أنه يمكن مصقول قليلا، وجعلها أكثر إيجازا وأسهل للقراءة، ولكن هذا هو جوهر.

Answer 10

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