سلام
کسی میتونه این سوالو کامل برام توضیح بده
اینکه چه طور همه درختاشو بدس بیارم؟
(۰۴ دى ۱۳۹۱ ۱۱:۰۹ ب.ظ)fas نوشته شده توسط: سلام
کسی میتونه این سوالو کامل برام توضیح بده
اینکه چه طور همه درختاشو بدس بیارم؟
سلام
ببین دوست عزیز اگر پیمایش postorder و preorder یه درخت رو به ما بدن در صورتی میتونیم به صورت یکتا اونو رسم کنیم که گره تک فرزندی نداشته باشه وگرنه به اندازه "دو به توان تعداد گره های تک فرزندی" میتونیم درخت رسم کنیم. خوب شاید سوال پیش بیاد که از کجا بفهمیم که چند تا گره تک فرزندی داره ؟ روش کار به این شکله که اگر مثلآ تو پیمایش preorder داشته باشیم de و در پیمایش postorder داشته باشیم ed این یگ گره تک فرزندی است. از آنجایی که تو این تست سه تا گره تک فرزندی داریم :
de and ed
fg and gf
hi and ih
در نتیجه ما سه تا گره تک فرزندی داریم و طبق قضیه بالا دو به توان تعداد گره های تک فرزندی (۳) -----> 8 درخت متفاوت میتونیم بکشیم.