في المقال السابق ، قلت خوارزمية التقويم العودية (الجذر الأول للشجرة (التسلسل الأول)).
لخص الخوارزمية غير المثيرة للتجاوز الأول.
1) أدخل المكدس ، وذلك أساسًا لإدخال العقدة الأولى ، ثم قم بزيارة هذه العقدة
2) بينما
3) الطفل المناسب للعقدة IF صحيح ، نقل إلى 1) استمر في اجتياز ، وإلا سيتم الخروج من العقدة الحالية ونقلها إلى العقدة الأصل التي تتجاوز 1)
انظر أولاً إلى الخوارزمية التي تتوافق مع هذه الفكرة:
نسخ رمز رمز على النحو التالي:
int preorderTraversenonRcursiveex (const bitree & t ، int (*visitnode) (بيانات TelemType)))
{{
إذا (t == null)
{{
العودة -1 ؛
}
bitnode *pbinode = t ؛
sqstack s ؛
initStack (& s) ؛
push (& s ، (selectype) t) ؛
بينما (! isstackedy (s))
{{
بينما (pbinode)
{{
VisitNode (pbinode-> البيانات) ؛
إذا (pbinode! = t)
{{
push (& s ، (selectype) pbinode) ؛
}
pbinode = pbinode-> lchild ؛
}
إذا (pbinode == null)
{{
pop (& s ، (selemtype*) & pbinode) ؛
}
إذا (pbinode-> rchild == null)
{{
pop (& s ، (selemtype*) و pbinode) ؛
}
pbinode = pbinode-> rchild ؛
}
العودة 0 ؛
}
ملاحظة: 1) يتم استخدام بنية المكدس هنا ، ويمكنك رؤية المكدس المخزن بترتيب الهيكل أعلاه
2) عند حفظ العقدة هنا ، فإن ما أحفظه هو عنوان المؤشر ، أي عنوان العقدة ، ويحولها إلى تخزين int. لماذا تفكر في استخدام المؤشرات بنفسك؟
الخوارزمية أعلاه خاطئة في الواقع! لماذا؟ لقد راجعت هنا لفترة طويلة. لأنه إذا كان المكدس فارغًا ، ولكن لا يزال هناك شجرة الشجرة الصحيحة ، فلن يتم التحقق منها كثيرًا بعد أن كتبت ذلك ، ثم أوضحت ذلك في وقت لاحق. عندما تكون شجرة الطفل اليسرى فارغة ، على النحو التالي: على النحو التالي:
نسخ رمز رمز على النحو التالي:
int preorderTraversenonRcursive (const bitree & t ، int (*visitnode) (بيانات TelemType)))
{{
إذا (t == null)
{{
العودة -1 ؛
}
bitnode *pbinode = t ؛
sqstack s ؛
initStack (& s) ؛
push (& s ، (selectype) t) ؛
بينما (! isstackedy (s))
{{
getTop (s ، (selectype*) & pbinode) ؛
بينما (pbinode)
{{
VisitNode (pbinode-> البيانات) ؛
pbinode = pbinode-> lchild ؛
push (& s ، (selectype) pbinode) ؛
}
إذا (pbinode == null)
{{
pop (& s ، (selemtype*) & pbinode) ؛
}
إذا (! isStackedy (s))
{{
pop (& s ، (selemtype*) & pbinode) ؛
pbinode = pbinode-> rchild ؛
push (& s ، (selectype) pbinode) ؛
}
}
العودة 0 ؛
}
هذا هو الحال. اضغط عليه في عقدة الطفل الأيمن ، ثم حدد ما إذا كان الطفل الأيسر للشجرة اليمنى فارغًا ، ويواصل الدورة.
هناك نفايات هنا: أحدهما هو دفع العقد من الطفل الفارغ للدخول إلى المكدس ، والآخر هو استخدام GetTop بشكل متكرر للحصول على العنصر العلوي من المكدس
العودة هنا لمشاهدة الخوارزمية المصممة أولاً ، حيث لا يتم الضغط على العقدة الفارغة في المؤشر الفارغ أو الطفل الفارغ ، ولكن لا يمكن إخراجها تمامًا. NULL لاغية هذا ، بحيث لن يكون هناك إحراج لن يعرض عقدة شجرة الشجرة الفرعية اليمنى ، على النحو التالي: على النحو التالي:
نسخ رمز رمز على النحو التالي:
// عبادة شجرة ثنائية
int preorderTraversenonRcursiveex (const bitree & t ،
int (*visitnode) (بيانات TelemType))
{{
إذا (t == null)
{{
العودة -1 ؛
}
bitnode *pbinode = t ؛
sqstack s ؛
initStack (& s) ؛
push (& s ، (selectype) t) ؛
بينما (! isStackedy (s) || pbinode) // التعديل الرئيسي هو هذه الجملة
{{
بينما (pbinode)
{{
VisitNode (pbinode-> البيانات) ؛
إذا (pbinode! = t)
{{
push (& s ، (selectype) pbinode) ؛
}
pbinode = pbinode-> lchild ؛
}
إذا (pbinode == null)
{{
pop (& s ، (selemtype*) & pbinode) ؛
}
إذا (pbinode-> rchild == null)
{{
pop (& s ، (selemtype*) و pbinode) ؛
}
pbinode = pbinode-> rchild ؛
}
العودة 0 ؛
}
بعد إضافة الحلقة الأولى ، تكون قضية الاختبار مشابهة للشجرة الثنائية. على النحو التالي ، اختبر الشجرة الثنائية في القسم السابق:
في هذا الوقت ، لا تزال بيانات الإدخال 12 34 0 0 78 0. نتائج الاختبار هي كما يلي:
--- Bitree ---
الرجاء إدخال بيانات عقدة Bitree:
12
الرجاء إدخال بيانات عقدة Bitree:
34
الرجاء إدخال بيانات عقدة Bitree:
0
الرجاء إدخال بيانات عقدة Bitree:
0
الرجاء إدخال بيانات عقدة Bitree:
78
الرجاء إدخال بيانات عقدة Bitree:
0
الرجاء إدخال بيانات عقدة Bitree:
0
12 34 78
هذا لا يكفي للاختبار ، انظر إلى الشجرة الثنائية التالية
في هذا الوقت ، يجب أن تكون بيانات الإدخال: 12 34 24 0 0 0 0 0 0 78 37 0 0. نتائج الاختبار هي كما يلي:
--- Bitree ---
الرجاء إدخال بيانات عقدة Bitree:
12
الرجاء إدخال بيانات عقدة Bitree:
34
الرجاء إدخال بيانات عقدة Bitree:
أربعة وعشرون
الرجاء إدخال بيانات عقدة Bitree:
0
الرجاء إدخال بيانات عقدة Bitree:
0
الرجاء إدخال بيانات عقدة Bitree:
50
الرجاء إدخال بيانات عقدة Bitree:
0
الرجاء إدخال بيانات عقدة Bitree:
0
الرجاء إدخال بيانات عقدة Bitree:
78
الرجاء إدخال بيانات عقدة Bitree:
37
الرجاء إدخال بيانات عقدة Bitree:
0
الرجاء إدخال بيانات عقدة Bitree:
0
الرجاء إدخال بيانات عقدة Bitree:
0
12 34 24 50 78 37
يمكن أن نرى من التمرير الأولي أنه صحيح. ، ثم إضافته للانضمام إليه.