صفحه‌ها: ۱ ۲
(۱۸ دى ۱۳۸۹ ۰۱:۱۴ ق.ظ)حامد نوشته شده توسط:(18 دى ۱۳۸۹ ۱۲:۱۷ ق.ظ)Maryam-X نوشته شده توسط: سلام
بروبچ یه سوال دیگه در باره‌ی این پیمایش ها:
اگر دو تا راس در پیمایش پیش ترتیب و پس ترتیب دقیقا به یک ترتیب بیایند اونوقت این معنیش چیه؟
مثل این:
g e j c b f i d a h
h f g b c e j a d i
e & j به یک ترتیب اومدند.
۲-الان اینجا چند تا گره‌ی تک فرزندی داریم؟
درخت رو که بکشید می توان به این نتیجه رسید که: هر وقت که دو برگ همزاد باشند( داری والد یکسان باشند) در پیمایش پیش ترتیب و پس ترتیب دقیقا به یک ترتیب می آیند.
۳ تا گره‌ی تک فرزندی دارید که با توجه به شکل b ,a و d می باشند.از اون فرمول که بروبچ گفتند هم می تونید استفاده کنید.cb=>bc.id=>di.da=>ad.
مرسی...
الان با توجه به گفته‌ی شما این درخت ما چند تا برگ داره؟
(۱۹ دى ۱۳۸۹ ۰۱:۰۸ ق.ظ)Maryam-X نوشته شده توسط: مرسی...سوالتون چه ربطی به گفته های من داشت؟
الان با توجه به گفته‌ی شما این درخت ما چند تا برگ داره؟
۴ تا برگ داریم:
g که فرزند چپ f هست.
e که فرزند چپ c هست.
j که فرزند راست c هست.
i که فرزند چپ یا راست d هست.
با توجه به گفته‌ی من تنها این نتیجه رو میتونید بگیرید که دو تا از برگهامون(e,j) والد یکسان دارند و بقیه برگها والد یکسان ندارند.
ممنون آقا حامد به خاطر جوابای خوبتون.
یک سوال:
آیا میتونیم بگیم که وقتی پس وپیش ترتیب رو داشتیم برای یافتن برگها:
۱/ببینیم کدوما عینا تکرار شدن اونا برگ با والد یکسانند.
۲/اولی تو پیمایش پس و آخری تو پیمایش پیش ترتیب برگند.
(۱۹ دى ۱۳۸۹ ۰۹:۴۱ ق.ظ)sepid نوشته شده توسط: ممنون آقا حامد به خاطر جوابای خوبتون.بله.جمله‌ی دومتون بصورت کاملتر میشه:اولی تو پیمایش پس ترتیب سمت چپ ترین برگ و آخری توی پیمایش پیش ترتیب سمت راست ترین برگ می باشد.
یک سوال:
آیا میتونیم بگیم که وقتی پس وپیش ترتیب رو داشتیم برای یافتن برگها:
۱/ببینیم کدوما عینا تکرار شدن اونا برگ با والد یکسانند.
۲/اولی تو پیمایش پس و آخری تو پیمایش پیش ترتیب برگند.
البته ممکن است برگهای دیگری نیز وجود داشته باشه که با این دو مورد که گفتید پیدا نشوند.
مثلا:
pre :hfgbcejkadi
post:gejckbfidah
الان k نیز برگ است ولی با استفاده از موارد بالا قابل تشخیص نیست.
(۱۹ دى ۱۳۸۹ ۰۱:۴۶ ب.ظ)حامد نوشته شده توسط:برای این سوال اگر اول تک فرزندی‌ها رو پیدا کنیم(a و d) بعد از پیمایش حذفشون می کنیم:(19 دى ۱۳۸۹ ۰۹:۴۱ ق.ظ)sepid نوشته شده توسط: ممنون آقا حامد به خاطر جوابای خوبتون.بله.جمله‌ی دومتون بصورت کاملتر میشه:اولی تو پیمایش پس ترتیب سمت چپ ترین برگ و آخری توی پیمایش پیش ترتیب سمت راست ترین برگ می باشد.
یک سوال:
آیا میتونیم بگیم که وقتی پس وپیش ترتیب رو داشتیم برای یافتن برگها:
۱/ببینیم کدوما عینا تکرار شدن اونا برگ با والد یکسانند.
۲/اولی تو پیمایش پس و آخری تو پیمایش پیش ترتیب برگند.
البته ممکن است برگهای دیگری نیز وجود داشته باشه که با این دو مورد که گفتید پیدا نشوند.
مثلا:
pre :hfgbcejkadi
post:gejckbfidah
الان k نیز برگ است ولی با استفاده از موارد بالا قابل تشخیص نیست.
pre:hfgbcejki
post:gejckbfih
i سمت راست ترین برگ و g سمت چپ ترین برگ هست(پس حالا یک محدوده برگ داریم) که h و f خارج از اون محدوده هست(یعنی دو فرزندی هستند) پس برای راحتی حذفشون می کنیم:
pre :gbcejki
post:gejckbi
در هر دو پیمایش ترتیب گره های gejki یکسانه پس برگ هستند. گره های b و c هم که نه تک فرزندی هستند ونه برگ، در نتیجه دو فرزندی هستند.
تک فرزندی: ۲
برگ:۵
دو فرزندی:۴
(بر اساس مثال صفحه ۱۴۱ کتاب پارسه)
درسته؟
(۲۴ دى ۱۳۸۹ ۰۹:۲۴ ق.ظ)**sara** نوشته شده توسط: برای این سوال اگر اول تک فرزندی‌ها رو پیدا کنیم(a و d) بعد از پیمایش حذفشون می کنیم:کتاب مورد نظر را ندارم.(جزوه چاپی سال قبل پارسه را دارم)
pre:hfgbcejki
post:gejckbfih
i سمت راست ترین برگ و g سمت چپ ترین برگ هست(پس حالا یک محدوده برگ داریم) که h و f خارج از اون محدوده هست(یعنی دو فرزندی هستند) پس برای راحتی حذفشون می کنیم:
pre :gbcejki
post:gejckbi
در هر دو پیمایش ترتیب گره های gejki یکسانه پس برگ هستند. گره های b و c هم که نه تک فرزندی هستند ونه برگ، در نتیجه دو فرزندی هستند.
تک فرزندی: ۲
برگ:۵
دو فرزندی:۴
(بر اساس مثال صفحه ۱۴۱ کتاب پارسه)
درسته؟
ایرادی در استدلالتون نمی بینم.
با توجه به اینکه رسم درخت خیلی خیلی ساده است هنوز دلیل اینکه دوستان بر این روشها تکیه دارند را نمی فهمم.احتمال انکه سوال تکراری آنهم در درسی مثل ساختمان داده به این شکل برای مهندسی کامپیوتر مطرح شود بسیار پایین است و منطقی‌تر این است که بر روی رسم درخت با استفاده از پیمایش‌ها مسلط شوید تا کشف جزییاتی که به راحتی با استفاده از رسم قابل دسترس می باشند.
سوال:باداشتن inorder یک درخت جستجوی دودویی چند درخت متفاوت می توان به دست آورد؟
مثال ساده:
inorder:5,12,14,17
(۲۴ دى ۱۳۸۹ ۰۱:۰۸ ب.ظ)حامد نوشته شده توسط:(24 دى ۱۳۸۹ ۰۹:۲۴ ق.ظ)**sara** نوشته شده توسط: برای این سوال اگر اول تک فرزندی‌ها رو پیدا کنیم(a و d) بعد از پیمایش حذفشون می کنیم:کتاب مورد نظر را ندارم.(جزوه چاپی سال قبل پارسه را دارم)
pre:hfgbcejki
post:gejckbfih
i سمت راست ترین برگ و g سمت چپ ترین برگ هست(پس حالا یک محدوده برگ داریم) که h و f خارج از اون محدوده هست(یعنی دو فرزندی هستند) پس برای راحتی حذفشون می کنیم:
pre :gbcejki
post:gejckbi
در هر دو پیمایش ترتیب گره های gejki یکسانه پس برگ هستند. گره های b و c هم که نه تک فرزندی هستند ونه برگ، در نتیجه دو فرزندی هستند.
تک فرزندی: ۲
برگ:۵
دو فرزندی:۴
(بر اساس مثال صفحه ۱۴۱ کتاب پارسه)
درسته؟
ایرادی در استدلالتون نمی بینم.
با توجه به اینکه رسم درخت خیلی خیلی ساده است هنوز دلیل اینکه دوستان بر این روشها تکیه دارند را نمی فهمم.احتمال انکه سوال تکراری آنهم در درسی مثل ساختمان داده به این شکل برای مهندسی کامپیوتر مطرح شود بسیار پایین است و منطقی‌تر این است که بر روی رسم درخت با استفاده از پیمایش‌ها مسلط شوید تا کشف جزییاتی که به راحتی با استفاده از رسم قابل دسترس می باشند.
با حامد موافقم توی همین امتحان آخر تسلط سازمان سنجش اومده بود و تعداد برگها رو میخواست منم توی ۱ دقیقه درخت رو کشیدم و جواب رو بدست اوردم کلا کشیدن درخت بهتره
(۲۵ دى ۱۳۸۹ ۰۱:۰۱ ق.ظ)Maryam-X نوشته شده توسط: سوال:باداشتن inorder یک درخت جستجوی دودویی چند درخت متفاوت می توان به دست آورد؟
مثال ساده:
inorder:5,12,14,17
جواب میشه عدد کاتالان چون این درختا وجه تمایزشون فقط شکلشونه چرا که برای هر شکل خاص فقط وفقط یک حالت برچسب گذاری وجود داره پس میشه:۱۴
(۲۳ آذر ۱۳۸۹ ۰۸:۲۰ ب.ظ)حامد نوشته شده توسط: من که کمتر از ۱ دقیقه شکلشو کشیدم.و با توجه به اینکه می دونم توی این حالت جواب رد خور نداره خیلی بهتر از حفظ کردن فرموله.اینم شکلش(که یکی از حالتهای شکلش می باشد با توجه به اینکه تک فرزندی‌ها رو می تونید چپ یا راست والدشون بدید شکلهای متفاوتی ایجاد میشه):
خیلی راحت طراح می تونه سوال رو طوری عوض کنه که اون فرمول اصلا بدردتون نخوره!
میشه لطفا توضیح بدی این درخت رو چه طور از روی پیمایش postorder و preorder رسم کردی!من تا یه جاهایی می تونم رسمش کنم ولی بعدش دچار مشکل می شم...
منظورم این درخت بود...
preorder: a b d e f g c h i j
post order
g f e b i j h c a(۲۶ دى ۱۳۸۹ ۱۱:۲۰ ق.ظ)sani نوشته شده توسط: میشه لطفا توضیح بدی این درخت رو چه طور از روی پیمایش postorder و preorder رسم کردی!من تا یه جاهایی می تونم رسمش کنم ولی بعدش دچار مشکل می شم...روش خاصی نداره که توضیح بدم.فقط باید تمرین کنید و پیمایش‌ها رو خوب درک کرده باشید.پیش ترتیب رو از چپ به راست بهش نگاه میکنیم و همزمان پس ترتیب را از راست به چپ.
منظورم این درخت بود...
preorder: a b d e f g c h i j
post order
من در جریان نوشته های این پست نیستم، فقط این آخری رو خوندم! اگه منظورتون رو درست فهمیده باشم باید دنبال یه همچین چیزی بگردید!
postorder: T1post T2post
preorder: r T1pre T2pre
اگه این دو تا پیمایش رو داشته باشیم به شرط این که درخت کامل باشه میشه به صورت زیر عمل کرد:
postorder: T1post T2postx r
preorder: r T1pre xT2pre
یعنی توی نمایش postorder، دومین گره ریشه‌ی زیر درخت سمت راست r هست و با توجه به نمایش preorder میشه گره های زیر درخت چپ و راست رو به دست آورد (چون مرزشون یعنی x پیدا شده) و به همین صورت به بازگشتی حل میشه!
امیدوارم تونسته باشم منظورم رو برسونم ...
(۲۶ دى ۱۳۸۹ ۰۵:۰۷ ب.ظ)۵۴m4n3h نوشته شده توسط: من در جریان نوشته های این پست نیستم، فقط این آخری رو خوندم! اگه منظورتون رو درست فهمیده باشم باید دنبال یه همچین چیزی بگردید!
postorder: T1post T2post
preorder: r T1pre T2pre
اگه این دو تا پیمایش رو داشته باشیم به شرط این که درخت کامل باشه میشه به صورت زیر عمل کرد:
postorder: T1post T2postx r
preorder: r T1pre xT2pre
یعنی توی نمایش postorder، دومین گره ریشه‌ی زیر درخت سمت راست r هست و با توجه به نمایش preorder میشه گره های زیر درخت چپ و راست رو به دست آورد (چون مرزشون یعنی x پیدا شده) و به همین صورت به بازگشتی حل میشه!
امیدوارم تونسته باشم منظورم رو برسونم ...
اوه...یک دنیا ممنون...این روش واقعا خوب عمل می کنه!
روی چند تا درخت دیگه هم امتحان کردم و در کمال ناباوری تونستم درختش رو بکشم! البته بازم باید بررسی کنم تا ببینم مشکلی هست یا نه!
فکر کنم اون شرط کامل بودن به خاطر اینکه درخت منحصر به فرد باشه! ولی خوب ما که درختمون منحصر به فرد نیست،مشکلی پیش نمی یاد.
سوال جدید = تاپیک جدید + عنوان کامل و صحیح