سلام دوستان، ابتدا ممنون بابت وقتی برای خوندن این تاپیک می گذارید
من روشی رو که در حل این سوال اومده تست کردم اما نفهمیدم بلاخره زیر درخت پر Tبا بیشترین عناصر رو چه جوری به دست آورد و چرا مرتبه اش شد n؟(یعنی چون فقط یک بار همه گره ها رو چک کرد شد n)(تو رو خدا اگه خیلی دیر می گیرم بهم نخندین
)
من از یه روش دیگه استفاده کردم. این کدم الان خودم نوشتم. واقعا توضیحش طولانیه. امیدوارم واضح باشه به اندازه ی کافی. رابطه ی بازگشتی این کد میشه [tex]T(n) = 2T(n/2) 1[/tex] ; که از [tex]o(n)[/tex] هست
کد:
f(Tree T , int depth)
{
if( leaf(T) )
return (1, T);
ret1 = f ( T->left , depth + 1 );
ret2 = f ( T->right , depth + 1 );
if ( ret1.Tree == T->left and ret2.Tree == T->right )
{
if( ret1.depth == ret2.depth )
return ( ret1.depth + 1 , T );
elseif( | ret1.depth - ret2.depth | = 1 )
return ( min(ret1.depth, ret2.depth) + 1 , T);
else
return max ( ret1 , ret2 ) ; // max depth haro moghayese mikone
}
else
{
if( ret1.depth >= ret2.depth )
return ret1;
return ret2;
}
}بی نهایت سپاس از انرژی و زمانی که صرف کردین، دارم سعی می کنم بفهمم که بلاخره کجاش داره به ما یه درخت پر با بیشترین گره رو برمی گردونه، بازهم ممنون که در این زمان اندک برای پاسخ گویی زمان گذاشتین
فقط اینو در نظر داشته باش که خروجی تابع آدرس ریشه درخت پر به همراه ارتفاع درخته. یه structure در نظرش بگیر. من برای سادگی اینجوری نوشتم.
Thanks
الان خیلی برام واضح تر شد، یک دنیا ممنون، و از خدا می خوام که امسال هر جایی دوست دارید قبول بشید
(۱۷ بهمن ۱۳۹۱ ۰۱:۵۳ ب.ظ)fa_karoon نوشته شده توسط: Thanksخواهش میکنم. ممنونم ازتون . ایشالا شما هم موفق باشید.
الان خیلی برام واضح تر شد، یک دنیا ممنون، و از خدا می خوام که امسال هر جایی دوست دارید قبول بشید