المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:الگوریتم:پیمایش درخت‌ها پیش‌ترتیب٬ میان‌ترتیب و پس‌ترتیب

پیمایش درخت‌ها؛ پیش‌ترتیب، میان‌ترتیب و پس‌ترتیب

تعریف

همانطور که در بخش پیمایش گراف اشاره شد، پیمایش درخت‌ها نیز معمولا جهت محاسبه‌ی مقادیری انجام می‌شود که برای حل برخی مسائل کاربرد دارند. یکی از این مقادیر دنباله‌های پیش‌ترتیب، میان‌ترتیب و پس‌ترتیب مربوط به درخت‌ها می‌باشد.

فرض کنید می‌خواهیم در پیمایش یک درخت،‌ دنباله‌ای از رئوس به دست بیاوریم که نشان‌دهنده‌ی ترتیب مشاهده رئوس در آن پیمایش باشد.

به عنوان مثال برای درخت ۳ رأسی با نام T که در آن رأس ۱ ریشه باشد و دو رأس ۲و ۳ به ریشه متصل باشند را در نظر می‌گیریم و پیمایش عمق‌اول را از ریشه شروع کنیم و ابتدا به رأس ۲ رفته و پس از بازگشت به ریشه به رأس ۳ می‌رویم. فرض کنیم در ابتدای ورود به هر رأس نام آن را به دنباله اضافه کنیم، در این صورت دنباله‌ی $<1, 2, 3>$(از چپ به راست) تولید خواهد شد.

حال فرض کنید نحوه‌ی تولید دنباله را به نحوی دهیم که هنگام پایان کار در یک رأس و خروج پیمایش از آن، نام آن را به دنباله اضافه نماییم. در این صورت دنباله‌ی تولید شده $<3, 2, 1>$ خواهد بود.

به دنباله‌ی اول دنباله‌ی پیش‌ترتیب و به دنباله‌ی دوم دنباله‌ی پس‌ترتیب پیمایش مربوطه از درخت داده شده می‌گوییم، چرا که در دنباله‌ی اول، پیش از شروع کار در هر رأس و در دنباله دوم پس از اتمام کار در هر رأس نام آن را به دنباله افزودیم.

این دو نوع از دنباله‌های پیمایشی برای هر درختی قابل محاسبه هستند. اما نوع دیگری از دنباله‌های پیمایشی که تنها برای درخت‌های دودویی کاربرد دارد، دنباله‌ی میان‌ترتیب نام دارد که در آن نام هر رأس را در زمانی که پیمایش برای یکی از زیردرخت‌های رأس به اتمام رسیده و برای ورود به زیردرخت دوم رأس به آن وارد می‌شود، به دنباله اضافه می‌نماییم که در درخت T دنباله‌ی $<2, 1, 3>$ را تولید می‌نماید.

لازم به ذکر است که این دنباله‌ها برای هر یک از دیگر انواع پیمایش‌ها مانند سطح‌اول، طبقه به طبقه و … نیز به طریق مشابه قابل محاسبه است و تفاوت انواع دنباله‌های پیمایشی تنها در تعریف زمان اضافه نمودن رأس به انتهای دنباله‌ی مربوطه است.

پیاده‌سازی برای پیمایش عمق‌اول

preOrder.cpp
void preOrder(int x){
	queue.push_back(x);
	for(int i=0;i< children[x].size(); i++){
		preOrder(children[x][i]);
	}
	return;
}
postOrder.cpp
void postOrder(int x){
	for(int i=0;i< children[x].size(); i++){
		postOrder(children[x][i]);
	}
	queue.push_back(x);
}
inOrder.cpp
void inOrder(int x){
	inOrder(leftChild[x]);
	queue.push_back(x);
	inOrder(rightChild[x]);
	return;
}

کابردها

زمان_شروع_و_پایان_گره‌ها_در_پیمایش_میان‌ترتیب

مراجع


ابزار صفحه