در یک درخت باینری T با n گره در چه حالتی گره در اولین پیمایش post order مشابه آخرین گره در پیمایش inorder است؟
۱) زیر درخت چپ T خالی باشد.
۲) T دارای ارتفاع n-1 باشد.
۳) زیر درخت راست T خالی باشد.
۴) T حداکثر سه گره داشته باشد.
دوستان برای این سوال من سه تا پاسخ متفاوت توی سه تا کتاب دیدم! دیگه به خودم و جوابم هم شک کردم
گفتم دوستان یه نظری بدن.یه جا گزینه ۱ رو زده بود درست که نظر منم همین گزینه هست.
یه کتاب دیگه گزینه ۲ رو کلید زده بود!!!!
کتاب سوم هم گفته بود گزینه صحیح وجود ندارد!!!!!
قضیه چیه؟!
ممنون.موفق باشید
سلام دوباره.
ببین این سوالا رو باید مثال بزنی واسه خودت و سعی کنی مثال نقض پیدا کنی.
جواب درست گزینه ۱ هست و غلط بودن بقیه با مثال نقض اثبات میشه.
یه درخت مورب راست بکش(زیر درخت چپ خالیه) و بعد postorder و inorder رو روش انجام بده. میبینی که درست جواب میده. مثلا ریشه رو بزار a فرزند راستش b و فرزند راست b هم c.
در اینصورت پیمایش postorder به شکل cba میشه و inorder به شکل abc. میبینیم که اولین گره پیمایش شده در postorder برابره با اخرین گره پیمایش شده در inorder.
برای بقیه هم مثال نقض میشه آورد.
Sent from my Google Galaxy Nexus using Tapatalk 2.4
آقای یوسفی تو کتابشون گفتند حالت اول هم مثال نقض داره
a ریشه باشه و b فرزند راستش و c فرزند چپ b
که در این حالت زیردرخت چپ خالیه. ولی شرایط برقرار نیست.
post : CBA
in : ACB
که اولین گره در post با آخرین گره در in برابر نیست.
دقت کنید که آخرین گره در post و اولین گره در in مثل همن ولی سوال این رو نمی خواد.
اگه اشتباه می کنم بگید.
@egm1176
به نظرم درسته! تو گزینه ها باید به جای اینا مینوشت که درخت مورب چپ یا راست باشه ممکنه یا نه؟؟!!
یعنی گزینه صحیح وجود نداره دیگه؟
آقا امیر نظر شما چیه؟؟
سارا جان موافقم باهات.
باید میزد درخت مورب.
Sent from my Google Galaxy Nexus using Tapatalk 2.4
گزینه ی ۳ درست است.
![[تصویر: 1.gif]](https://img.manesht.ir/1.gif)
در گزینه ی ۱ حالات پیشوندی و میانوندی یکسان اند.
(۱۳ دى ۱۳۹۱ ۰۱:۳۹ ب.ظ)Amir V نوشته شده توسط: سلام دوباره.
ببین این سوالا رو باید مثال بزنی واسه خودت و سعی کنی مثال نقض پیدا کنی.
جواب درست گزینه ۱ هست و غلط بودن بقیه با مثال نقض اثبات میشه.
یه درخت مورب راست بکش(زیر درخت چپ خالیه) و بعد postorder و inorder رو روش انجام بده. میبینی که درست جواب میده. مثلا ریشه رو بزار a فرزند راستش b و فرزند راست b هم c.
در اینصورت پیمایش postorder به شکل cba میشه و inorder به شکل abc. میبینیم که اولین گره پیمایش شده در postorder برابره با اخرین گره پیمایش شده در inorder.
برای بقیه هم مثال نقض میشه آورد.
Sent from my Google Galaxy Nexus using Tapatalk 2.4
منظور این سوال از زیردرخت چپ یا راست T چیه؟ منظورش برای ریشه است؟ چون زیردرخت چپ و راست برای هر گره ای قابل تعریفه.
دوست عزیز (mahdi) شما اشتباه می کنید .
خودتون یه درخت مورب راست بکش . می بینی postorder و inorder با هم فرق می کنه:
مثال :
ABC
postorder میشه :
CBA
و inorder میشه :
ABC
که با هم فرق داره
------
همون ۳ درسته. بنده هم امتحان کردم.دقت بفرمایید.
(۱۴ بهمن ۱۳۹۱ ۰۳:۲۷ ق.ظ)csharpisatechnology نوشته شده توسط: دوست عزیز (mahdi) شما اشتباه می کنید .
خودتون یه درخت مورب راست بکش . می بینی postorder و inorder با هم فرق می کنه:
مثال :
ABC
postorder میشه :
CBA
و inorder میشه :
ABC
که با هم فرق داره
------
همون ۳ درسته. بنده هم امتحان کردم.دقت بفرمایید.
بله postorder با inorder فرق می کنه در درخت مورب راست. سوال گفته
"گره در اولین پیمایش post order مشابه آخرین گره در پیمایش inorder"
یعنی گره اول و آخرو مقایسه کرده
سه که قطعا نیست
بهترین جواب گزینه ی ۲ هستش منظور سوال و طراح هم این بوده که درخت مورب چپ باشه هرچند حالت ۲ هم به طور کلی نادرسته