تالار گفتمان مانشت

پیمایش inorder جنگل و inorder درخت دودویی متناظر با آن یکسان هست؟

دو تا تست از کتاب پروران پژوهش هست که دو تا جواب متفاوت داده. کتاب ساختمان داده یوسفی سوال ۴۳ و ۵۸ فصل ششم.

نقل قول: پیمایش inorder جنگل و inorder درخت دودویی متناظر با آن یکسان هست؟

دوست عزیز، بله، طبق فصل پنجم کتاب "ساختمان داده - هورویتز"، پیمایش Inorder مربوط به جنگل با پیمایش Inorder مربوط به درخت دودویی متناظر با آن یکسان است. البته این قضیه برای پیمایش Preorder هم صدق خواهد کرد ولی لزوما برای پیمایش Postorder نتیجه یکسانی تولید نخواهد شد.

سلام
بله یکسان است ،کتاب مقسمی صفحه 232 نکته 1

سلام .متاسفانه طبق نظر استاد یوسفی منابع اصلی دو مدل بحث کرده اند. بعضی پیمایش in جنگل را مسقل انجام می دهند که ربطی به پیمایش in درخت دودیی حاصل ندارد . ولی بعضی ابتدا درخت را دودویی می کنند و سپس ان را in پیمایش می کنند. ایشان در کلاس فرمودند که باید در صورت سوال ذکر شود .

کلا غیر POSTORDER باقی پیمایشها مثل همه
توی کتاب پوران(چاپ قدیم - جدید رو نمیدونم )خیلی بد گفته اما توی هورویتز یادمه قبلا دیده بودمش .

تا جاییکه میدونم توی کتاب ساختمان چاپ 89 پوران (مهندس یوسفی) گفته شده که‌: پیمایش postorder جنگل با پیمایش Inorder درخت دودویی حاصل یکسانه.
والبته در تستهاش هم این نکته ذکر شده که‌: برای یافتن inorder یک جنگل inorder درخت دودویی معادل رو بیابیم.

(08 دى 1390 12:29 ق.ظ)Eternal8620 نوشته شده توسط: [ -> ]تا جاییکه میدونم توی کتاب ساختمان چاپ ۸۹ پوران (مهندس یوسفی) گفته شده که‌: پیمایش postorder جنگل با پیمایش Inorder درخت دودویی حاصل یکسانه.
والبته در تستهاش هم این نکته ذکر شده که‌: برای یافتن inorder یک جنگل inorder درخت دودویی معادل رو بیابیم.

فکر نمیکنما

پیماش POST ORDER درخت عبارت‌، حاصلش پیمایش فرم پسوندیه( شاید با این قاطی کرده باشید )

(08 دى 1390 12:35 ق.ظ)Masoud05 نوشته شده توسط: [ -> ]فکر نمیکنما
پیماش POST ORDER درخت عبارت‌، حاصلش پیمایش فرم پسوندیه( شاید با این قاطی کرده باشید )

من عین عبارت کتاب رو نقل کردم.(کتاب چاپ ۸۹- پوران - یوسفی - صفحه‌ی ۱۶۷)
در ضمن منظورتون رو متوجه نشدم!من این نکته رو گفتم که "پیمایش postorder جنگل با پیمایش Inorder درخت دودویی حاصل یکسانه" که البته خودم روی چندتا مثال تست کردم جواب درست میده.

(08 دى 1390 01:36 ق.ظ)Eternal8620 نوشته شده توسط: [ -> ]

(08 دى 1390 12:35 ق.ظ)Masoud05 نوشته شده توسط: [ -> ]فکر نمیکنما
پیماش POST ORDER درخت عبارت‌، حاصلش پیمایش فرم پسوندیه( شاید با این قاطی کرده باشید )

من عین عبارت کتاب رو نقل کردم.(کتاب چاپ ۸۹- پوران - یوسفی - صفحه‌ی ۱۶۷)
در ضمن منظورتون رو متوجه نشدم!من این نکته رو گفتم که "پیمایش postorder جنگل با پیمایش Inorder درخت دودویی حاصل یکسانه" که البته خودم روی چندتا مثال تست کردم جواب درست میده.

فکر کنم روی درخت دودویی معادل جنگل منظورتون هست دیگه؟ یعنی اول جنگل رو به درخت دودویی تبدیل کردید؟
حالا بدون تبدیل از قوانین Inorder , pre , post order برید ببینید چی میبینید.

(08 دى 1390 01:38 ق.ظ)Masoud05 نوشته شده توسط: [ -> ]فکر کنم روی درخت دودویی معادل جنگل منظورتون هست دیگه؟ یعنی اول جنگل رو به درخت دودویی تبدیل کردید؟
حالا بدون تبدیل از قوانین Inorder , pre , post order برید ببینید چی میبینید.

بله، منظورم درخت دودویی معادل جنگله.
خوب صورت سوال این تاپیک هم همینه "پیمایش inorder جنگل و inorder درخت دودویی متناظر با آن یکسان هست؟ "و پاسخ من هم اینه که اگه یه جنگل رو پیمایش postorder کنیم و سپس همان جنگل رو به درخت دودویی تبدیل کنیم و بعد اون درخت دودویی حاصل رو Inorder پیمایش کنیم این دو پیمایش با هم برابرند.
همچنین اگه قصد داشته باشیم پیمایش Inorder یک جنگل رو داشته باشیم می تونیم درخت دودویی متناظرش رو پیمایش Inorder کنیم.

بله اما بحث داشت به سمت کلیات میرفت ومنم بطور کلی گفتم .

(08 دى 1390 01:59 ق.ظ)Masoud05 نوشته شده توسط: [ -> ]بله اما بحث داشت به سمت کلیات میرفت ومنم بطور کلی گفتم .

خدا رو شکر که مسئله حل شد!