15 آبان 1393, 10:10 ق.ظ
17 آبان 1393, 12:28 ق.ظ
سوال 95 سال 85 علوم هست.
اولین گره پسوندی قراره برابر آخرین گره میانوندی بشه :
LRV
LVR
قرمزا باید برابر شوند. با مثال زدن متوجه میشید هر درختی غیر از مورب راست و چپ نمیتونه به این حالت برسه. (که این درختا ارتفاعی برابر ارتفاع n-1 دارند) حالا چرا
یه مورب راست از نوع bst هیچ گرهی در سمت چپ نداره پس توی پیمایش LRV هیچ L نخواهید دید و به نوعی پیمایش اینجوری خلاصه میشه : RV
به همین ترتیب وقتی درخت مورب راست LVR پیمایش میشه,پیمایشش خلاصه میشه به VR
میبینید که آخر پیمایش میانترتیب (راست ترین گره درخت) و اول پیمایش پسترتیب (باز هم راست ترین گره درخت) یکسان در اومدن.
برای مورب چپ خودتون اثبات کنید که چرا. (ی شکل ساده با گره های محدود رو پیمایش کنید ) مشکلی بود حتما بپرسید
اولین گره پسوندی قراره برابر آخرین گره میانوندی بشه :
LRV
LVR
قرمزا باید برابر شوند. با مثال زدن متوجه میشید هر درختی غیر از مورب راست و چپ نمیتونه به این حالت برسه. (که این درختا ارتفاعی برابر ارتفاع n-1 دارند) حالا چرا
یه مورب راست از نوع bst هیچ گرهی در سمت چپ نداره پس توی پیمایش LRV هیچ L نخواهید دید و به نوعی پیمایش اینجوری خلاصه میشه : RV
به همین ترتیب وقتی درخت مورب راست LVR پیمایش میشه,پیمایشش خلاصه میشه به VR
میبینید که آخر پیمایش میانترتیب (راست ترین گره درخت) و اول پیمایش پسترتیب (باز هم راست ترین گره درخت) یکسان در اومدن.
برای مورب چپ خودتون اثبات کنید که چرا. (ی شکل ساده با گره های محدود رو پیمایش کنید ) مشکلی بود حتما بپرسید