لطفا سوالت رو واضح تر بگو.
تو تبدیل جنگل به درخت دودویی که مشکل نداری؟؟
اگر نه که پیمایش جنگل رو بدست میاری و بعد جنگل رو به درخت دودویی تبدیل کن و باز پیمایش کن میبینی که
پیمایش inorder جنگل با inorder درخت دودویی متناظرش یکسانه
پیمایش post جنگل با inorder درخت دودویی متناظرش یکسانه
درسته !!

(۲۲ آبان ۱۳۹۲ ۱۱:۵۲ ق.ظ)zeinab نوشته شده توسط:  لطفا سوالت رو واضح تر بگو.
تو تبدیل جنگل به درخت دودویی که مشکل نداری؟؟
اگر نه که پیمایش جنگل رو بدست میاری و بعد جنگل رو به درخت دودویی تبدیل کن و باز پیمایش کن میبینی که
پیمایش inorder جنگل با inorder درخت دودویی متناظرش یکسانه
پیمایش post جنگل با inorder درخت دودویی متناظرش یکسانه
درسته !!

توی تبدیل جنگل به دودویی مشکل ندارم و پیمایش درخت دودویی هم که ساده است
ولی خود پیمایش جنگل را نمیدونم چه جوریه و وقتی طبق پیمایش های جنگل که توی کتاب گفته شده پیش میرم نمیدونم چرا پیمایش جنگل با دودویی هایی که بالا گفتیم یکی نمیشه.

مثلا در preorder جنگل گفته شده
۱/ ریشه درخت اول را ببین
۲/ زیر درخت درخت اول را پیمایش pre کن
۳/ سایر درخت های جنگل را پیمایش کن

---

اصلا اون شکل قبلی رو در نظر نگیرید.

این شکل که گذاشتم آیا درست حل کردم یا نه؟
پیمایش های سمت چپی را بر اساس تعریف پیمایش های جنگل انجام دادم.

اول اینکه من ساختمان پوران رو دارم که گفته
پیمایش preorder جنگل با preorder درخت دودویی متناظرش یکسانه و
پیمایش postorder جنگل با inorder درخت دودویی متناظرش یکسانه و در مورد inorder چیزی نگفته. یعنی فقط در مورد preorder , postorder جنگل ، این قضیه ثابت هست.
پس احتمال زیاد پارسه اشتباه گفته. چون حداقل شما یه مثال نقض زدی.
و اینکه پارسه گفته "پیمایش inorder جنگل با inorder درخت دودویی متناظرش یکسانه" غلطه!

و اما پاسختون در مورد این مثالی که زدین اشتباهه
جنگل :
preorder : ABCD
inorder : BACD
postorder : BCAD
درخت دودویی متناظر :
preorder : ABCD
inorder : BCAD
postorder : CBDA

شاید هم اشتباه تایپی بوده که اشتباه نوشتین.
inorder , postorder جنگل رو اشتباه نوشتی

(۲۲ آبان ۱۳۹۲ ۰۷:۴۴ ب.ظ)zeinab نوشته شده توسط:  اول اینکه من ساختمان پوران رو دارم که گفته
پیمایش preorder جنگل با preorder درخت دودویی متناظرش یکسانه و
پیمایش postorder جنگل با inorder درخت دودویی متناظرش یکسانه و در مورد inorder چیزی نگفته. یعنی فقط در مورد preorder , postorder جنگل ، این قضیه ثابت هست.
پس احتمال زیاد پارسه اشتباه گفته. چون حداقل شما یه مثال نقض زدی.
و اینکه پارسه گفته "پیمایش inorder جنگل با inorder درخت دودویی متناظرش یکسانه" غلطه!

جنگل :
inorder : BACD
postorder : BCAD

اینطور که من تو اینترنت دیدم جایی ننوشته که inorder جنگل با inder دودویی یکسانه.
البته توی یکی از تستهای پوران گفته شده که (آزاد ۸۳) که برای یافتن inorder جنگل باید از inorder دودویی معادلش استفاده کرد.
توی اون تست به اشتباه نوشته شده بود که inorder جنگل و دودویی یکسانه و پوران این اشتباه را گوشزد کرده بود
پس پارسه توی کتابش اشتباه نوشته که inorder جنگل و دودویی یکسانه
البته یه سوالی که باز پیش میاد اگر برای inorder جنگل باید از inorder دودویی بدست بیاد، که اینجوری inorder دودویی با post و inorder جنگل یکی میشه و این جا پوران ظاهرا اشتباه کرده و حالا چه جوری باید inorder جنگل را بدست بیارم هنوز نمیدونم ؟؟؟؟؟

ولی دو عبارت دیگه صحیحه که و دیگه کاری باهاش ندارم:
preorder جنگل = preorder درخت دودویی
postorder جنگل = inorder درخت دودویی

البته توی کتاب پارسه ظاهرا یه تعریف دیگه هم اشتباه هست و اونم نحوه پیمایش postorder جنگل. چون در اونجا گفته شده که ریشه اولین درخت آخرین نودی هست که پیمایش میشه. یعنی در این شکل BCDA میشه که با inorder دودویی (BCAD) یکی نیست.

پیمایش هایی post و inorder جنگل را هم طبق تعریف کتاب پارسه (پیمایش جنگل) نوشتم که ظاهرا تعاریف کتاب پارسه اشتباه هست یا شاید من اشتباه برداشت کردم.
ترتیب پیمایش صحیح همون چیزی بود که شما گفتید
جنگل :
inorder : BACD
postorder : BCAD

نتیجه گیری کلی:
اگر جایی یکی از پیمایش های جنگل را خواستند اول جنگل را دودویی میکنم
پیمایش pre دودویی را بدست میارم که میشه pre جنگل
پیمایش inorder دودویی را بدست میارم که میشه post جنگل
یعنی اصلا خطر نمیکنم که بخواهم متسقیما از روی جنگل بدست بیارم
و ظاهرا (مطمئن نیستم) پیمایش inorder جنگل را هم مثل دودویی از روی خود جنگل حساب میکنم و نه از روی دودویی متناظرش

هر جا از حرفهام اشتباه بود لطفا بگید

ببینید کلا برای پیدا کردن پیمایش پیش ترتیب میتونید
۱- هم درخت های جنگل رو از چپ به راست پیمایش پیش ترتیب کنید که مثل همیشه ست، اول ریشه بعد زیر درخت چپ بعد زیر درخت راست، به همین ترتیب درخت دوم و سوم... هم پیمایش پیش ترتیب کنید.
۲- هم میتونید معادل دودویی رو بدست بیارید و پیمایش پیش ترتیب درخت دودویی معادل رو بنویسید.
این دوتا باهم برابرن...
*****
حالا برای پیمایش میان ترتیب میتونید
۱- درخت های جنگل رو از چپ به راست پیمایش **POSTORDER** کنید (دقت کنید این معادل پیمایش inorder جنگل است!!)
۲- یا معادل دودویی رو بدست بیارید و پیمایش میان ترتیب رو از رو درخت دودویی معادل بنویسید...
این دوتا هم با هم برابرن...
(تو کتاب مقسمی گفته:
پیمایش inorder جنگل F که معادل با پیمایش inorder درخت دودویی متناظرش است، به این صورت است: الف- اگرF تهی است پس بگردید. ب- زیردرختان اولین درخت را به صورت inorder پیمایش کنید و سپس ریشه درخت اول را باز یابی کنید *که این میشه همون پیمایش postorder خودمون!!*
ج- سایر درختان F را به صورت inorder پیمایش کنید.)
*******************************************************
پاسخی هم که دادین درسته.
فقط قسمت postorder جنگل رو مطمئن نیستم.