پرانتزگذاری درخت

[yaseriran]

درود!

نمایش پرانتزگذاری درخت را با c++ می خوام بنویسم...
برای نمونه: ورودی برنامه inorder: dbahgiecflkj
خروجی: a(b(d,null),c(e(g(h,i),null),f(null,j(k(l,null),nu ll))))

سپاس از دوستان...



اسب تازی افتاده زیر پالان * طوق زرین همه بر گردن خر میبینیم...

[Arcsinos]

باید بگم که فقط با یه پیمایش نمیتوان درخت منحصر به فردی ساخت : به عنوان مثال اگر پیمایش inorder=ABC باشه تو اینجا هم میتونه A ریشه باشه و هم B و هم C . برای به دست آووردن درخت منحصر به فرد پیمایش inorder به علاوه ی یکی از پیمایش های preorder یا postorder ضروریست .

[yaseriran]

درود!

باید بگم که فقط با یه پیمایش نمیتوان درخت منحصر به فردی ساخت : به عنوان مثال اگر پیمایش inorder=ABC باشه تو اینجا هم میتونه A ریشه باشه و هم B و هم C . برای به دست آووردن درخت منحصر به فرد پیمایش inorder به علاوه ی یکی از پیمایش های preorder یا postorder ضروریست .


درسته؛ شما همونطوری که گفتید پرانتزگذاری کنید.


هوا بس ناجوانمردانه سرد است...

[Arcsinos]

دوست عزیز همه ی کاراش رو انجام دادم ، درختشم تشکیل دادم تابع write رو هم نوشتم فقط کافیه که درخت رو کامل کنی (اشاره گرهای راست و چپش رو به خونه ی مورد نظر اشاره بدی ) و ریشه رو بدی به تابع write که برات پرانتز گذاری کنه همین . اینو به خودت میسپارم . منم درس دارم و منم پروژه دارم . پروژه ی منم پیاده سازی درخت انتخابی و دارم روش کار میکنم .
بیشتر از این نمیتونم همراهیت کنم :


// prepost.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "iostream"
#include "conio.h"
using namespace std;
struct node
{
node *left;
char info;
node *right;
};
node *getnode()
{
node *q;
q=new struct node;
return q;
}
void add(char pre[20],char in[20],int more) /*begin add*/
{
cout<<"please enter preorder for example: a d v h : ";
for(int i=0 ;i< more;i++)
cin>>pre[i];
cout<<"\nplease enter preorder for example: a d v h : ";
for(int j=0 ;j< more;j++)
cin>>in[j];
} /*end add*/
int shakhes(char pre[],char in[],int result[20][2],int more ) /*begin shakhes*/
{ for(int s=0;s<more;s++)
{result[s][0]=0;
result[s][1]=0;
}
int a,b=-1;
char a1;
a1=pre[0];
for(int i1=0;i1<more;i1++)
if(a1==in[i1])
{ result[i1][0]=1;
a=i1;
break;
}
for(int i=0 ;i<(more);i++)
{
for (int j=0;j<more;j++)
if(pre[i]==in[j] )
{b=j;
break;
}
if((b==0) || (b==(more -1)))
result[b][1]=1;
else
{if(result[b-1][1]==0 && result[b+1][1]==0)
result[b][1]=2;
else
result[b][1]=1;
}
}
return(a); } /*end shakhes*/
void flog(char pre[],char in[],int result[20][2],int more,int a) /*begin flog*/
{
int b=-1,h;
for(int i=1;i<more;i++)
{
for (int j=0;j<more;j++)
if(pre[i]==in[j] )
{b=j;
break;
}
for(int k=1;k<(more-1);k++)
if(result[k+1][0]!=0 && result[k-1][0]!=0)
result[k][1]=0;
if(b<a)
{h=-1;
for (int i1=b; 0 <=i1;i1--)
if(result[i1][0] != 0 && result[i1][1] != 0)
{result[b][0]=((result[i1][0]*2)+1);
result[i1][1]=(result[i1][1])-1;
h=0;
break;
}
if(h!=0)
{
for(int i2=b;i2<=a ;i2++)
if((result[i2][0] !=0) && (result[i2][1]!=0))
{result[b][0]=((result[i2][0])*2);
result[i2][1]=(result[i2][1])-1;
break;
}}
}
if(b>a)
{ result[b][0]=((result[a][0])*2)+1;
result[a][1]=(result[a][1])-1;
for(int k1=0;k1<=a;k1++)
result[k1][1]=0;
a=b;
}
}
return; } /*end flog */

void sort(char in[],int result[20][2],int more) /*begin sort*/
{int temp;char temp1;
for (int i=0;i<more-1;i++)
for (int j=0;j<more-1;j++)
if(result[j][0]>result[j+1][0])
{ temp = result[j][0];
result[j][0] = result[j+1][0];
result[j+1][0] = temp;
temp1=in[j];
in[j]=in[j+1];
in[j+1]=temp1;
}
}
void write(node *q)
{
if(q!=NULL)
{
cout<<"("<<q->info;
write(q->left);
cout<<",";
write(q->right);
cout<<")";
}
else
cout<<"NULL";
}
int _tmain(int argc, _TCHAR* argv[])
{
int a,more;
node *tree[20];
char pre[20];
char in[20];
int result[20][2];
int d;
cout<<"please enter number of node: ";
cin>>more;
add(pre,in,more);
a=shakhes(pre,in,result,more);
flog(pre,in,result,more,a);
sort(in,result,more);
for(int k=0;k<more;k++)
cout<<endl<<result[k][0]<<" "<<in[k];
for(int i=0;i<15;i++)
tree[i]=getnode();
for(int k=0;k<more;k++)
for(int i=0;i<15;i++)
if(result[k][0]==i+1)
tree[i]->info =in[k];
//write(tree[0]);
getch();
return 0;
}