پیمایش درخت

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو


پیمایش درخت[ویرایش]

در علم کامپیوتر پیمایش درختی { که به عنوان جستجوی درخت Arkiletian نیز شناخته میشود } یک شکل از پیمایش نموداری {گراف } است و به پروسه ملاقات هر گره در ساختمان درخت داده دقیقا در بار اول در روش سیستماتیک اشاره دارد . اینگونه پیمایشات به ترتیب گره ای که ملاقات میکنند دسته بندی شده اند. الگوریتم های زیر برای یک درخت دودویی شرح داده شده اند اما ممکن قابل تعمیم به سایر درخت ها نیز باشند.

انواع[ویرایش]

در مقایسه با ساختمان داده های خطی مانند لیست های پیوندی و آرایه یک بعدی که یک متد پیمایش استاندارد دارند {صورت خطی} ساختار های درختی میتوانند در مسیر های مختلفی پیمایش شوند. برای شروع از ریشه یک درخت دودویی سه گام اصلی وجود دارد که می تواند انجام شود در این صورت ترتیب انجام آنها نوع پیمایش درختی را مشخص میکند . این مراحل عبارتند از : انجام یک عمل در گره فعلی{که اشاره به دیدن گره دارد } ،پیمایش به سمت گره فرزند چپ و پیمایش به سمت گره فرزند راست.در برخی از روش ها پیمایش شامل تکرار همه گره ها می شود . چراکه از گره داده شده ممکن است بیش از یک گره بعدی وجود داشته باشد{ آن ساختمان داده خطی نیست } پس ، با فرض محاسبه ی متوالی {نه موازی} بعضی از گره ها باید در برخی مسیر ها به تعویق بیافتند و برای ملاقات های بعدی ذخیره شوند .این کار اغلب بواسطه پشته{ Stack} و از طریق الگوریتم LIFO و یا از طریق صف } {queueو از طریق الگوریتم FIFO انجام می شود . ساختمان داده همانند یک درخت بازگشتی است ، پیمایش می تواند به عنوان یک بازگشت تعریف شود ، در یک مد طبیعی و روشن گره های معوق به صورت ضمنی { مجازی} در پشته تماس ذخیره می شوند .نامی که به پیمایش ها داده میشود از ترتیبی که آن ها گره ها را ملاقات میکنند گرفته شده است . به بیان ساده تر پیشروی به سمت پایین {اول-عمق ، فرزند اول سپس نوه ، قبل از فرزند دوم } یا اول-سطح {اول سطح یا عرض ، فرزند اول سپس فرزند دوم قبل از نوه} ؟ پیمایش های اول –عمق بیشتر بر اساس وضعیت عناصر ریشه با توجه به گره های موجود در سمت چپ و راست دسته بندی شده اند . تصور کنید که گره چپ و راست در مکان خود ثابت هستند، پس گره ریشه می تواند در طرف چپ گره سمت چپ قرار داده شود{پیمایش پیشوندی }یااینکه بین گره راست و چپ قرار گیرد {پیمایش میانوندی } یا طرف راست گره سمت راست باشد {پیمایش پسوندی}.هیچگونه اختلاف مشابهی در پیمایش اول-سطح که به گرهفرزند نسبت داده شده وجود ندارد . پیمایش اول-سطح بی ابهام و واضح است.برای طراحی همیشه فرض بر این است که گره های سمت چپ بر گره های سمت راست مقدم هستند.این مرتب سازیمیتواندتازمانیکه همین ترتیب برای همه متد های پیمایش ، در نظر گرفته وارونه شود. پیمایش اول –عمق از طریق پشته به آسانی قابل پیاده سازی است ، در حالی که اول-سطح به سادگی از طریق صف قابل پیاده سازی است .فراتر از این پیمایشات عمومی طرح های پیچیده تر و ترکیبی مختلفی نیز قابل پیاده سازی است ، نظیر جستجوهای عمق محدود (depth- limited) ، جستجوی تعمیق تکراری ( iterative deepening depth-first) .می‌خواهیم با حرکت روی یال‌های یک درخت، همهٔ گره‌های آن را هر کدام یک بار ملاقات کنیم. به این کار پیمایش درخت می‌گویند.بسته به این که کدام عنصر، کی ملاقات شود، پیمایش درخت لیست یا یک ترتیب خطی از عناصر آن درخت به ما می‌دهد. طبیعتاً پیمایش‌های متفاوت ترتیب‌های متفاوتی خواهند داد. سه روش معمول پیمایش درخت که بیشتر برای پیمایش درخت دودویی به کار می‌روند، عبارتند از:

اول‌عمق[ویرایش]

نوشتار(های) وابسته: الگوریتم جستجوی عمق اول

اول-عمق Depth-first سه نوع پیمایش اول- عمق وجود دارد : پیمایش پیشوندی ( Pre-Order) ، پیمایش میانوندی (In-Order ) ، پیمایش پسوندی (Post- order ) برای درخت دودویی ، آن ها در هر گره ، با شروع از گره ریشه به عنوان عملیات بازگشتی تعریف شده اند که الگوریتم آن ها به شرح زیر است: پیمایش پیش‌ترتیب:

  1. ریشه را ملاقات کن.
  2. زیر درخت چپ را پیمایش کن.
  3. زیر درخت راست را پیمایش کن.

پیمایش میان‌ترتیب:

  1. زیردرخت چپ را پیمایش کن.
  2. ریشه را ملاقات کن.
  3. زیردرخت‌ راست را پیمایش کن.

پیمایش پس‌ترتیب:

  1. زیر درخت چپ را پیمایش کن.
  2. زیر درخت راست را پیمایش کن.
  3. ریشه را ملاقات کن.

Pre-order preorder(node)

 if node == null then return
 visit(node)
 preorder(node.left) 
 preorder(node.right)

iterativePreorder(node)

 parentStack = empty stack
 while (not parentStack.isEmpty() or node ≠ null)
   if (node ≠ null) 
     visit(node)
     if (node.right ≠ null) parentStack.push(node.right) 
     node = node.left   
   else     
    node = parentStack.pop()

In-order inorder(node)

 if node == null then return
 inorder(node.left)
 visit(node)
 inorder(node.right)

iterativeInorder(node)

 parentStack = empty stack
 while (not parentStack.isEmpty() or node ≠ null)
   if (node ≠ null)
     parentStack.push(node)
     node = node.left
   else
     node = parentStack.pop()
     visit(node)
     node = node.right

Post-order postorder(node)

 if node == null then return
 postorder(node.left)
 postorder(node.right)
 visit(node)

iterativePostorder(node)

 parentStack = empty stack  
 lastnodevisited = null 
 while (not parentStack.isEmpty() or node ≠ null)
   if (node ≠ null)
     parentStack.push(node)
     node = node.left
   else
     peeknode = parentStack.peek()
     if (peeknode.right ≠ null and lastnodevisited ≠ peeknode.right) 
       /* if right child exists AND traversing node from left child, move right */
       node = peeknode.right
     else
       visit(peeknode)
       lastnodevisited = parentStack.pop() 
       node = null

هر کدام از این روش‌های پیمایش را می‌توان به دو روش بازگشتی و غیر بازگشتی پیاده‌سازی کرد.

درخت عمومی Generic tree[ویرایش]

به منظور پیمایش هر درختی در پیمایش اول- عمق ، عملیات های بازگشتی زیر در هر گره انجام می شود: 1. انجام عمل پیمایش پیشوندی 2. برای هر i (با i=1 to n ) انجام میشود : 1. ملاقات iام ، اگر وجود داشته باشد . 2. انجام عملیات پیمایش میانوندی 3. انجام عملیات پیمایش پسوندی جایی که n تعداد گره های فرزند است ، بسطه به مشکلی که وجود دارد عملیات پیمایش پیشوندی ، میانوندی و پسوندی ممکن است بی اعتبار شوند و یا اینکه ممکن است شما بخواهید از یک گره فرزند خاصی بازدید کنید بنابراین این عملیات ها اختیاری هستند. همچنین در عمل (تمرین) ممکن است بیش از یک عملیات پیشوندی ، میانوندی و پسوندی نیاز باشد . به عنوان مثال زمان وارد شدن به یک درخت سه تایی ، یک عملیات پیشوندی بواسطه مقایسه ، بخش ها انجام شده است . ممکن است یک عملیات پسوندی پس از متوازن کردن مجدد درخت نیاز باشد.

اول‌سطح[ویرایش]

نوشتار(های) وابسته: الگوریتم جستجوی اول سطح

درخت ها می توانند به صورت سطح تربیب پیمایش شوند، به طوریکه همه گره ها در یک سطح را ملاقات می کنیم، سپس به ترتیب به سطوح پایین تر می رویم و تمام گره های آنها را ملاقات می کنیم.

سایر روش ها[ویرایش]

روش های پیمایش دیگری هم وجود دارند که جزء هیچ یک از دو روش بالا دسته بندی نمی شوند. جستجوی درختیِ مونته کاریو یکی از این روش هاست که روی محتمل ترین حرکات براساس توسعه ی درخت جستجو روی نمونه سازی تصادفی فضای محل جستجو بنا شده است.

مثال[ویرایش]

درخت دودویی:

یک درخت دودویی
اول‌عمق
  • دنباله پیمایش پیش‌ترتیب: A, B, D, E, H, I, C, F, G
  • دنباله پیمایش میان‌ترتیب: D, B, H, E, I, A, F, C, G
  • دنباله پیمایش پس‌ترتیب: D, H, I, E, B, F, G, C, A
اول‌سطح
  • دنباله پیمایش سطح‌تربیب: A, B, C, D, E, F, G, H, I

درخت های بینهایت[ویرایش]

با اینکه عموما پیمایش روی درخت هایی با تعداد گره محدود انجام می شود اما امکان پیاده سازی آن روی درخت های بی نهایت و نامحدود نیز وجود دارد. حتی بعضی درخت های محدود نیز آنقدر بزرگند که می توان بعنوان درخت های بینهایت آن ها را مورد بررسی و آنالیز قرار داد مانند درخت بازی یا شطرنج. این یک علاقه خاص در برنامه نویسی تابعی است. بنابراین ساختمان های داده بی نهایت اگر ( به شدت ) مورد ارزیابی قرار نگرفته اند اغلب میتواند تعریف شود و کار کند ، در این صورت زمان بی نهایتی خواهد برد . برخی ازدرختان محدود برای نمایش ساده بیش از حد بزرگ هستند نظیر درخت بازی ، شطرنج ، بازی گو و نظایرآن . این کاری سودمند و مفید سات که آن ها را به عنوان اینکه اگر آن ها بی نهایت بودند بررسی کنیم .یک نیاز اساسی برای پیمایش ، ملاقات کردن هر گره است . برای درختان بی نهایت الگوریتم های ساده اغلب به شکست می انجامند . به عنوان مثال درخت دودویی داده شده با عمق بی نهایت ، پیمایش اول-عمق از یک سمت درخت پایین خواهد رفت ( بنابر قانون سمت چپ ).هیچگاه مابقی را ملاقات نخواهدکرد. و در واقع اگر پیمایش میانوندی و پسوندی هیچگاه گرهی را ملاقات نکنند پس باید به برگ رسیده باشند (ولی در واقعیت اینطور نیست ).در مقابل ، پیمایش اول-سطح ( پیمایش سطحی ) درخت دودویی با عمق بی نهایت را بدون مشکل پیمایش میکند . و در واقع هر درخت را با فاکتور انشعاب محدود پیمایش میکند . به بیانی دیگر درختی با 2 عمق داده شده که گره ریشه فرزندان بی نهایت بسیاری دارد و هر یک از این فرزندان دو فرزند دارند، پیمایش اول-عمق تمامی گره ها را ملاقات میکند در مرتبه اول از گره های نوه ( فرزند فرزند هر گره ) تهی میشود ،سپس به سمت بعدی حرکت میکند ( فرض میکنیم که آن پیمایش پسوندی نیست ). در مقابل پیمایش اول- سطح هیچگاه به گره نوه نمیرسد ، بنابراین آن به دنبال تهی کردن فرزند اول است . تجزیه و تحلیل های پیچیده تری از زمان اجرا میتوانند از طریق اعداد ترتیبی نامحدود داده شوند .بنابراین جستجوهای اول-عمق یا اول-سطح پیمایشات درخت درخت بی نهایت را انجام نمیدهند و برای درختان خیلی بزرگ کارآمد نیستند . به هر حال، پیمایشات ترکیبی میتواند درختان بی نهایت ( قابل شمارش ) را پیمایش کنند مخصوصا از طریق اثبات مورب ( "مورب" ترکیبی است از افقی و عمودی که سطح و عمق را مرتبط میکند). مشخصا ، شاخه های درخت بی نهایت داده شده با عمق نامحدود گره ریشه را با علامت ()، فرزندان گره ریشه را با علامت (1) ، (2) و.... نوه ها را با علامت (1,1) ، (1,2) و .... (2,1) ، (2,2) ، .... مشخص میکند.در نتیجه ، گره ها در یک تناظر یک به یک با توالی محدودی از اعداد مثبتی هستند ، که قابل شمارش اندو میتوانند برای مرتبه اول بوسیله مجموع ورودی ها و سپس با رعایت ترتیب واژه نگاری بین جمع داده شده( تنها توالی محدود با مقادیر داده شده جمع میشوند بنابراین تمامی ورودی هایی که به صورت رسمی بدان دسترسی یافته است ، یک تعداد متناهی از ترکیب یک عدد طبیعی داده شده است ) که یک پیمایش را میدهد ، جایگذاری شوند .این میتواند به عنوان نگاشت عمق بی نهایت درخت باینری بر روی این درخت و سپس پیمایش اول-سطح تفسیر شود : جاگزینی ضلع پایینی متصل به گره والد به فرزندان دوم و بعدی خودش با ضلع سمت راست ازاولین فرزند به دومین فرزند و از دومین فرزند به سومین فرزند و ... . بنابراین در هر مرحله یک یا هر دو میتوانند به پایین ( اضافه کردن یک (1) ) یا به راست ( اضافه کردن یک (1) به آخرین عدد ) ( بجز ریشه که اضافی است و می تواند به پایین برود ) بروند ، که ارتباط و مراسلات بین درخت دودویی بی نهایت وشماره گذاری بالا را نشان میدهد . مجموع ورودی ها (منهای 1) مربوط به فاصله از ریشه که برابر است با 2n-1 گره در عمق n-1 در درخت دودویی بی نهایت .

انواع دیگر[ویرایش]

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

کاربرد ها[ویرایش]

پیمایش پیشوندی در حالی که گره ها و اضلاع را تکثیر میکند میتواند یک کپی کاملی از درخت دودویی را بسازد.پیمایش میانوندی به شکل رایج تری در جستجوی درخت دودویی مورد استفاده قرار میگیرد چراکه مقادیرزیر مجموعه را با توجه به مقایسه ای که درخت دودویی پیاده سازی میکند برمیگرداند. پیمایش پسوندی در هنگام حذف یا آزاد سازی گره ها و مقادیر میتواند یک درخت دودویی کامل را حذف کند،همچنین میتواند یک پسوند نمایشی از درخت دودویی را ایجاد کند .

پیاده سازی Implementation[ویرایش]

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

پیمایش موریس از نخ کشی استفاده میکند[ویرایش]

یک درخت دودویی نخ کشی شده بوسیله هر اشاره گر فرزند چپ (که در غیر این صورت پوچ است) به پیمایش میانوندی قبلی هر گره (اگر وجود داشته باشد ) اشاره میکند و هر اشاره گر فرزند راست (که در غیر این صورت پوچ است ) به جانشین پیمایش میانوندی هر گره اشاره میکند (اگر وجود داشته باشد). مزایا : 1.چون که از پشته تماس استفاده میکند و حافظه و زمان صرف میکند از بازگشت اجتناب میکند . 2. گره یک رکورد از والدینش نگه میدارد . معایب : 1. درخت پیچیده تر است. 2. در یک زمان تنها یک پیمایش قابل انجام است. 3. زمانی که هر دو فرزند حاضر نیستند و هر دو مقادیر گره ها به اجدادشان اشاره میکنند خیلی مستعد رخ دادن خطاست. پیمایش موریس یک پیاده سازی از پیمایش میانوندی است که از نخ کشی استفاده میکند: 1. ایجاد لینک هایی به جانشین میانوندی 2. چاپ داده مورد استفاده این لینک ها 3. بگرداندن تغییرات و بازگرداندن درخت اصلی

منابع[ویرایش]

  • قدسی، محمد. داده‌ساختارها و مبانی الگوریتم‌ها. تهران : موسسه فرهنگی فاطمی ، ۱۳۸۸ ISBN ۹۷۸-۹۶۴-۳۱۸-۵۴۹-۷.
  • جعفر، تنها. ناصر، آیت. ساختمان داده‌ها و الگوریتم‌ها(رشته کامپیوتر). تهران : دانشگاه پیام‌نور ، ۱۳۸۷ ISBN ۹۷۸-۹۶۴-۳۸۷-۵۰۶-۰.
  • Wikipedia contributors, "Tree traversal," Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Tree_traversal&oldid=533659477

(accessed 18 January 2013)