موضوع مقاله: درخت دودویی نخی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # درخت دودویی نخی | مقدمه: در درختی که اتصالات تهی آن به این صورت استفاده شده‌است، درخت دودویی نخ‌کشی شده نامیده می‌شود. | ## بخش 1: درخت دودویی نخی | برای مثال، درخت دودویی نخ‌کشی شده به روش میانوندی به شکل زیر تعریف می‌شود: «برای هر گره، اتصال تهی سمت راست، به گره بعدی در پیمایش میانوندی اشاره کنند و اتصال تهی سمت چپ، به گره قبلی در پیمایش میانوندی اشاره کنند.» درخت دودویی نخ‌کشی شده این امکان را فراهم می‌سازد که پیمایش مقادیر در درخت دودویی به روش پیمایش خطی، سریعتر از پیمایش بازگشتی درخت به صورت میانوندی صورت گیرد. همچنین پیدا کردن والد یک گره در یک درخت دودویی نخی، بدون استفاده از اشاره‌گرهای والد یا بدون استفاده از پشته هم امکان‌پذیر است، هر چند که این کار کمی آهسته است. این قابلیت وقتی مفید است که فضای پشته اندک باشد یا وقتی که پشته اشاره‌گرهای والد غیرقابل دسترس باشد. (برای پیدا کردن گره والد به روش الگوریتم جستجوی عمق اول) برای اینکه ببینیم این کار چگونه امکان‌پذیر است، گرهی به نام k را تصور کنید که یک فرزند سمت راست به نام r دارد. در مورد اول که r یک فرزند سمت چپ دارد، آن گره فرزند هم به نوبه خود یا باید یک فرزند سمت چپ داشته باشد یا باید اتصالی نخی به k باشد و به همین ترتیب این قضیه برای کلیه فرزندان سمت چپ صادق است. بنابراین با دنبال کردن زنجیره‌ای از اشاره‌گرهای سمت چپ گره r، ما بالاخره به گره k می‌رسیم. به شکل مشابه، اگر گرهی به نام p داشته باشیم که فرزند سمت چپ آن q است، با دنبال کردن زنجیره اشاره‌گرهای سمت راست q، بالاخره به p خواهیم رسید. | ## بخش 2: درخت دودویی نخی | آرایه پیمایش میانوندی نخ‌ها نشانه‌روهایی به گره ماقبل و گره مابعد گره فعلی هستند. گره ماقبل و گره مابعد بستگی به پیمایش یک درخت دارد که معمولاً از پیمایش میانوندی استفاده می‌شود. وسط|قاب بنابراین کافیست اشاره‌گرهای تهی سمت راست هر گره را به گره مابعد آن و اشاره‌گر تهی سمت چپ هر گره را به گره ماقبل آن متصل کنیم. در شکل بالا اشاره‌گر تهی سمت راست E به F متصل شده‌است و اشاره‌گر تهی سمت چپ E به D متصل شده‌است. مثال درخت دودویی زیر را در نظر بگیرید: وسط|قاب می‌خواهیم این درخت را بر اسا پیمایش میانوندی آن نخ‌کشی کنیم. حالا می‌توان اشاره‌گرهای تهی سمت راست را به گره مابعد و اشاره‌گرهای تهی سمت چپ را به گره مابعد نخ‌کشی کرد. شکل زیر پدید خواهد آمد: وسط|قاب پیمایش یک درخت نخی به روش میانوندی غیر بازگشتی الگوریتم گره جاری را بررسی کنید و ببینید آیا فرزند سمت چپی دارد که در لیست گره‌های ملاقات شده وجود نداشته باشد؟ | ## بخش 3: درخت دودویی نخی | فرزند چپ را به لیست گره‌های ملاقات شده اضافه کنید و آن را گره فعلی خود در نظر بگیرید. اگر گره دیگری وجود دارد به مرحله یک بروید، در غیر این صورت خارج شوید؛ درخت پیمایش شده‌است. حال درخت زیر را در نظر بگیرید: قاب|وسط Liمرحله اول'A' گره سمت چپی به نام B دارد که هنوز ملاقات نشده‌است، بنابرایت ما B را به «لیست گره‌های ملاقات شده اضافه می‌کنیم و سپس B را گره جاری خود در نظر می‌گیریم. بنابراین D را به لیست خود اضافه کرده و آن را گره جاری خود فرض می‌کنیم.B Dمرحله ۳'D فرزند چپ ندارد، بنابراین ما D را چاپ می‌کنیم. بنابراین ما B را گره جاری خود فرض می‌کنیم.B DDمرحله ۴'B یقیناً یک فرزند چپ دارد، اما ما قبلاً آن را به لیست گره‌های ملاقات شده اضافه کرده‌ایم. بنابراین ما اتصال نخ آن را دنبال می‌کنیم و به گره A می‌رسیم و سپس A را گره جاری خود فرض می‌کنیم.B DD Bمرحله ۵'A یک فرزند چپ دارد که قبلاً ملاقات شده‌است. | ## جمع‌بندی | سپس ما فرزند راست آن را بررسی می‌کنیم که C است و هنوز در لیست گره‌های ملاقات شده وجود ندارد.