#include #include #include #include #include using namespace std; #define max 10 struct btreenode { struct btreenode *leftchild ; int data ; struct btreenode *rightchild ; } ; struct stack { struct btreenode *addr; struct stack *next; } ; struct endlist{ struct btreenode *pr; struct btreenode *next ; }; struct btreenode *insert ( struct btreenode **,struct stack **lt, int ) ; void stackad(struct stack **lt,struct btreenode *bt); void delstack(struct stack *lt); struct btreenode *popestack(struct stack **lt); void inorder ( struct btreenode * ) ; void swap(struct btreenode **bt); int lastleaf(struct btreenode **bt); int main() { srand(time(0)); struct btreenode *bt; bt=NULL ; struct stack *lt; lt=NULL ; struct endlist *el; el=NULL ; int a[max]; for(int i=0;i<10;i++){ a[i]=pow(-1,rand())*(rand()%100); } printf("The list befor a sorting:\n"); for(int i=0;i<10;i++) printf("%d ",a[i]); printf("\n"); for ( int i = 0 ; i < max ; i++ ) { stackad(<,insert ( &bt, <, a[i] ) ); int k=0; do{ k++; }while (pow(2,k)<=i+1); for(int j=0;j<=k;j++){ swap (&bt); } //swap(&bt); // inorder (bt); // printf ("\n+++++++\n"); } //swap (&bt); //printf ( "\nIn-order traversal of binary tree:\n" ) ; // inorder ( bt ) ; for (int z=max -1;z>=0;z--){ a[z]= bt->data; bt->data=-1000; int k=0; do{ k++; }while (pow(2,k)<=z+1); for(int y=0;y<=k;y++) swap (&bt); inorder (bt); printf ("\n++++++++++++++\n"); } printf("The list after a sorting:\n"); for(int i=0;i<10;i++) printf("%d ",a[i]); printf("\n"); return 0; } struct btreenode *insert ( struct btreenode **sr,struct stack **lt, int num ) { if ( *sr == NULL ) { *sr =(btreenode *) malloc ( sizeof ( struct btreenode ) ) ; ( *sr ) -> leftchild = NULL ; ( *sr ) -> data = num ; ( *sr ) -> rightchild = NULL ; return *sr; } else { struct btreenode *temp ; temp =popestack(&(*lt)); if ( temp -> leftchild == NULL && temp -> rightchild == NULL ) { stackad(&(*lt),insert ( &(temp -> leftchild) ,lt, num )) ; //return temp -> leftchild ; } else if( temp -> rightchild == NULL ) { stackad(&(*lt),insert ( &( temp -> rightchild ),lt, num )) ; popestack(lt); } } } void swap(struct btreenode **bt){ if(*bt == NULL/* || (*bt) ->leftchild ==NULL*/){ return ; } else { if((*bt)->leftchild !=NULL && (*bt)->data < ((*bt)->leftchild)->data) { int temp=(*bt) ->data; (*bt)->data = ((*bt)->leftchild)->data; ((*bt)->leftchild)->data=temp ; printf ("\ntemp=%d,next=%d\n",temp ,(*bt)->data ); swap (&((*bt)->leftchild )); swap (&((*bt)->rightchild )); } if((*bt)->rightchild !=NULL &&(*bt)->data < ((*bt)->rightchild )->data ) { int temp=(*bt) ->data; (*bt)->data = ((*bt)->rightchild )->data; ((*bt)->rightchild )->data=temp ; swap (&((*bt)->leftchild) ); swap (&((*bt)->rightchild )); } swap (&((*bt)->leftchild) ); swap (&((*bt)->rightchild )); } } void stackad(struct stack **lt,struct btreenode *bt){ if( *lt == NULL ) { *lt =(stack *) malloc ( sizeof ( struct stack ) ) ; ( *lt) -> addr = bt ; ( *lt ) -> next = NULL ; } else stackad(&((*lt)->next) ,bt); } void delstack (struct stack **lt){ struct stack *temp; temp=*lt; *lt=(*lt)->next ; // free(temp ); } struct btreenode *popestack(struct stack **lt){ struct btreenode *temp ; temp =(*lt) ->addr ; if(temp->leftchild != NULL && temp->rightchild !=NULL ) delstack (&(*lt)); temp=(*lt) ->addr ; return temp ; } void inorder ( struct btreenode *sr ) { if ( sr != NULL ) { //inorder ( sr -> leftchild ) ; printf ( "%d ", sr -> data ) ; if(sr->leftchild !=0) printf ( "l->%d ", (sr -> leftchild) -> data); else printf ("l->0"); if(sr->rightchild !=0) printf ( "r->%d ", (sr -> rightchild) -> data); else printf ("r->0"); printf ("\n"); inorder ( sr -> leftchild ) ; inorder ( sr -> rightchild ) ; } } int lastleaf (struct btreenode **bt){ int temp ; if((*bt)->leftchild ==NULL ) { temp =(*bt) ->data ; free(&bt); return temp ; } else { lastleaf (&((*bt)->leftchild )) ; if((*bt)->rightchild != NULL ) lastleaf (&((*bt)->rightchild) ); } }

binary tree sort