زیپ

دستورالعمل‌ها

ساختن یک zipper برای یک درخت دودویی.

Zippers روشی کاملاً تابعی برای پیمایش درون یک ساختار داده و دست‌کاری آن هستند. آن‌ها در اصل یک ساختار داده و یک اشاره‌گر به درون آن ساختار داده را در خود دارند (که به آن «کانون» می‌گویند).

برای نمونه، اگر یک درخت رز داشته باشیم (درختی که هر گره آن یک مقدار و فهرستی از گره‌های فرزند دارد)، یک zipper ممکن است از این عملیات پشتیبانی کند:

• from_tree (یک zipper از درخت رز بیرون می‌کشد، کانون روی گره‌ی ریشه است)
• to_tree (درخت رز را از zipper بیرون می‌کشد)
• value (مقدار گره‌ی کانون را می‌گیرد)
• prev (کانون را به فرزند قبلی همان والد منتقل می‌کند و یک zipper تازه برمی‌گرداند)
• next (کانون را به فرزند بعدی همان والد منتقل می‌کند و یک zipper تازه برمی‌گرداند)
• up (کانون را به والد منتقل می‌کند و یک zipper تازه برمی‌گرداند)
• set_value (مقدار گره‌ی کانون را تنظیم می‌کند و یک zipper تازه برمی‌گرداند)
• insert_before (یک زیردرخت تازه پیش از گره‌ی کانون درج می‌کند، این زیردرخت prev گره‌ی کانون می‌شود و یک zipper تازه برمی‌گرداند)
• insert_after (یک زیردرخت تازه پس از گره‌ی کانون درج می‌کند، این زیردرخت next گره‌ی کانون می‌شود و یک zipper تازه برمی‌گرداند)
• delete (گره‌ی کانون و همه‌ی زیردرخت‌ها را حذف می‌کند؛ کانون در صورت امکان به گره‌ی next، در غیر این صورت در صورت امکان به گره‌ی prev و در غیر این صورت به گره‌ی والد منتقل می‌شود و یک zipper تازه برمی‌گرداند)

نکته‌ها

این تمرین به برابری سفارشی می‌پردازد. برای اطلاعات بیشتر این صفحه را ببینید.