رایانه

سه روش استاندارد برای پیمایش درختهای دودویی وجود داره: پیمایش پیشوندی (preorder)، پیمایش میانوندی (inorder) و پیمایش پسوندی (postorder).

تعاریف بازگشتی این پیمایش ها به ترتیب زیره:

پیمایش پیشوندی:

1- پردازش ریشه

۲- پیمایش زیردرخت چپ ریشه به روش پیشوندی

3- پیمایش زیردرخت راست ریشه به روش پیشوندی

پیمایش میانوندی:

1- پیمایش زیردرخت چپ ریشه به روش میانوندی

2- پردازش ریشه

3- پیمایش زیردرخت راست ریشه به روش میانوندی

پیمایش پسوندی:

1- پیمایش زیردرخت چپ ریشه به روش پسوندی

2- پیمایش زیردرخت راست ریشه به روش پسوندی

3- پردازش ریشه

فرض کنیم برای ذخیره سازی اطلاعاتی از نوع عدد صحیح از درخت دودویی استفاده بشه. از ساختار زیر برای تعریف گره درخت بهره می بریم:

struct node

{

int info ;

node *parent ;

node *Lchild ;

node *Rchild ;

} ;

برای چاپ محتویات گرههای درخت با پیمایشهای سه گانه می شه توابع بازگشتی به صورت زیر پیاده سازی کرد:

void preorder ( node *root )

{

if ( !root )

return;

cout << "(" << root->info << ")" ;

preorder ( root->Lchild ) ;

preorder ( root->Rchild ) ;

}

void inorder ( node *root )

{

if ( !root )

return;

inorder ( root->Lchild ) ;

cout << "(" << root->info << ")" ;

inorder ( root->Rchild ) ;

}

void postorder ( node *root )

{

if ( !root )

return;

postorder ( root->Lchild ) ;

postorder ( root->Rchild ) ;

cout << "(" << root->info << ")" ;

}

توجه داشته باشید که در این روش نیازی به فیلد parent گره نداریم.

علاوه بر این، دو روش دیگه هم برای پیاده سازی پیمایشها وجود داره: روش غیر بازگشتی با استقاده از پشته و روش غیر بازگشتی بدون استفاده از پشته.

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