سورس پروژه درخت جستجوی دودویی به زبان سی شارپ

سورس پروژه درخت جستجوی دودویی به زبان سی شارپ

Binary search tree in C sharp

درخت جستجوی دودویی یا BST و یا Binary search tree که به آن درخت دودویی مرتب هم می گویند، یک ساختار داده می باشد و یک نوع درخت دودویی محسوب می شود که ممکن است تهی نیز باشد.

عملیات ذکر شده در زیر بر روی یک درخت جستجوی دودویی تعریف می ‌شود: ایجاد یک درخت جستجوی خالی، تست خالی بودن درخت، درج یک کلید جدید در درخت، بدون برهم خوردن خاصیت درخت، پیدا کردن یک کلید خاص در درخت، حذف یک کلید از درخت با حفط خاصیت درخت، پیمایش درخت جستجوی دودویی به این صورت که همه ی گره‌ ها یک بار در دسترس قرار گیرند.

.

جستجوی یک عنصر در BST:

فرض کنید بخواهیم دنبال عنصری با کلید x بگردیم. ابتدا از ریشه شروع می کنیم. اگر ریشه تهی باشد، درخت جستجو فاقد هر عنصری بوده و جستجو ناموفق خواهد بود. در غیر این صورت x را با مقدار کلید ریشه مقایسه می کنیم. اگر x کمتر از مقدار کلید ریشه باشد، زیر درخت چپ را جستجو می کنیم. اگر x بزرگتر از مقدار کلید ریشه باشد آنگاه زیر درخت راست را جستجو می کنیم.