زمان کنونی: ۰۳ دى ۱۴۰۳, ۰۴:۱۳ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

درخت باینری

ارسال:
  

Eng_Sara پرسیده:

درخت باینری


در یک درخت باینری T با n گره در چه حالتی گره در اولین پیمایش post order مشابه آخرین گره در پیمایش inorder است؟

۱) زیر درخت چپ T خالی باشد.
۲) T دارای ارتفاع n-1 باشد.
۳) زیر درخت راست T خالی باشد.
۴) T حداکثر سه گره داشته باشد.


دوستان برای این سوال من سه تا پاسخ متفاوت توی سه تا کتاب دیدم! دیگه به خودم و جوابم هم شک کردم Big Grin گفتم دوستان یه نظری بدن.

یه جا گزینه ۱ رو زده بود درست که نظر منم همین گزینه هست.
یه کتاب دیگه گزینه ۲ رو کلید زده بود!!!!
کتاب سوم هم گفته بود گزینه صحیح وجود ندارد!!!!! Big Grin

قضیه چیه؟!

ممنون.موفق باشید
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Amir V پاسخ داده:

Re: درخت باینری

سلام دوباره.

ببین این سوالا رو باید مثال بزنی واسه خودت و سعی کنی مثال نقض پیدا کنی.

جواب درست گزینه ۱ هست و غلط بودن بقیه با مثال نقض اثبات میشه.

یه درخت مورب راست بکش(زیر درخت چپ خالیه) و بعد postorder و inorder رو روش انجام بده. میبینی که درست جواب میده. مثلا ریشه رو بزار a فرزند راستش b و فرزند راست b هم c.
در اینصورت پیمایش postorder به شکل cba میشه و inorder به شکل abc. میبینیم که اولین گره پیمایش شده در postorder برابره با اخرین گره پیمایش شده در inorder.

برای بقیه هم مثال نقض میشه آورد.

Sent from my Google Galaxy Nexus using Tapatalk 2.4
نقل قول این ارسال در یک پاسخ

ارسال:
  

mahdiii پاسخ داده:

RE: درخت باینری

(۱۳ دى ۱۳۹۱ ۰۱:۳۹ ب.ظ)Amir V نوشته شده توسط:  سلام دوباره.

ببین این سوالا رو باید مثال بزنی واسه خودت و سعی کنی مثال نقض پیدا کنی.

جواب درست گزینه ۱ هست و غلط بودن بقیه با مثال نقض اثبات میشه.

یه درخت مورب راست بکش(زیر درخت چپ خالیه) و بعد postorder و inorder رو روش انجام بده. میبینی که درست جواب میده. مثلا ریشه رو بزار a فرزند راستش b و فرزند راست b هم c.
در اینصورت پیمایش postorder به شکل cba میشه و inorder به شکل abc. میبینیم که اولین گره پیمایش شده در postorder برابره با اخرین گره پیمایش شده در inorder.

برای بقیه هم مثال نقض میشه آورد.

Sent from my Google Galaxy Nexus using Tapatalk 2.4

منظور این سوال از زیردرخت چپ یا راست T چیه؟ منظورش برای ریشه است؟ چون زیردرخت چپ و راست برای هر گره ای قابل تعریفه.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

egm1176 پاسخ داده:

RE: درخت باینری

آقای یوسفی تو کتابشون گفتند حالت اول هم مثال نقض داره

a ریشه باشه و b فرزند راستش و c فرزند چپ b
که در این حالت زیردرخت چپ خالیه. ولی شرایط برقرار نیست.
post : CBA
in : ACB

که اولین گره در post با آخرین گره در in برابر نیست.
دقت کنید که آخرین گره در post و اولین گره در in مثل همن ولی سوال این رو نمی خواد.
اگه اشتباه می کنم بگید.


فایل‌(های) پیوست شده

نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Eng_Sara پاسخ داده:

درخت باینری

@egm1176
به نظرم درسته! تو گزینه ها باید به جای اینا مینوشت که درخت مورب چپ یا راست باشه ممکنه یا نه؟؟!!
یعنی گزینه صحیح وجود نداره دیگه؟

آقا امیر نظر شما چیه؟؟
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Amir V پاسخ داده:

Re: درخت باینری

سارا جان موافقم باهات.
باید میزد درخت مورب.

Sent from my Google Galaxy Nexus using Tapatalk 2.4
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

csharpisatechnology پاسخ داده:

درخت باینری

گزینه ی ۳ درست است.
[تصویر:  1.gif]

در گزینه ی ۱ حالات پیشوندی و میانوندی یکسان اند.


فایل‌(های) پیوست شده

نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

csharpisatechnology پاسخ داده:

درخت باینری

دوست عزیز (mahdi) شما اشتباه می کنید .
خودتون یه درخت مورب راست بکش . می بینی postorder و inorder با هم فرق می کنه:
مثال :
ABC
postorder میشه :
CBA
و inorder میشه :
ABC
که با هم فرق داره
------
همون ۳ درسته. بنده هم امتحان کردم.دقت بفرمایید.
نقل قول این ارسال در یک پاسخ

ارسال:
  

mahdiii پاسخ داده:

RE: درخت باینری

(۱۴ بهمن ۱۳۹۱ ۰۳:۲۷ ق.ظ)csharpisatechnology نوشته شده توسط:  دوست عزیز (mahdi) شما اشتباه می کنید .
خودتون یه درخت مورب راست بکش . می بینی postorder و inorder با هم فرق می کنه:
مثال :
ABC
postorder میشه :
CBA
و inorder میشه :
ABC
که با هم فرق داره
------
همون ۳ درسته. بنده هم امتحان کردم.دقت بفرمایید.

بله postorder با inorder فرق می کنه در درخت مورب راست. سوال گفته
"گره در اولین پیمایش post order مشابه آخرین گره در پیمایش inorder"
یعنی گره اول و آخرو مقایسه کرده
سه که قطعا نیست
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۰
  

fsi2013 پاسخ داده:

درخت باینری

بهترین جواب گزینه ی ۲ هستش منظور سوال و طراح هم این بوده که درخت مورب چپ باشه هرچند حالت ۲ هم به طور کلی نادرسته
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تعداد برگ درخت؟؟؟؟؟؟؟ rad.bahar ۴ ۴,۹۱۱ ۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ
آخرین ارسال: mohamadrra
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۳ ۵,۶۵۰ ۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ
آخرین ارسال: marzi.pnh
  زمان جستجوی درخت fateme.sm ۰ ۱,۷۹۵ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۴۱۶ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  عمق درخت ???? rad.bahar ۱ ۲,۴۳۶ ۱۱ مهر ۱۳۹۹ ۰۳:۳۱ ب.ظ
آخرین ارسال: عزیز دادخواه
  محاسبه ارتفاع درخت.... baharkhanoom ۳ ۸,۱۷۱ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ
آخرین ارسال: mohsentafresh
  تعداد درخت فراگیر ss311 ۰ ۲,۳۳۹ ۰۶ بهمن ۱۳۹۸ ۰۵:۰۶ ب.ظ
آخرین ارسال: ss311
  درخت دسترس پذیری برای شبکه های پتری αɾια ۱ ۲,۴۲۳ ۰۹ تیر ۱۳۹۸ ۰۶:۳۰ ب.ظ
آخرین ارسال: αɾια
  سطح و عمق و ارتفاع درخت remove ۵ ۱۱,۴۷۴ ۱۹ اسفند ۱۳۹۷ ۰۴:۲۴ ب.ظ
آخرین ارسال: mstfvi
  الگوریتم درخت porseshgar ۰ ۱,۷۰۶ ۱۷ بهمن ۱۳۹۷ ۱۲:۲۴ ب.ظ
آخرین ارسال: porseshgar

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close