خانه / الگوریتم / الگوریتم و کد درخت با آرایه C++

الگوریتم و کد درخت با آرایه C++

در ابن بخش از سری پست های الگوریتم  دیجی نکست  قصد دارم در مورد نمایش درخت با آرایه توضیحاتی بدم ، و سپس سراغ کد آن به زبان C++ برویم …

راه های مختلفی برای پیاده سازی و نمایش درخت وجود دارد ، که مهمترین اونها توسط لینک لیست و شاید آرایه انجام میگیره … در این قسمت از این پست سعی دارم به شما تلقین کنم که لینک لیست برای پیاده سازی درخت بهتر از آرایه است (لینک لیست چیه؟ کلیک کنید ) ، چرا ؟
درسته که برای ساختن لینک لیست باید از کلاس استفاده کنید (البته کتابخانه آماده linklist هم وجود دارد که در آینده در موردش حرف خواهم زد) اما بهینگی که در لینک لیست برای درخت وجود دارد در آرایه نیست مخصوصا در درخت های خیلی بزرگتر ، آرایه فضای زیادی از مموری بدون استفاده اشغال میکند و این برای کار های حرفه ای اصلا اتفاق جالبی نیست .

NonLinkedRepBinTr
مثلا در شکل بالا درخت چون بصورت نسبتا متعادل رشد کرده اگر الگوریتمش با آرایه پیاده سازی شود بهینگی آن زیاد به چشم نخواهد آمد ولی اگر مثلا یک طرف در خت رشد کند ولی طرف دیگر آن زیاد رشدی نداشته باشد باعث خواهد شد که الگوریتم با آرایه اصلا جالب به نظر نیاد ، این مطلبی که الان گفته شده همان کامل بودن درخت است (درخت کامل دقیقا چیه ؟ دعوت میکنم از ویکی پدیا این مطلب رو بخونید ، کلیک کنید ) .

اما یک سوال دیگر که به نظر میرسد اینه که ورودی ما به کد در چه قالبی باشد ؟
برای اینکار ما به ازای هر ریشه یک پرانتز باز میکنیم و به ازای ها برادر یک ویرگول میگذاریم و در نهایت پرانتز هارا میبندیم که مثالی از آن را در شکل زیر برای شما آماده کردم :
1
این عبارت (a(b,c)) یعنی a دو فرزند دارد که b و c هستند که آنها خود با همدیگر برادر هستند . نکته ای وجود دارد این است که مثلا اگر بخواهیم پدر c را پیدا کنیم باید اندیس c را که ۳ است تقسیم بر ۲ کنیم که پاسخ در اعداد صحیح ۱ میباشد و اندیس ۱همان a است . و همینکار برای b نیز قابل بیان است .

 

خب ، الگوریتم را توضیح دادیم ، حالا بریم سراغ کد این الگوریتم به زبان C++ :

 



#include <iostream>
#include <string>
//by pooyaChavoshi , diginext.ir
using namespace std;
int main (){
    string s,t ;
    cout<<"INTER TREE SENTENCE WITH PARANTHENSES : "<<endl;
    cin>>s ;
    int size = 0;
    int count = 0;
    for (int i=0 ; i<s.length() ; i++){
        if (s[i]>='A' && s[i]<='Z' || s[i]>='a' && s[i]<='z'){
            count++;
        }
        size++;
        
    }
    int a[count*3];
    cout<<count<<endl;
    
    int j=0,i=0;
    
    while(i <size)
    {
    if( s[i]=='(' )
    {
        if(j==0) j=1;
        else  j=2*j;
        i=i+1;
    }
    else if( s[i]==',' )
    {
        j=j+1;
        i=i+1;
    }
    else if( s[i]==')' )
    {
        j=j/2;
        i=i+1;
    }
    else {
         
         t[j]=s[i];
         i=i+1;
         }
    }
    for (int i = 0 ; i<count*3 ; i++){
        cout<<i<<" ";
    }
    cout<<endl;
    
    for (int i = 0 ; i<count+1 ; i++){
        cout<<t[i]<<" ";
    }
}
//example : (a(b(d,e),f(g,h)) 



 

لطفا صرفا کد را کپی نکنید ، و سعی داشته باشید کل مطلب را فرا بگیرید و درصورت داشتن مشکل حتما بیان کنید تا دوستان دیگر نیز استفاده بکنند.

۲ دولایک کن

درباره pooya

آواتار pooya
پویا چاوشی مدیر وبسایت دیجی نکست هستم... دانشجوی رشته ی نرم افزار و در زمینه طراحی و برنامه نویسی وب و همچنین برنامه نویسی بازی و طراحی نرم افزار اندروید فعالیت دارم ... در اوقات فراغتم گاها آهنگسازی هم میکنم// امیدوارم مطالبی که براتون مینویسم مفید باشه و استفاده بکنید.

دیدگاهتان را ثبت کنید

آدرس ایمیل شما منتشر نخواهد شدعلامتدارها لازمند *

*

شکلک خودتو انتخاب کن !

SmileBig SmileGrinLaughFrownBig FrownCryNeutralWinkKissRazzChicCoolAngryReally AngryConfusedQuestionThinkingPainShockYesNoLOLSillyBeautyLashesCuteShyBlushKissedIn LoveDroolGiggleSnickerHeh!SmirkWiltWeepIDKStruggleSide FrownDazedHypnotizedSweatEek!Roll EyesSarcasmDisdainSmugMoney MouthFoot in MouthShut MouthQuietShameBeat UpMeanEvil GrinGrit TeethShoutPissed OffReally PissedMad RazzDrunken RazzSickYawnSleepyDanceClapJumpHandshakeHigh FiveHug LeftHug RightKiss BlowKissingByeGo AwayCall MeOn the PhoneSecretMeetingWavingStopTime OutTalk to the HandLoserLyingDOH!Fingers CrossedWaitingSuspenseTremblePrayWorshipStarvingEatVictoryCurseAlienAngelClownCowboyCyclopsDevilDoctorFemale FighterMale FighterMohawkMusicNerdPartyPirateSkywalkerSnowmanSoldierVampireZombie KillerGhostSkeleton

bigtheme