حل تشریحی سوال شماره 40 دروس مشترک (ساختمان‌های گسسته، ساختمان داده‌ها، طراحی الگوریتم، مهندسی نرم‌افزار، شبکه‌های کامپیوتری)

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

به نام مسیر ویژه را روی این درخت پیاده سازی کنید:

• مسیر ویژه از ریشه شروع میشود و در هر مرحله به یک فرزند چپ با راست حرکت می‌کند.
• شرط حرکت:

اگر مقدار گره فعلی زوج باشد به فرزند چپ بروید.

اگر مقدار گره فعلی فرد باشد به فرزند راست بروید.

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

با توجه به این که ساختار درخت به صورت سطح به سطح (Level Order) در یک صف معمولی (Queue) ذخیره

شده است و شما میتوانید از دو پشته (Stacks) و یک صف استفاده کنید پیچیدگی زمانی محاسبه این مسیر

ویژه چیست؟ (n تعداد کل گر‌ها و ارتفاع درخت است.)