نمایش درخت دودویی با استفاده از آرایه

برنامه: نمایش درخت دودویی با استفاده از آرایه توضیحات :

یک درخت دودویی رو به دو صورت میشه نمایش داد
1 - نمایش با آرایه
2 - نمایش با لیست پیوندی

در این قسمت نمایش درخت دودویی با استفاده از ارایه رو می خوایم پیاده کنیم.
همونطور که می دونید در این روش ،ریشه رو در خانه اول ارایه قرار میدیم و از قانون زیر پیروی می کنیم

* اگر عنصری در خانه ی i ام ارایه باشد آنگاه
           پدر ان در خانه ی جزوصحیح i/2 قرار دارد.
           فرزند چپ آن در خانه ی 2*i قرار دارد.
           فرزند راست آن در خانه ی 1+2*i قرار دارد.

*برای نمایش درختی با عمق k به ارایه ای با 2^k-1 خانه نیاز داریم.


درخت ورودی را به صورت زیر از ورودی میگیریم.((فرزند راست ، فرزند چپ)پدر)

(F(B(A,D(C,E)),G(,I(H))))

الگوریتم:

تابع set آرایه ی []s که حاوی رشته ی فوق هست را به همراه ارایه ی []t که قرار هست درخت طبق قوانین بالا در ان ذخیره شود و متغیری که اندازه ی ارایه []s را در خود دارد را از ورودی گرفته و با چند دستور if عملیات را انجام می دهد.

 برنامه ی نمایش درخت با ارایه به زبان ++c

 void set(char s[],char[] t,int sSize)
{
    int i=0;
    int j=0;
    int depth=1,oldDepth=1;
    
    while(i < sSize)
    {
    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;
         }
    }//end while
}//end function