[مهمان]

سلام

چطور می توانیم گره ای را در درخت جستجوی دودوی با دو زیر درخت هم چپ هم راست
را پاک کرد

در صورت امکان کد در c

لطفا کمک کنید دوستان کارم بدجور گیره

با تشکر

[Saied]

سلام دوست عزیز
این سوال به لینکس ربطی نداره ولی من به شما جواب می دم .
چندین الگاریتم برای این کار وجود داره . یکی از ساده ترین هاش استفاده از توابع بازگشتی یا recursion است . بدین ترتیب که شما مثلا یه تابع داری به نام deltree که یه گره می گیره و اونو با تمام بچه هاش پاک می کنه . خوب شما مسلما باید اول بچه های این نود ریشه رو از برگ ها به سمت بالا پاک کنی . بنابراین یه تابع دیگه می نویسی مثلا delchildren که این همون تابع بازگشتی مون است . تو این تابع اول خود همین تابع رو با دادن بچه های سمت چپ و راست صدا می کنی ( که اون ها هم در مورد بچه های خودشون این کار رو تکرار می کنن ) و بعد از ان دو بچه سمت راست و چپ همین نود خودت رو پاک می کنی . این کار باعث میشه که توابع بازگشتی که دارن بازگشت می کنن به صورت reverse بچه هاشون رو پاک کنن که همون مطلوب مساله است . شرط اتمام بازگشت رو هم این بذار که اگه اون نود بچه ای نداشت تابع تموم بشه .
این کار بر مبنا الگاریتم DFS یا همون depth first search است شما می تونی با یه for خیلی ساده و با استفاده از breath first search این کار رو انجام بدی ولی استفاده از توابع بازگشتی خیلی ساده تره .

[مهمان]

سلام
دوست عزیز من می خواهم نود را پاک کنم نه بچه هاشرو
به این صورت که نودی که می خواهم پاک کنم دارای 2 فرزند هست
و فقط نود پاک خواهد شد و بچه هاش باید در درخت بمانند

لطفا اگر امکان دارد کد این رو برام بفرستید

با تشکر

[Saied]

خوب این کار که خیلی ساده تره .
اگه اون نود بچه نداشت خیلی راحت حذف میشه . اگه یه بچه داشته باشه حذف میشه و اون بچه میاد جاش و اگه دوتا بچه داشته باشه چندین الگاریتم وجود داره یعنی میشه چند تا bst داشت . یکیش که من خودم معمولا این کار رو می کنم اینه که کوچکترین نود در زیر درخت راست نود اصلی رو پیدا کرده و حذفش می کنیم و میاریمش به جای نودی که قراره حذف بشه و همه چیز ok هست . شما می تونی همین کار رو با بزرگترین نود سمت چپ انجام بدی . این دو تا لینک رو یه نگاه بکنی بد نیست .
<!-- m --><a class="postlink" href="http://en.wikipedia.org/wiki/Binary_search_tree#Deletion">http://en.wikipedia.org/wiki/Binary_sea ... e#Deletion</a><!-- m -->
<!-- m --><a class="postlink" href="http://scitec.uwichill.edu.bb/cmp/online/CS20L/Backup/Powerpoint/CS20L-Lecture%20Set%2010%20-%20Binary%20Search%20Trees.ppt">http://scitec.uwichill.edu.bb/cmp/onlin ... 0Trees.ppt</a><!-- m -->
تو همون لینک اول کد پا یتن هست که می تونی به زبان مورد نظرت ترجمه کنی .

[Saied]

یه چیزی که یادم رفت بگم در مورد نا متوازن شدن BST است . ببین شما که پشت سر هم از درخت delete می کنی ممکنه درختت به یک array یا linked list تبدیل بشه و در نتیجه (O(logn رو در درختت از دست بدی . برای جلوگیری از این کار هم الگاریتم هایی وجود داره مثل AVL Tree که دیگه در موردش توضیحی نمی دم خودت برو جستجو کن .