PDA

View Full Version : کمک در مورد درخت جستجوی بهینه دودویی



aliexo
پنج شنبه 12 خرداد 1390, 11:12 صبح
سلام
من هرچی اینترنتو گشتم هیچی راجع به درخت جستجوی بهینه دودویی پیدا نکردم به زبان ++C یا C
هرچی بود جاوا بود
می خواستم ببینم کسی سایتی میشناسه معرفی کنه یا اینکه خودش داشته باشه که بتونه کمکم کنه؟
اگه خوده درختهای قابل تشکیل رو هم نشوون بده یا ترسیم کنه عالی میشه ، چون واقعا استاده ما نتونست درست توضیح بده و من دوست دارم بدونم

quiet_programmer
پنج شنبه 12 خرداد 1390, 18:25 عصر
باسلام.

برو کتاب ساختمان دادها به زبان سی نوشته هووریتز رو مطالعه کن هم کد داره و هم توضیح.
در ضمن قرار نیست که همه چی رو استاد بگه. «البته این نظر من بود و به خودم این نکته رو یادآوری کردم»
دانش+جو=دانشجو

موفق باشی.

هم دانشگاهی
جمعه 13 خرداد 1390, 22:31 عصر
سلام !

این کد کتاب طراحی الگوریتم نیپولیتان هستش :

اول دو تا آرایه R و A رو تشکیل میدی بعد به کمک عنصر R[1][n]
درخت رو درست میکنی :

#include <iostream>
#include <stdio.h>
#include <windows.h>
#include <conio.h>
using namespace std;
/************************************************** ****************************/
void gotoxy(int x,int y)
{
COORD pos;
pos.X=x; pos.Y=y; SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_H ANDLE),pos);
}
/************************************************** ****************************/
struct node
{
char name[20];
node *left;
node *right;
};
int n=4;
float R[6][5];
float A[6][5];
char NAME[5][20] = { "" , "DON" , "ISABELLE" , "RALPH", "WALLY"};
float P[5] = {0 , 0.375 , 0.375 , 0.125 , 0.125};
/************************************************** ****************************/
void show(float a[6][5])
{
for(int i=1;i<=n+1;i++)
{
for(int j=0;j<=n;j++)
printf("%3.3f ",a[i][j]);
cout<<endl;
}
cout<<"-----------------------\n";
getch();
}
/************************************************** ****************************/
void opt(int n , const float P[] , float &minave)
{
int i,j,m,k,diagonal;
float sum,min;
for(i=1;i<=n;i++)
{
A[i][i-1]=0;
A[i][i]=P[i];
R[i][i-1]=0;
R[i][i]=i;
}
A[n+1][n]=0;
R[n+1][n]=0;
for(diagonal=1;diagonal<=n-1;diagonal++)
for(i=1;i<=n-diagonal;i++)
{
j=i+diagonal;
sum=0;
for(m=i;m<=j;m++)
sum+=P[m];
A[i][j]=A[i][i-1]+A[i+1][j]+sum;
R[i][j]=i;
for(k=i;k<=j;k++)
{
min=A[i][k-1]+A[k+1][j]+sum;
if(min<A[i][j])
{
A[i][j]=min;
R[i][j]=k;
}
}
}
show(A);
show(R);
minave=A[1][n];
}
/************************************************** ****************************/
node* tree(int i , int j , int x , int y)
{
int k;
node *p;
k= (int) R[i][j];
if(k==0)
return 0;
else
{
p=new node;
strcpy(p->name,NAME[k]);
gotoxy(x,y); cout<<p->name;
y+=2;
p->left = tree(i,k-1,x,y);
x+=10;
p->right = tree(k+1,j,x,y);
return p;
}
}
/************************************************** ****************************/
int main()
{
for(int i=0;i<6;i++)
for(int j=0;j<5;j++)
A[i][j]=R[i][j]=0;
float z;
float &minave=z;
opt(n,P,minave);
system("cls");
tree(1,n,0,0);
getch();
return 0;
}


در ضمن موقع چاپ اون ماتریس اولی A و دومی R هست !

امیدوارم مفید باشه