PDA

View Full Version : ایجاد یک درخت کامل با استفاده از اشاره گرها



احمد کرک
جمعه 21 بهمن 1384, 18:00 عصر
طریقه ایجاد یک درخت کامل با استفاده از اشاره گرها (درج گره از چپ به راست)
به چه طریق می توان راست ترین گره را پیدا کرد.
درخت کامل با استفاده از آرایه بسیار ساده است اما در لیستهای پیوندی با مشکل مواجه هستم.
خواهشمندم در این مورد راهنمایی فرمایید.

bahman_asham
سه شنبه 09 اسفند 1384, 19:35 عصر
/************************************************** *************************/
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <ctype.h>
#include <string.h>
#define TRUE 1
/************************************************** **************************/
void input ();
int menu_select();
void maketree(struct tree *);
void delet(struct tree * , int );
void find (struct tree *);
void inorder (struct tree *s);
void preorder (struct tree *s);
void postorder (struct tree *s);
/************************************************** **************************/
struct tree {
struct tree *left ;
char name[20] ;
int number ;
struct tree *right ;
} ;
struct tree *start , *node ;
char pname[20] ;
/************************************************** **************************/
int main (void)
{

textcolor(2);
textbackground(9);
int n;
start = NULL ;
while (TRUE) {
switch(menu_select()) {
case 1:
clrscr();
input() ;
break ;
case 2:
clrscr();
gotoxy(26,20) ;
printf("s) enter name for search:");
gets(pname) ;
find(start);
getch() ;
break ;
case 3:
clrscr();
printf("\n inorder print of information\n");
gotoxy(6,4) ;
printf(" name number");
gotoxy(6,5) ;
printf("************* *******");
inorder(start) ;
printf("\n press a key to continue ..") ;
getch() ;
break ;
case 4:
clrscr() ;
printf("\n preorder print of information\n");
gotoxy(6,4) ;
printf(" name number");
gotoxy(6,5) ;
printf("************* *******");
preorder(start) ;
printf("\n press a key to continue ") ;
getch() ;
break ;
case 5:
clrscr() ;
printf("\n postorder print of information\n");
gotoxy(6,4) ;
printf(" name number");
gotoxy(6,5) ;
printf("************* *******");
postorder(start) ;
printf("\n press a key to continue ..") ;
getch() ;
break ;

case 6:
clrscr();
gotoxy(27,20);
printf("enter element:");
scanf("%d",&n);
delet(start,n);
break;
case 7:
exit(0) ;
break;

}
}
}
/************************************************** **************************/
void input ()
{
int i ;
char numstr[10] ;
clrscr() ;
gotoxy(4, 3) ;
printf(" name number \n");
gotoxy(4,4) ;
printf("************* ******* ");
i = 5 ;
while (TRUE) {
node = (struct tree *) malloc(sizeof(struct tree)) ;
node -> left = NULL ;
node -> right = NULL ;
gotoxy(4, i) ;
gets(node -> name) ;
if(!node -> name[0]) {
gotoxy(5,i + 2) ;
printf("press a key to continue ..");
getch() ;
break ;
}
gotoxy(23,i) ;
gets(numstr) ;
node -> number = atoi(numstr) ;
if (start == NULL)
start = node ;
else
maketree(start) ;
i++ ;
}
}
/************************************************** **************************/
int menu_select()
{
int choice ;
char s[5] ;
clrscr() ;
gotoxy(18, 4) ;
printf("1) enter the elements in tree.");
gotoxy(19, 6) ;
printf("2) search for elements in tree.");
gotoxy(20, 8) ;
printf("3) inorder print of information. ") ;
gotoxy(21,10) ;
printf("4) preorder print of information. ") ;
gotoxy(22,12) ;
printf("5) postorder print of information. ") ;
gotoxy(23,14) ;
printf("6) delete elements of tree. ") ;
gotoxy(24,16) ;
printf("7) quit from bahman asham program. ") ;
do {
gotoxy(25, 18) ;
printf("s) Enter your select(1-7) :");
gets(s) ;
choice = atoi(s) ;
} while (choice < 0 || choice > 7);
return choice ;
}
/************************************************** **************************/
void maketree(struct tree *top)
{
struct tree *help ;
help = top ;
while (help != NULL)
{
if(node ->number>help ->number)
{
if (help -> right != NULL)
help = help -> right ;
else {
help -> right=node ;
break ;
}
}
else {
if (help -> left != NULL )
help = help -> left ;
else {
help -> left=node ;
break ;
}
}
}
}
/************************************************** **************************/
void find (struct tree *s)
{
if (s == NULL)
{
return ;
}
find(s -> left) ;
if (strcmp(s -> name, pname) == 0) {
gotoxy(27,22);
printf("r) %s number is:", pname);
printf(" %d",s -> number) ;
return ;
}
find(s -> right) ;
}
/************************************************** **************************/
void inorder (struct tree *s)
{
if (s == NULL)
return ;
inorder(s -> left) ;
printf("\n %s", s -> name) ;
printf("\t\t\t %d", s -> number);
inorder(s -> right) ;
}
/************************************************** **************************/
void preorder (struct tree *s)
{
if (s == NULL)
return ;
printf("\n %s", s -> name) ;
printf("\t\t\t %d", s -> number) ;
preorder(s -> left) ;
preorder(s -> right) ;
}
/************************************************** **************************/
void postorder (struct tree *s)
{
if (s == NULL)
return ;
postorder(s -> left) ;
postorder(s -> right) ;
printf("\n%s", s -> name) ;
printf("\t\t\t %d", s -> number);
}
/************************************************** **************************/
void delet(struct tree *root,int t)
{
struct tree *temp,*temp1,*temp2,*temp3,*temp4;
int found,end;
temp=root;
temp1=temp;
temp2=temp3;
temp3=temp4;
while(!found && !end)
{
if (temp->left->number==t)
{
temp1=temp;
temp2=temp->left;
found=1;
}
if (temp->right->number==t)
{
temp1=temp;
temp2=temp->right;
found=1;
}
if (temp->number>t) temp=temp->left;
if (temp->number<t) temp=temp->right;
if (temp==NULL) end=1;
}
if (found)
{
if (temp2->right!=NULL)
{
temp4=temp1;
temp3=temp1->right;
while (temp->left!=NULL)
{
temp4=temp3;
temp3=temp3->left;
}
temp2->number=temp3->number;
strcpy(temp2->name,temp3->name);
temp4->left=NULL;
}
else
{
temp4=temp1;
temp3=temp2->left;
while (temp3->right!=NULL)
{
temp4=temp3;
temp3=temp3->right;
}
temp2->number=temp3->number;
strcpy(temp2->name,temp3->name);
temp4->right=NULL;
}}

else


printf("not found");

}
/************************************************** **************************/

bahman_asham
سه شنبه 09 اسفند 1384, 19:36 عصر
ممنونم دوست گرامی

Sepidar
سه شنبه 09 اسفند 1384, 20:20 عصر
لطفا از تگ کد استفاده کنید
ممنون

amir683
دوشنبه 01 خرداد 1385, 16:06 عصر
salam mamnon misham age lotf konid shekle graphicie in barnamaro vasam benevisin