۰
subtitle
ارسال: #۱
[نکات] تکمیلی BST , Heap,Graph دنباله ساختمان داده
به زودی راه اندازی می شود
شما هم، هر کمکی تونستید، دریغ نکنید
شما هم، هر کمکی تونستید، دریغ نکنید
(۱۰ آذر ۱۳۸۹ ۰۹:۳۹ ب.ظ)Masoud05 نوشته شده توسط: ادغام ۲ هیپ که جمعاً n عنصر دارد از مرتبه(O(n هست.
(۰۷ دى ۱۳۸۹ ۱۲:۰۴ ق.ظ)afagh1389 نوشته شده توسط: نکته مهم ولی ساده از min-heap برای استخراج متوالی minها , از max heap برای استخراج متوالی maxها استفاده میشود و heap در امر جستجو کارایی ندارد!خود هیپ به تنهایی معنی نداره، در واقع هرگاه اسم هیپ میاد منظور یکی از این ۲ حالت بیشینه و یا کمینه هست . برای مرتب سازی هم در ارسال ۷ توضیح داده شده
نقل قول: جستجوی کلید در درخت دودویی
کد:
void search ( node _ pointer tree ,
keytype keyin,
node _ poiner & p)
{
bool found ;
p = tree;
found = false;
while (! found)
if ( p - > key == keyin )
found = true ;
else if ( keyin < p - > key )
p = p -> left ;
else
p = p - > right ;
}
نقل قول: تعیین یک درخت جست وجوی بهینه برای مجموعه ای از کلید ها، هر یک با احتمالی مشخص
کد:
void optsearchtree ( int n ,
const float p[];
float & minavg,
index R[][])
{
index i , j , k , diagonal ;
float A [1..n + 1] [0..n];
for ( i = 1 ; i ≤ n ; i ++) {
A [i] [i -1] = 0
A [i] [i] = p [i];
R [i] [i] = i ;
R [i] [ i – ۱ ] = ۰;
}
A[ n + 1 ] [n] = 0 ;
R[ n + 1 ] [n] = 0 ;
for (diagonal = 1;diagonal ≤ n – ۱; diagonal++)
for ( i = 1; i ≤ n – diagonal ; i ++) {
j = i + diagonal ;
A[i][j] = minimum(A[i][k-1]+A[k+1][j])+∑pm
R[i][j] = a value of k that gave the minimum;
}
minavg = A [1][n];
}
نقل قول: ساخت درخت جست و جوی دودویی بهینه
کد:
node _ pointer tree ( index i , j )
{
index k ;
node _ pointer p ;
k = R [i] [j];
if ( k == 0 )
return NULL;
else {
p = new nodetype ;
p - > key = key [k] ;
p - > left = tree (i , k – ۱);
p - > right = tree ( k+1 , j);
return P;
}
}
نقل قول: تابع پیمایش Inorder
کد:
void inOrder(BinaryTreeNode *t)
{
if (t != null)
{
inOrder(t -> leftChild);
cout << t -> data; // Visit = Print
inOrder(t -> rightChild);
}
}
نقل قول: تابع پیمایشPreorder
کد:
void preOrder(BinaryTreeNode *t)
{
if (t != null)
{
cout << t -> data; // Visit = Print
preOrder(t -> leftChild);
preOrder(t -> rightChild);
}
}
نقل قول: تابع پیمایشPostorder
کد:
void postOrder(BinaryTreeNode *t)
{
if (t != null)
{
postOrder(t -> leftChild);
postOrder(t -> rightChild);
cout << t -> data; // Visit = Print
}
}