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

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

به عنوان مثال برای درخت ۳ رأسی با نام 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;
}

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

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