پیمایش inorder جنگل و inorder درخت دودویی متناظر با آن یکسان هست؟
دو تا تست از کتاب پروران پژوهش هست که دو تا جواب متفاوت داده. کتاب ساختمان داده یوسفی سوال ۴۳ و ۵۸ فصل ششم.
نقل قول: پیمایش inorder جنگل و inorder درخت دودویی متناظر با آن یکسان هست؟
دوست عزیز، بله، طبق فصل پنجم کتاب "ساختمان داده - هورویتز"، پیمایش Inorder مربوط به جنگل با پیمایش Inorder مربوط به درخت دودویی متناظر با آن یکسان است. البته این قضیه برای پیمایش Preorder هم صدق خواهد کرد ولی لزوما برای پیمایش Postorder نتیجه یکسانی تولید نخواهد شد.
سلام
بله یکسان است ،کتاب مقسمی صفحه ۲۳۲ نکته ۱
سلام .متاسفانه طبق نظر استاد یوسفی منابع اصلی دو مدل بحث کرده اند. بعضی پیمایش in جنگل را مسقل انجام می دهند که ربطی به پیمایش in درخت دودیی حاصل ندارد . ولی بعضی ابتدا درخت را دودویی می کنند و سپس ان را in پیمایش می کنند. ایشان در کلاس فرمودند که باید در صورت سوال ذکر شود .
کلا غیر POSTORDER باقی پیمایشها مثل همه
توی کتاب پوران(چاپ قدیم - جدید رو نمیدونم )خیلی بد گفته اما توی هورویتز یادمه قبلا دیده بودمش .
تا جاییکه میدونم توی کتاب ساختمان چاپ ۸۹ پوران (مهندس یوسفی) گفته شده که: پیمایش postorder جنگل با پیمایش Inorder درخت دودویی حاصل یکسانه.
والبته در تستهاش هم این نکته ذکر شده که: برای یافتن inorder یک جنگل inorder درخت دودویی معادل رو بیابیم.
(۰۸ دى ۱۳۹۰ ۱۲:۲۹ ق.ظ)Eternal8620 نوشته شده توسط: تا جاییکه میدونم توی کتاب ساختمان چاپ ۸۹ پوران (مهندس یوسفی) گفته شده که: پیمایش postorder جنگل با پیمایش Inorder درخت دودویی حاصل یکسانه.فکر نمیکنما
والبته در تستهاش هم این نکته ذکر شده که: برای یافتن inorder یک جنگل inorder درخت دودویی معادل رو بیابیم.
پیماش POST ORDER درخت عبارت، حاصلش پیمایش فرم پسوندیه( شاید با این قاطی کرده باشید )
(۰۸ دى ۱۳۹۰ ۱۲:۳۵ ق.ظ)Masoud05 نوشته شده توسط: فکر نمیکنمامن عین عبارت کتاب رو نقل کردم.(کتاب چاپ ۸۹- پوران - یوسفی - صفحه‌ی ۱۶۷)
پیماش POST ORDER درخت عبارت، حاصلش پیمایش فرم پسوندیه( شاید با این قاطی کرده باشید )
در ضمن منظورتون رو متوجه نشدم!من این نکته رو گفتم که "پیمایش postorder جنگل با پیمایش Inorder درخت دودویی حاصل یکسانه" که البته خودم روی چندتا مثال تست کردم جواب درست میده.
(۰۸ دى ۱۳۹۰ ۰۱:۳۶ ق.ظ)Eternal8620 نوشته شده توسط:(08 دى ۱۳۹۰ ۱۲:۳۵ ق.ظ)Masoud05 نوشته شده توسط: فکر نمیکنمامن عین عبارت کتاب رو نقل کردم.(کتاب چاپ ۸۹- پوران - یوسفی - صفحه‌ی ۱۶۷)
پیماش POST ORDER درخت عبارت، حاصلش پیمایش فرم پسوندیه( شاید با این قاطی کرده باشید )
در ضمن منظورتون رو متوجه نشدم!من این نکته رو گفتم که "پیمایش postorder جنگل با پیمایش Inorder درخت دودویی حاصل یکسانه" که البته خودم روی چندتا مثال تست کردم جواب درست میده.
فکر کنم روی درخت دودویی معادل جنگل منظورتون هست دیگه؟ یعنی اول جنگل رو به درخت دودویی تبدیل کردید؟
حالا بدون تبدیل از قوانین Inorder , pre , post order برید ببینید چی میبینید.
(۰۸ دى ۱۳۹۰ ۰۱:۳۸ ق.ظ)Masoud05 نوشته شده توسط: فکر کنم روی درخت دودویی معادل جنگل منظورتون هست دیگه؟ یعنی اول جنگل رو به درخت دودویی تبدیل کردید؟بله، منظورم درخت دودویی معادل جنگله.
حالا بدون تبدیل از قوانین Inorder , pre , post order برید ببینید چی میبینید.
خوب صورت سوال این تاپیک هم همینه "پیمایش inorder جنگل و inorder درخت دودویی متناظر با آن یکسان هست؟ "و پاسخ من هم اینه که اگه یه جنگل رو پیمایش postorder کنیم و سپس همان جنگل رو به درخت دودویی تبدیل کنیم و بعد اون درخت دودویی حاصل رو Inorder پیمایش کنیم این دو پیمایش با هم برابرند.
همچنین اگه قصد داشته باشیم پیمایش Inorder یک جنگل رو داشته باشیم می تونیم درخت دودویی متناظرش رو پیمایش Inorder کنیم.
بله اما بحث داشت به سمت کلیات میرفت ومنم بطور کلی گفتم .
(۰۸ دى ۱۳۹۰ ۰۱:۵۹ ق.ظ)Masoud05 نوشته شده توسط: بله اما بحث داشت به سمت کلیات میرفت ومنم بطور کلی گفتم .خدا رو شکر که مسئله حل شد!