۱- تو یه درخت باینری با n گره تو چه حالتی اولین گره تو پیمایش postorder مشابه با آخرین گره تو پیمایش inorder میشه؟
سوال ۹۵ سال ۸۵ علوم هست.
اولین گره پسوندی قراره برابر آخرین گره میانوندی بشه :
LRV
LVR
قرمزا باید برابر شوند. با مثال زدن متوجه میشید هر درختی غیر از مورب راست و چپ نمیتونه به این حالت برسه. (که این درختا ارتفاعی برابر ارتفاع n-1 دارند) حالا چرا
یه مورب راست از نوع bst هیچ گرهی در سمت چپ نداره پس توی پیمایش LRV هیچ L نخواهید دید و به نوعی پیمایش اینجوری خلاصه میشه : RV
به همین ترتیب وقتی درخت مورب راست LVR پیمایش میشه,پیمایشش خلاصه میشه به VR
میبینید که آخر پیمایش میانترتیب (راست ترین گره درخت) و اول پیمایش پسترتیب (باز هم راست ترین گره درخت) یکسان در اومدن.
برای مورب چپ خودتون اثبات کنید که چرا. (ی شکل ساده با گره های محدود رو پیمایش کنید ) مشکلی بود حتما بپرسید