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



/**************************************************  *************************/

#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");



}

/**************************************************  **************************/