درخت ریشهدار
در نظریهٔ گراف، یک درخت ریشهدار (به انگلیسی: rooted tree) به درختی گفته میشود که یک رأس در آن به عنوان ریشه برچسب خورده باشد. درخت ریشهدار یک ساختار داده کلیدی در علوم کامپیوتر است.
![](http://upload.wikimedia.org/wikipedia/fa/thumb/5/58/Tree3.png/200px-Tree3.png)
رأسهایی که به طور مستقیم به رأس دیگری متصل اند بچههای آن نامیده میشوند. مثلاً در شکل بالا و بچههای هستند و پدر آنهاست. همچنین اگر یک رأس بچهای نداشته باشند به آن برگ میگویند.(مانند گره )
چند نمونه از درخت ریشهدار: درخت جستجوی دودویی، درخت قرمز و سیاه، درخت مبنایی
تعداد درختهای ریشه دار با رأس بر اساس دنباله روبرو است: ۱, ۱, ۲, ۴, ۹, ۲۰, ۴۸, ۱۱۵, ۲۸۶, ۷۱۹, ۱۸۴۲, ۴۷۶۶,...[۱]
مثالهایی از استعمال
ویرایشفایل سیستمها درختهای ریشه دار هستند. برای نمونه درایو در کامپیوتر یک ریشه است. در این درخت ریشه دار فایلها و پوشهها رأسها هستند. این رأسها توسط لینکهایی در هارد مشخص میشوند.
پانویس
ویرایش- ↑ Weisstein, Eric W. "Rooted Tree". mathworld.wolfram.com (به انگلیسی). Retrieved 2023-12-16.