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

[roberty]

سلام به همگی
استاد ساختمان داده ما یه سوال داده بود که برای یک گره معلوم از درخت پدر آن گره رو به دو روش بازگشتی و غیر بازگشتی پیدا کنید.
برای روش بازگشتی که یه تابع parent معرفی میشه و با استفاده از همین تابع میشه پدر رو پیدا کرد ولی برای روش غیر بازگشتی مشکل پیاده سازی تابع parent هست که بنده هرچی به مخم فشار میارم نمیتونم با ابزار هایی مثل فرزند چپ و فرزند راست یا همون LC و RC و یا حتی ریشه درخت T پدر یک گره رو پیدا کنم.

قصد بنده این نیست که برام برنامه اش رو بنویسید. فقط میخوام بدونم الگوریتم اجرای اینکار چجوری هست.
بی نهایت ممنونم:لبخندساده:

[sanaz e]

براي پياده سازي درخت از چي استفاده مي كني؟ آرايه يا ليست پيوندي ....؟

[roberty]

براي پياده سازي درخت از چي استفاده مي كني؟ آرايه يا ليست پيوندي ....؟
از لیست پیوندی !!:لبخند:

ممنون

[pesar irooni]

باید از استک استفاده کنی . در مورد بازگشتی سیتم بطور خودکار خودش از استک استفاده میکنه.
اگه بری پیمایش درخت بصورت غیربازگشتی یا همون تکراری رو بخونی که تو همه کتابای ساختمان داده هست همه جی میاد دستت. (ضمنا اگه بخوای از استک استفاده نکنی میتونی از نخ استفاده کنی)

[roberty]

باید از استک استفاده کنی . در مورد بازگشتی سیتم بطور خودکار خودش از استک استفاده میکنه.
اگه بری پیمایش درخت بصورت غیربازگشتی یا همون تکراری رو بخونی که تو همه کتابای ساختمان داده هست همه جی میاد دستت. (ضمنا اگه بخوای از استک استفاده نکنی میتونی از نخ استفاده کنی)

یعنی طبق قانون lifo برای استک اولین گره که ریشه هست رو باید وارد استک کنیم و بعد فرزندان ریشه و موقع pup کردن پدر رو بدست بیاریم یا اینکه کار دیگه ای باید انجام بشه؟

[pesar irooni]

بستگی به نوع پیمایش شما داره. اما اینجا شما میخوای پدر یک گره رو پیدا کنی پس فکر کنم اینطور که میگم خوب باشه: شما ریشه رو با گره ات مقایسه میکنی که اگه برابر باشه پس پدر نداره(آخه). بعد فرزندان ریشه رو با گره ات مقایسه میکنی که اگه برابر بود پدر میشه ریشه و اگه نبود شما باید همین کار رو با یکی از فرزندان به عنوان ریشه تکرار کنی. فرض میکنیم (طبق preOrder) شما میخوای اول تمام فرزندان سمت چپ ریشه مقایسه بشند. اینجا میای و فرزند سمت راست رو به استک پوش میکنی و بعد root رو برابر فرزند سمت چپ قرار میدی و همین کار رو تکرار میکنی تا یا گره ات پیدا بشه و یا دیگه ریشه فرزند چپ نداشته باشه. شما تو این مسیر هرچی فرزند راست بوده تو استک پوش کردی. حالا بالاترین عنصر استک رو که یک از فرزندای سمت راست تو مسیر بوده پاپ میکنی و کارت رو با اون عنوان ریشه به همین سبک تکرار میکنی تا یا عنصرت پیدا بشه و یا استک خالی بشه و دیگه فرزند چپی هم نداشته باشیم (که این حالت زمانی اتفاق میفته که اصلا اون عنصر متعلق به درخت نبوده باشه)

[minaaa68]

سلام به همگی
تابع پیدا کردن parent رو به دو روش بازگشتی و غیر بازگشتی می خواستم.
اگر این کد رو یعنی پیدا کردن پدر اصلی از طریق یکی از فرزندان رو می دونید ، کمکم کنید