سلام
چطور میشه با داشتن پیمایش میان ترتیب و ارتفاع هر عنصر درخت را یکتا ساخت؟خب وقتی درخت عادی باشه نود میتونه بره راست و چپ !! بعد یکتایی چی میشه این وسط؟
مثال میزنم نمیتونم درخت بکشم
مرسی
------------
ببخشید ی سوال دیگه هم دارم از قدسی
سوال ۳/۲۹ گفتن که ترتیب ملاقات برگ های یک درخت در پیمایش سطح ترتیب با هیچکدام از ۳ تا پیمایش دیگه برابر نیست؟ درست آیا ؟
(۱۵ فروردین ۱۳۹۵ ۰۹:۵۸ ب.ظ)samanbeigmiri نوشته شده توسط: تنها در صورتی میتوان درخت دودویی را یکتا رسم کرد که گره ی تک فرزندی نداشته باشیم.
یه سر بزن توی این لینکا : من خودم درخت رو یادم نیست آخرین بار کی خوندم ولی سوالتون جالب بود رفتم یه سرچی زدم.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
اینجا البته بحثشون یه کوچولو متفاوت تر هست،اما به هر حال صرف داشتن ارتفاع نمیشود گره ایی را قائل به داشتن گره ی تک فرزندی یا نداشتن آن ملزم دانست.یعنی ارتفاع تاثیر مستقیمی روی یک تا بودن یا نبودن دارد و گره های تک فرزندی هستند که یکتایی یا عدم اون رو در درخت(دودویی) نه BST مشخص میکنند.
------
برای سوال بعدیتون هم بله درسته.با هیچ کدام از حالت ها درست نیست
یه درخت با سه سطح رسم کنید و توش بنویسید a , b , c , d , e , f , g پیمایش سطح ترتیب همونه که از روی قاعده ی عادی پیمایش درخت بر اساس شماره ها هستش.یعنی اول ریشه و بعد سمت چپ و بعد راست و به همین ترتیب، یعنی مثلا شما گره ها رو از یک تا ۷ شماره گذاری کنید. و الفبای بالا رو بر اون اساس بنویسید.
بعد پیمایش ها رو هم بنویسید؛ میبینید که با هیچ کدوم جور نیست
مرسی از توجه شما
تو تست اول قدسی بدون هیچ اشاره ای فقط این گزینه را درست فرض کرده گفتم شاید نکته ای باشه من بی خبرم
من نتونستم عکس بگیرم شما به تست نگاه بندازید مشخص هست در مورد تست دوم : من همین م فرمودین رسم کردم ولی ترتیب ملاقات برگ ها حفظ هست...یعنی این برگ ها ب همون ترتیبی پیمایش میشن که توی اون ۳ تا پیمایش شدن..مکانشون متفاوت هست ولی تقدم و اینا یکیه
داستان چیه الان ؟
سلام به دوست خوبم سامان و shirin0101
در مورد سوال اول من مطمئن نیستم اما فکر میکنم بشه با دانستن پیمایش میان ترتیب و عمق هر عنصر درخت رو یکتا ساخت.من چند تا مثال واسه خودم زدم و تونستم درخت رو بسازم ولی مثال نقض پیدا نکردم.واسه توجیهش میتونم بگم که با پیمایش میان ترتیب و عمق هر عنصر میشه چپ یا راست بودن عناصر رو پیدا کرد.اما مطمئن نیستم.هرکسی مطمئن شد ما رو با خبر کنه.
در مورد سوال دوم در حالت کلی اینطور نیست اما میشه چند درخت رو مثال زد که پیمایش سطحی با پیمایش های دیگه برابر باشه. مثلا درخت دودویی ۳ عنصری پر،که پیمایش سطحی اون با پیمایش پیش ترتیب برابره.
(۱۵ فروردین ۱۳۹۵ ۱۰:۵۳ ب.ظ)reza.bsh نوشته شده توسط: سلام به دوست خوبم سامان و shirin0101
در مورد سوال اول من مطمئن نیستم اما فکر میکنم بشه با دانستن پیمایش میان ترتیب و عمق هر عنصر درخت رو یکتا ساخت.من چند تا مثال واسه خودم زدم و تونستم درخت رو بسازم ولی مثال نقض پیدا نکردم.واسه توجیهش میتونم بگم که با پیمایش میان ترتیب و عمق هر عنصر میشه چپ یا راست بودن عناصر رو پیدا کرد.اما مطمئن نیستم.هرکسی مطمئن شد ما رو با خبر کنه.
در مورد سوال دوم در حالت کلی اینطور نیست اما میشه چند درخت رو مثال زد که پیمایش سطحی با پیمایش های دیگه برابر باشه. مثلا درخت دودویی ۳ عنصری پر،که پیمایش سطحی اون با پیمایش پیش ترتیب برابره.
مرسی از پاسخ شما...
میشه یکی از مثال هاتون بگید؟ چطور تشخیص دادین من اول درخت میکشم و میان ترتیب براش مینویسم بعد که برعکس میخوام برم این مسیر..یعنی از میان ترتیب و ارتفاع استفاده کنم و درخت بکشم نمیتونم اخه درخت عادی هست فرضا...یعنی خیلی حالت ها میتونم بکشم
درمورد تست دوم هم نتیجه اینکه در حالت کلی ترتیب برگ ها حفظ نمیشه؟ میشه یک مثال نقض بگید؟
ی سوال!! چرا هیچکدوم از دوستان به ترتیب ملاقات برگ اشاره نکردن تو صحبت هاشون؟
اقای reza.bsh در این مثالی ک فرمودین ترتیب ملاقات برگ توی هر ۳تا پیمایش برابر میشه چرا فقط پیش ترتیب؟ شاید من درست متوجه نشدم
با تشکر
(۱۵ فروردین ۱۳۹۵ ۱۱:۲۳ ب.ظ)shirin0101 نوشته شده توسط:(15 فروردین ۱۳۹۵ ۱۰:۵۳ ب.ظ)reza.bsh نوشته شده توسط: سلام به دوست خوبم سامان و shirin0101
در مورد سوال اول من مطمئن نیستم اما فکر میکنم بشه با دانستن پیمایش میان ترتیب و عمق هر عنصر درخت رو یکتا ساخت.من چند تا مثال واسه خودم زدم و تونستم درخت رو بسازم ولی مثال نقض پیدا نکردم.واسه توجیهش میتونم بگم که با پیمایش میان ترتیب و عمق هر عنصر میشه چپ یا راست بودن عناصر رو پیدا کرد.اما مطمئن نیستم.هرکسی مطمئن شد ما رو با خبر کنه.
در مورد سوال دوم در حالت کلی اینطور نیست اما میشه چند درخت رو مثال زد که پیمایش سطحی با پیمایش های دیگه برابر باشه. مثلا درخت دودویی ۳ عنصری پر،که پیمایش سطحی اون با پیمایش پیش ترتیب برابره.
مرسی از پاسخ شما...
میشه یکی از مثال هاتون بگید؟ چطور تشخیص دادین من اول درخت میکشم و میان ترتیب براش مینویسم بعد که برعکس میخوام برم این مسیر..یعنی از میان ترتیب و ارتفاع استفاده کنم و درخت بکشم نمیتونم اخه درخت عادی هست فرضا...یعنی خیلی حالت ها میتونم بکشم
درمورد تست دوم هم نتیجه اینکه در حالت کلی ترتیب برگ ها حفظ نمیشه؟ میشه یک مثال نقض بگید؟
ی سوال!! چرا هیچکدوم از دوستان به ترتیب ملاقات برگ اشاره نکردن تو صحبت هاشون؟
اقای reza.bsh در این مثالی ک فرمودین ترتیب ملاقات برگ توی هر ۳تا پیمایش برابر میشه چرا فقط پیش ترتیب؟ شاید من درست متوجه نشدم
با تشکر
واسه سوال اول همون مثال درخت پر دودویی با ۳ عنصر رو میشه مثال زد.واسه ۱ مثال دیگه یکی از برگ ها رو حذق کنید که گره تک فرزندی هم داشته باشید.
در مورد سوال دوم من فکر کردم منظور ترتیب کل عناصره نه فقط برگ ها.
اگه منظور فقط ترتیب برگ ها باشه که فکر کنم ترتیب ملاقات برگ ها در تمام پیمایشهای سطحی،پیش ترتیب،میان ترتیب و پس ترتیب با هم برابر باشه.چون در تمام این پیمایش ها اول گره چپ پیمایش میشه بعد گره راست.پس ترتیب ملاقات برگ ها همیشه مثل همه.(اگر در پیمایش انجام شده گره های غیر برگ رو حذف کنیم میبینیم که ترتیب ها با هم برابره).
(۱۵ فروردین ۱۳۹۵ ۰۹:۲۸ ب.ظ)shirin0101 نوشته شده توسط: سلامسلام به همگی
چطور میشه با داشتن پیمایش میان ترتیب و ارتفاع هر عنصر درخت را یکتا ساخت؟خب وقتی درخت عادی باشه نود میتونه بره راست و چپ !! بعد یکتایی چی میشه این وسط؟
مثال میزنم نمیتونم درخت بکشم
مرسی
این سوال کاملا هم درستهاولا اینجا نگفته که عمق هر گره!گفته ارتفاع هر گره!
دوما با داشتن پیمایش میان ترتیب و ارتفاع هر گره،میشه یک درخت دودویی یکتا کشید.
مثلا با پیمایش میان ترتیب c b a و اینکه ازتفاع c=0 (یعنی برگ) ،ارتفاع b=1 و ارتفاع a=2 (یعنی ریشه،چون بیشترین ارتفاع رو داره) فقط و فقط درخت مورب چپ زیر بدست میاد.
اول که ریشه رو میکشیم(گره a)،بعد چون که گره های b و c در سمت چپ a هستن،پس a فرزند سمت راست نداره.
بعدش در سمت چپ a، گره ی با بیشترین ارتفاع بعدی b هستش،که بعنوان فرزند سمت چپ a رسمش میکنیم.
و در پایان برگ c (گره با ارتفاع ۰) میمونه که چون تو پیمایش میان ترتیب،در سمت چپ b هستش،پس فرزند سمت چپ b خواهد بود.
و درخت بصورت یکتا رسم شد.
![[تصویر: 399932_tree.jpg]](https://img.manesht.ir/399932_tree.jpg)
و یک درخت بدون گره تک فرزندی هم میکشم:
مثلا پیمایش میان ترتیب درختی بصورت زیر هستش:
d, b ,e ,a ,c با ارتفاع های هر گره d=0 , b=1 , e=0 , a=2 , c=0
پس a ، ریشه ما خواهد بود(گره ای با بیشترین ارتفاع) و d و b و e در سمت چپ a هستند و c در سمت راست a.
پس c فرزند راست a خواهد بود.
در سمت چپ a: گره b ( دارای بیشترین ارتفاع در بین گره های سمت چپ a) بعنوان فرزند سمت چپ a انتخاب میشه.
و چون بر طبق پیمایش،گره e فرزند راست b هستش و گره d فرزند چپ b هستش،پس درخت بصورت یکتا رسم شد.
اینم از شکل:
![[تصویر: 399932_tree2.jpg]](https://img.manesht.ir/399932_tree2.jpg)
(۱۵ فروردین ۱۳۹۵ ۰۹:۲۸ ب.ظ)shirin0101 نوشته شده توسط: ببخشید ی سوال دیگه هم دارم از قدسیدر مورد این سوال هم.ترتیب ملاقات برگ ها که تو این ۴ پیمایش یکسانه.ولی ترتیب ملاقات گره ها لزوما یکسان نیست
سوال ۳/۲۹ گفتن که ترتیب ملاقات برگ های یک درخت در پیمایش سطح ترتیب با هیچکدام از ۳ تا پیمایش دیگه برابر نیست؟ درست آیا ؟