درخت دودویی نخی

دانشنامه عمومی

در یک درخت دودویی، تعداد اتصالات تهی، بیشتر از تعداد اتصالات غیرتهی است. در یک درخت دودویی از کل اتصالات یعنی 2n، تعداد n+1 اتصال تهی است. از این اتصالات تهی می توان برای ارتباط با دیگر گره های درخت استفاده کرد. در درختی که اتصالات تهی آن به این صورت استفاده شده است، درخت دودویی نخ کشی شده ( به انگلیسی: Threaded binary tree ) نامیده می شود. یک درخت دودویی را می توان به چند روش نخ کشی کرد. این نخ کشی بسته به روش پیمایش درخت دارد. برای مثال، درخت دودویی نخ کشی شده به روش میانوندی به شکل زیر تعریف می شود:
«برای هر گره، اتصال تهی سمت راست، به گره بعدی در پیمایش میانوندی اشاره کنند و اتصال تهی سمت چپ، به گره قبلی در پیمایش میانوندی اشاره کنند. »
درخت دودویی نخ کشی شده این امکان را فراهم می سازد که پیمایش مقادیر در درخت دودویی به روش پیمایش خطی، سریعتر از پیمایش بازگشتی درخت به صورت میانوندی صورت گیرد. همچنین پیدا کردن والد یک گره در یک درخت دودویی نخی، بدون استفاده از اشاره گرهای والد یا بدون استفاده از پشته هم امکان پذیر است، هر چند که این کار کمی آهسته است. این قابلیت وقتی مفید است که فضای پشته اندک باشد یا وقتی که پشته اشاره گرهای والد غیرقابل دسترس باشد. ( برای پیدا کردن گره والد به روش الگوریتم جستجوی عمق اول )
برای اینکه ببینیم این کار چگونه امکان پذیر است، گرهی به نام k را تصور کنید که یک فرزند سمت راست به نام r دارد. بنابراین اشاره گر سمت چپ r یا باید یک فرزند باشد یا یک اتصال نخی به k باشد. در مورد اول که r یک فرزند سمت چپ دارد، آن گره فرزند هم به نوبه خود یا باید یک فرزند سمت چپ داشته باشد یا باید اتصالی نخی به k باشد و به همین ترتیب این قضیه برای کلیه فرزندان سمت چپ صادق است. بنابراین با دنبال کردن زنجیره ای از اشاره گرهای سمت چپ گره r، ما بالاخره به گره k می رسیم. به شکل مشابه، اگر گرهی به نام p داشته باشیم که فرزند سمت چپ آن q است، با دنبال کردن زنجیره اشاره گرهای سمت راست q، بالاخره به p خواهیم رسید.
نخ ها نشانه روهایی به گره ماقبل و گره مابعد گره فعلی هستند. گره ماقبل و گره مابعد بستگی به پیمایش یک درخت دارد که معمولاً از پیمایش میانوندی استفاده می شود. پیمایش میانوندی یک درخت دودویی به صورت ABCDEFGHI است. ماقبل گره E، گره D است و مابعد آن گره F است.
عکس درخت دودویی نخیعکس درخت دودویی نخیعکس درخت دودویی نخیعکس درخت دودویی نخیعکس درخت دودویی نخی
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلف

پیشنهاد کاربران