حل تشریحی سوال شماره 38 دروس مشترک (ساختمان‌های گسسته، ساختمان داده‌ها، طراحی الگوریتم، مهندسی نرم‌افزار، شبکه‌های کامپیوتری)

فرض کنید یک درخت دودویی با n گره داریم و میخواهیم از دو پشته و یک صف معمولی برای انجام پیمایش در

عمق (DFS) و پیمایش در عرض (BFS) به صورت همزمان استفاده کنیم شرایط زیر باید رعایت شود.

گره ریشه ابتدا در هر دو پشته و صف قرار می گیرد.

در هر مرحله یک گره از پشته اول برای پیمایش در عمق (DFS) و یک گره از صف برای پیمایش در عرض

(BFS) خارج می شود.

هنگام پیمایش فرزندان گره خارج شده باید طبق قواعد زیر به داده ساختارهای مربوطه اضافه شود:

الف - فرزندان چپ و راست گره به پشته دوم اضافه میشوند برای پیمایش DFS)

ب - فرزندان چپ و راست گره و به صف اضافه میشوند برای پیمایش BFS)

در نهایت الگوریتم تمام گره های درخت را پیمایش میکند.

پیچیدگی زمانی این الگوریتم در بدترین حالت چیست؟