في حياة البرمجة ، نواجه دائمًا هياكل الأشجار. في الأيام القليلة الماضية ، نحتاج فقط إلى تشغيل بنية الأشجار ، لذلك نسجل أساليب وعمليات التشغيل الخاصة بنا. لنفترض الآن أن هناك شجرة مثل هذه ، (لا يهم ما إذا كانت شجرة ثنائية أم لا ، المبادئ هي نفسها)
1. أولوية العمق
الاختصار الإنجليزي هو DFS ، وهو البحث الأول عن العمق.
البحث الأول هو طريقة أكثر شيوعًا في المراحل المبكرة من زحفات التنمية. الغرض منه هو الوصول إلى العقد الورقية للهيكل الذي تم تفتيشه (أي ملفات HTML التي لا تحتوي على أي ارتباطات تشعبية). في ملف HTML ، عند تحديد ارتباط تشعبي ، سيقوم ملف HTML المرتبط بإجراء بحث عن عمق الأول ، أي ، يجب البحث في سلسلة منفصلة بالكامل قبل البحث عن نتائج الارتباط التشعبي المتبقي. يتبع البحث عن أولوية العمق الارتباط التشعبي على ملف HTML حتى لا يمكن تعميقه ، ثم يعود إلى ملف HTML معين ، ويستمر في تحديد الارتباطات التشعبية الأخرى في ملف HTML. عندما لا تتوفر ارتباطات تشعبية أخرى ، انتهى البحث. تتمثل العملية ببساطة في التعمق في كل مسار فرعي ممكن حتى لا يمكن أن تكون أعمق ، ولا يمكن الوصول إلى كل عقدة إلا مرة واحدة. بالنسبة للمثال أعلاه ، فإن نتيجة اجتياز العمق الأول هي: A ، B ، D ، E ، I ، C ، F ، G ، H. (على افتراض أن الجانب الأيسر من عقدة الطفل قد ترك أولاً).
يتم استخدام أولوية العمق لاجتياز كل عقدة ، ويتطلب بنية البيانات مثل الكومة. خاصية المكدس هي الذهاب أولاً ثم الخروج. عملية التجوال بأكملها هي كما يلي:
أولاً ، اضغط على العقدة A في الكومة ، المكدس (أ) ؛
تنبثق العقدة A واضغط على العقد الفرعية A و B في الكومة في نفس الوقت. في هذا الوقت ، يكون B في الجزء العلوي من الكومة ، المكدس (B ، C) ؛
المنبثقة في العقدة B واضغط على العقد الطفل B و D في الكومة. في هذا الوقت ، D في الجزء العلوي من الكومة ، المكدس (D ، E ، C) ؛
منبثقة العقدة D ، لا يتم الضغط على العقد الفرعية ، و E في الجزء العلوي من الكومة ، المكدس (E ، C) ؛
POP UP NODE E و PRESS END NODE INTE INTE (I ، C) ؛
... بدوره ، ويتم الانتهاء من اجتياز النهائي. رمز Java تقريبًا على النحو التالي:
public void depthfirst () {stack <string ، object >> nodestack = new stack <map <string ، object >> () ؛ map <string ، object> node = new hashmap <string ، object> () ؛ nodestack.add (عقدة) ؛ بينما (! nodestack.isempty ()) {node = nodestack.pop () ؛ system.out.println (node) ؛ // احصل على عقدة الطفل للعقدة. بالنسبة للشجرة الثنائية ، فإن الحصول على عقدة الطفل اليسرى والعقدة الطفل اليمنى لقائمة العقدة <map <string ، object >> children = getChildren (node) ؛ if (children! = null &&! childs.isempty ()) {for (map child: child)2
الاختصار الإنجليزي هو BFS ، مما يعني اتساع Firstsearch. وفقًا لاختبار العملية ، يتم الوصول إلى كل طبقة من العقد بدورها ، وبعد الوصول إلى طبقة واحدة ، يمكن لكل عقدة الوصول إليها مرة واحدة فقط. على سبيل المثال أعلاه ، فإن نتيجة اجتياز العرض الأول هي: A ، B ، C ، D ، E ، F ، G ، H ، I (على افتراض أن كل طبقة من العقد يمكن الوصول إليها من اليسار إلى اليمين).
يتم استخدام أولوية العرض لاجتياز كل عقدة ، ويحتاج بنية بيانات مثل قائمة الانتظار. سمة قائمة الانتظار هي الأولى ، الأولى ، وفي الواقع ، يمكنها أيضًا استخدام قائمة انتظار مزدوجة. الفرق هو أنه يمكن إدخال العقد وظهرت في الموضع الأول من قائمة الانتظار المزدوجة. عملية التجوال بأكملها هي كما يلي:
أول إدراج العقدة A في قائمة الانتظار ، قائمة الانتظار (أ) ؛
المنبثقة العقدة A وإدراج العقد الطفل B و C من A في قائمة الانتظار. في هذا الوقت ، يكون B في بداية قائمة الانتظار و C في نهاية قائمة الانتظار ، قائمة الانتظار (B ، C) ؛
المنبثقة في العقدة B وإدراج العقد الطفل D و E من B في قائمة الانتظار في نفس الوقت. في هذا الوقت ، يكون C في بداية قائمة الانتظار و E في نهاية قائمة الانتظار ، قائمة الانتظار (C ، D ، E) ؛
المنبثقة العقدة C وإدراج العقد الفرعية F ، G ، H من C في قائمة الانتظار. في هذا الوقت ، يكون D على رأس قائمة الانتظار و H في نهاية قائمة الانتظار ، قائمة الانتظار (D ، E ، F ، G ، H) ؛
POP UP NODE D ، D ليس لديها عقد طفل ، في هذا الوقت e موجود على رأس قائمة الانتظار ، H في ذيل قائمة الانتظار ، قائمة الانتظار (E ، F ، G ، H) ؛
... بدوره ، ويتم الانتهاء من اجتياز النهائي. رمز Java تقريبًا على النحو التالي:
خبز الباطل العام () {deque > nodedeque = arraydeque جديد > () ؛ رسم خريطة العقدة = هاشماب جديد () ؛ novedequ.add (العقدة) ؛ بينما (! nodedeque.isempty ()) {node = nodedequ.peekfirst () ؛ System.out.println (Node) ؛ // الحصول على عقدة الطفل للعقدة. بالنسبة للشجرة الثنائية ، فإن عقدة الطفل الأيسر والعقدة الطفل اليمنى للعقدة هي الحصول على قائمة العقدة. > الأطفال = getChildren (العقدة) ؛ if (الأطفال! = null &&! children.isempty ()) {for (خريطة الطفل: الأطفال) {novedequ.add (child) ؛ }}}} // يتم استخدام قائمة الانتظار المزدوجة هنا ، والتي هي نفسها باستخدام قائمة الانتظار لخص
ما ورد أعلاه هو كل محتوى هذه المقالة حول أمثلة رمز تنفيذ Java للعمق الأول والولاية ، وآمل أن يكون ذلك مفيدًا للجميع. يمكن للأصدقاء المهتمين الاستمرار في الرجوع إلى الموضوعات الأخرى ذات الصلة على هذا الموقع. إذا كانت هناك أي أوجه قصور ، فيرجى ترك رسالة لإشارةها. شكرا لك يا أصدقائك لدعمكم لهذا الموقع!