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

درخت عبارت و پیمایش درخت

ارسال:
  

alireza01 پرسیده:

درخت عبارت و پیمایش درخت

چند تا سوال داشتم در مورد درخت عبارت و پیمایش درخت. ( درخت ها دودویی فرض شود )

الف ) با داشتن حداقل کدام پیمایش ( ها ) میتوان یک درخت واحد رسم کرد ( از بین Pre-order ، inorder و post-order )

ب ) آیا همان طور که میشه عبارت infix رو به postfix و prefix تبدیل کرد ، بالعکس اون هم ممکنه ؟

پ ) ایا مستقیم میشه درخت عبارت رو از روی یکی از دو ارزیابی ( postfix - prefix ) رسم کرد ؟ ( میدونم که از روی infix میشه )

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

۱
ارسال:
  

Pure Liveliness پاسخ داده:

RE: درخت عبارت و پیمایش درخت

سلام. با داشتن preorder و postorder میشه به راحتی گره های تک فرزندی رو به دست آورد. از طرفی اولین گره در ترتیب پیش ترتیب میشه ریشه و آخرین گره ش میشه سمت راست ترین برگ. برای پیمایش پس ترتیب، گره ی سمت چپ در عبارت سمت چپ ترین برگ و آخرین گره در عبارت ریشه هست.
با توجه به این که برگ ها بین سمت چپ ترین و سمت راست ترین برگ هستن و با توجه به این که میدونیم توی درخت دودویی تعداد کل گره ها برابر با مجموع گره های تک فرزندی، دوفرزندی و برگ هاست و همینطور تعداد برگ ها یکی از دوفرزندی ها بیشتر هست میشه درخت رو رسم کرد. منتها به شرطی که گره ی تک فرزندی نداشته باشیم. اگه داشته باشیم ۲ به توان تعداد تک فرزندی ها درخت میشه رسم کرد.
اگه پیمایش میان ترتیب رو با هر کدوم از پیمایش های پیش ترتیب، پس ترتیب و سطری داشته باشیم هم میشه درخت رو رسم کرد. پیمایش میان ترتیب واسه فهمیدن جهت و اون یکی پیمایش واسه پیدا کردن ریشه کمک میکنه.
هر کدوم از پیمایش های میان ترتیب، پیش ترتیب و پس ترتیب رو اگه تمام برگ ها یا تمام گره های دوفرزندی رو داشته باشیم و بگن که تک فرزندی نداریم یعنی دودویی محض هست هم میشه درخت واحد رو رسم کرد.
نکته: اگه بگن درخت کامل یا پر هست هم که خب از هر تک پیمایش میشه رسمش کرد. اما متوازن باشه نمیشه.
قسمت دوم و سوم سوالتون هم بله میشه.
برای هر قسمتی که خواستید مثال میزنم.
نقل قول این ارسال در یک پاسخ

ارسال:
  

alireza01 پاسخ داده:

RE: درخت عبارت و پیمایش درخت

(۰۷ آذر ۱۳۹۵ ۰۳:۵۸ ب.ظ)Pure Liveliness نوشته شده توسط:  برای هر قسمتی که خواستید مثال میزنم.

تشکر از پاسخگویی تون .

اگه ممکنه برای قسمت ۳ یک مثال از تبدیل مستقیم Postfix به درخت عبارت بگید . متشکرم
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

Pure Liveliness پاسخ داده:

RE: درخت عبارت و پیمایش درخت

(۰۷ آذر ۱۳۹۵ ۰۴:۲۰ ب.ظ)alireza01 نوشته شده توسط:  
(07 آذر ۱۳۹۵ ۰۳:۵۸ ب.ظ)Pure Liveliness نوشته شده توسط:  برای هر قسمتی که خواستید مثال میزنم.
تشکر از پاسخگویی تون .
اگه ممکنه برای قسمت ۳ یک مثال از تبدیل مستقیم Postfix به درخت عبارت بگید . متشکرم
خواهش میکنم. مثلا عبارت postfix زیر رو در نظر بگیرید:
[tex]ab\: -\: cdef\: \ slash \: -\: \ast\: +[/tex]

به همون ترتیبی که میومدیم تبدیل میکردیم این عبارت رو به میانوندی با همون اولویت و ترتیب درختش رو تیکه تیکه میکشیم.
اول از همه -ab رو رسم میکنیم که این خودش میشه یه عملوند واسه عملگر بعدی، بعدش c هست اما بعد از c عملگر نیست. پس این عبارت و c با هم عملگری ندارن. میریم سراغ حرف بعدی d بعدش عملگر نیست، میریم سراغ بعدی یعنی e اینم بعدش عملگر نیست، بعدی یعنی f بعدش عملگر هست. پس دو تای قبلیش میشه عملوند هاش یعنی عملگر / روی eو f عمل میکنه و اونا رو به ترتیب به عنوان عملوند های سمت چپ و راست زیردرخت قرار میده. حرف بعدی عملوند - هست که این زیردرخت /ef و d عملوندهاش هستن، بعدش عملگر * عملوند هاش اون زیردرخت راستی هست که طی دو مرحله رسم کردیم و هم c حالا به عملگر + میرسیم که عملوند هاش درخت چپ رسم شده و راست رسم شده هستن.
البته این خیلی قانونمند نبود و با پشته واینا میشه رسمش کرد. نمیدونم کجا دیدم ولی یادمه یه کتابی خیلی خوب توضیح داده بود.
البته! اگر عملگر تک عملوندی داشتیم ممکنه بتونیم هم به عنوان فرزند راست و هم چپ قرارش بدیم. این بستگی داره که قرارداد باشه یا نه، اگه نه که ۲ به توان تعداد تک فرزندی ها میشه درخت کشید.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ



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

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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