پیمایش_درخت
درخت‌های بینهایت
با اینکه عموماً پیمایش روی درخت‌هایی با تعداد گره محدود انجام می‌شود اما امکان پیاده‌سازی آن روی درخت‌های بی‌نهایت و نامحدود نیز وجود دارد. حتی بعضی درخت‌های محدود نیز آنقدر بزرگند که می‌توان به عنوان درخت‌های بینهایت آن‌ها را مورد بررسی و آنالیز قرار داد مانند [//en.wikipedia.org/wiki/Game_tree درخت بازی] یا [//en.wikipedia.org/wiki/Chess شطرنج]. این یک علاقه خاص در برنامه‌نویسی تابعی است؛ بنابراین ساختمان‌های داده بی‌نهایت اگر (به شدت) مورد ارزیابی قرار نگرفته‌اند اغلب می‌تواند تعریف شود و کار کند، در این صورت زمان بی‌نهایتی خواهد برد. برخی ازدرختان محدود برای نمایش ساده بیش از حد بزرگ هستند نظیر درخت بازی، شطرنج، بازی گو و نظایرآن. این کاری سودمند و مفید است که آن‌ها را به عنوان اینکه اگر آن‌ها بی‌نهایت بودند بررسی کنیم. یک نیاز اساسی برای پیمایش، ملاقات کردن هر گره است. برای درختان بی‌نهایت الگوریتم‌های ساده اغلب به شکست می‌انجامند. به عنوان مثال درخت دودویی داده شده با عمق بی‌نهایت، پیمایش اول-عمق از یک سمت درخت پایین خواهد رفت (بنابر قانون سمت چپ). هیچگاه مابقی را ملاقات نخواهدکرد؛ و در واقع اگر پیمایش میانوندی و پسوندی هیچگاه گرهی را ملاقات نکنند پس باید به برگ رسیده باشند (ولی در واقعیت اینطور نیست). در مقابل، پیمایش اول-سطح (پیمایش سطحی) درخت دودویی با عمق بی‌نهایت را بدون مشکل پیمایش می‌کند؛ و در واقع هر درخت را با فاکتور انشعاب محدود پیمایش می‌کند. به بیانی دیگر درختی با ۲ عمق داده شده که گره ریشه فرزندان بی‌نهایت بسیاری دارد و هر یک از این فرزندان دو فرزند دارند، پیمایش اول-عمق تمامی گره‌ها را ملاقات می‌کند در مرتبه اول از گره‌های نوه (فرزند فرزند هر گره) تهی می‌شود، سپس به سمت بعدی حرکت می‌کند (فرض می‌کنیم که آن پیمایش پسوندی نیست). در مقابل پیمایش اول- سطح هیچگاه به گره نوه نمی‌رسد، بنابراین آن به دنبال تهی کردن فرزند اول است. تجزیه و تحلیل‌های پیچیده تری از زمان اجرا می‌توانند از طریق اعداد ترتیبی نامحدود داده شوند؛ بنابراین جستجوهای اول-عمق یا اول-سطح پیمایشات درخت درخت بی‌نهایت را انجام نمی‌دهند و برای درختان خیلی بزرگ کارآمد نیستند. به هر حال، پیمایشات ترکیبی می‌تواند درختان بی‌نهایت (قابل شمارش) را پیمایش کنند مخصوصاً از طریق اثبات مورب («مورب» ترکیبی است از افقی و عمودی که سطح و عمق را مرتبط می‌کند). مشخصا، شاخه‌های درخت بی‌نهایت داده شده با عمق نامحدود گره ریشه را با علامت ، فرزندان گره ریشه را با علامت (۱)، (۲) و... نوه‌ها را با علامت (۱٬۱)، (۱٬۲) و ... (۲٬۱)، (۲٬۲)، .... مشخص می‌کند. در نتیجه، گره‌ها در یک تناظر یک به یک با توالی محدودی از اعداد مثبتی هستند، که قابل شمارش اندو می‌توانند برای مرتبه اول به وسیلهٔ مجموع ورودی‌ها و سپس با رعایت ترتیب واژه نگاری بین جمع داده شده (تنها توالی محدود با مقادیر داده شده جمع می‌شوند بنابراین تمامی ورودی‌هایی که به صورت رسمی بدان دسترسی یافته‌است، یک تعداد متناهی از ترکیب یک عدد طبیعی داده شده‌است) که یک پیمایش را می‌دهد، جایگذاری شوند. این می‌تواند به عنوان نگاشت عمق بی‌نهایت درخت باینری بر روی این درخت و سپس پیمایش اول-سطح تفسیر شود: جایگزینی ضلع پایینی متصل به گره والد به فرزندان دوم و بعدی خودش با ضلع سمت راست ازاولین فرزند به دومین فرزند و از دومین فرزند به سومین فرزند و ... . بنابراین در هر مرحله یک یا هر دو می‌توانند به پایین (اضافه کردن یک (۱)) یا به راست (اضافه کردن یک (۱) به آخرین عدد) (بجز ریشه که اضافی است و می‌تواند به پایین برود) بروند، که ارتباط و مراسلات بین درخت دودویی بی‌نهایت وشماره‌گذاری بالا را نشان می‌دهد. مجموع ورودی‌ها (منهای ۱) مربوط به فاصله از ریشه که برابر است با 2n-۱ گره در عمق n-1 در درخت دودویی بی‌نهایت.