چند تا سوال داشتم در مورد درخت عبارت و پیمایش درخت. ( درخت ها دودویی فرض شود )
الف ) با داشتن حداقل کدام پیمایش ( ها ) میتوان یک درخت واحد رسم کرد ( از بین Pre-order ، inorder و post-order )
ب ) آیا همان طور که میشه عبارت infix رو به postfix و prefix تبدیل کرد ، بالعکس اون هم ممکنه ؟
پ ) ایا مستقیم میشه درخت عبارت رو از روی یکی از دو ارزیابی ( postfix - prefix ) رسم کرد ؟ ( میدونم که از روی infix میشه )
متشکرم
سلام. با داشتن preorder و postorder میشه به راحتی گره های تک فرزندی رو به دست آورد. از طرفی اولین گره در ترتیب پیش ترتیب میشه ریشه و آخرین گره ش میشه سمت راست ترین برگ. برای پیمایش پس ترتیب، گره ی سمت چپ در عبارت سمت چپ ترین برگ و آخرین گره در عبارت ریشه هست.
با توجه به این که برگ ها بین سمت چپ ترین و سمت راست ترین برگ هستن و با توجه به این که میدونیم توی درخت دودویی تعداد کل گره ها برابر با مجموع گره های تک فرزندی، دوفرزندی و برگ هاست و همینطور تعداد برگ ها یکی از دوفرزندی ها بیشتر هست میشه درخت رو رسم کرد. منتها به شرطی که گره ی تک فرزندی نداشته باشیم. اگه داشته باشیم ۲ به توان تعداد تک فرزندی ها درخت میشه رسم کرد.
اگه پیمایش میان ترتیب رو با هر کدوم از پیمایش های پیش ترتیب، پس ترتیب و سطری داشته باشیم هم میشه درخت رو رسم کرد. پیمایش میان ترتیب واسه فهمیدن جهت و اون یکی پیمایش واسه پیدا کردن ریشه کمک میکنه.
هر کدوم از پیمایش های میان ترتیب، پیش ترتیب و پس ترتیب رو اگه تمام برگ ها یا تمام گره های دوفرزندی رو داشته باشیم و بگن که تک فرزندی نداریم یعنی دودویی محض هست هم میشه درخت واحد رو رسم کرد.
نکته: اگه بگن درخت کامل یا پر هست هم که خب از هر تک پیمایش میشه رسمش کرد. اما متوازن باشه نمیشه.
قسمت دوم و سوم سوالتون هم بله میشه.
برای هر قسمتی که خواستید مثال میزنم.
(۰۷ آذر ۱۳۹۵ ۰۳:۵۸ ب.ظ)Pure Liveliness نوشته شده توسط: برای هر قسمتی که خواستید مثال میزنم.
تشکر از پاسخگویی تون .
اگه ممکنه برای قسمت ۳ یک مثال از تبدیل مستقیم Postfix به درخت عبارت بگید . متشکرم
(۰۷ آذر ۱۳۹۵ ۰۴:۲۰ ب.ظ)alireza01 نوشته شده توسط:خواهش میکنم. مثلا عبارت postfix زیر رو در نظر بگیرید:(07 آذر ۱۳۹۵ ۰۳:۵۸ ب.ظ)Pure Liveliness نوشته شده توسط: برای هر قسمتی که خواستید مثال میزنم.تشکر از پاسخگویی تون .
اگه ممکنه برای قسمت ۳ یک مثال از تبدیل مستقیم Postfix به درخت عبارت بگید . متشکرم
[tex]ab\: -\: cdef\: \ slash \: -\: \ast\: +[/tex]
به همون ترتیبی که میومدیم تبدیل میکردیم این عبارت رو به میانوندی با همون اولویت و ترتیب درختش رو تیکه تیکه میکشیم.
اول از همه -ab رو رسم میکنیم که این خودش میشه یه عملوند واسه عملگر بعدی، بعدش c هست اما بعد از c عملگر نیست. پس این عبارت و c با هم عملگری ندارن. میریم سراغ حرف بعدی d بعدش عملگر نیست، میریم سراغ بعدی یعنی e اینم بعدش عملگر نیست، بعدی یعنی f بعدش عملگر هست. پس دو تای قبلیش میشه عملوند هاش یعنی عملگر / روی eو f عمل میکنه و اونا رو به ترتیب به عنوان عملوند های سمت چپ و راست زیردرخت قرار میده. حرف بعدی عملوند - هست که این زیردرخت /ef و d عملوندهاش هستن، بعدش عملگر * عملوند هاش اون زیردرخت راستی هست که طی دو مرحله رسم کردیم و هم c حالا به عملگر + میرسیم که عملوند هاش درخت چپ رسم شده و راست رسم شده هستن.
البته این خیلی قانونمند نبود و با پشته واینا میشه رسمش کرد. نمیدونم کجا دیدم ولی یادمه یه کتابی خیلی خوب توضیح داده بود.
البته! اگر عملگر تک عملوندی داشتیم ممکنه بتونیم هم به عنوان فرزند راست و هم چپ قرارش بدیم. این بستگی داره که قرارداد باشه یا نه، اگه نه که ۲ به توان تعداد تک فرزندی ها میشه درخت کشید.