Pastebin.vip

Linearization of binary tree

From , 3 Years ago, written in C, viewed 214 times.
URL https://pastebin.vip/view/ab8aa05e
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. struct node {
  4.         int data;
  5.         struct node *lh,*rh;
  6.         int ltag,rtag;
  7. }*pr,*t,*s[30];
  8.  
  9. struct node* creat() {
  10.         struct node *t,*q;
  11.         int i,x,j;
  12.         printf ( "i,x=" );
  13.         scanf ( "%d%d",&i,&x );
  14.         while ( ( i!=0 ) && ( x!=0 ) ) {
  15.                 q= ( struct node * ) malloc ( sizeof ( struct node ) );
  16.                 q->data=x;
  17.                 q->lh=NULL;
  18.                 q->rh=NULL;
  19.                 s[i ]=q;
  20.                 if ( i==1 )
  21.                         t=q;
  22.                 else {
  23.                         j=i/2;
  24.                         if ( ( i%2 ) ==0 )
  25.                                 s[j]->lh=q;
  26.                         else
  27.                                 s[j]->rh=q;
  28.                 }
  29.                 printf ( "i,x=" );
  30.                 scanf ( "%d%d",&i,&x );
  31.         }
  32.         return ( t );
  33. }
  34.  
  35. /*void inthread(struct node *p) //递归算法
  36. {
  37.         if(p!=NULL)
  38.         {
  39.                 inthread(p->lh);
  40.                 printf("%6d\t",p->data);
  41.                 if(p->lh!=NULL)
  42.                         p->ltag=0;
  43.                 else
  44.                 {
  45.                         p->ltag=1;
  46.                         p->lh=pr;
  47.                 } //建立P节点的左线索，指向前趋节点PR
  48.                 if(pr!=NULL)
  49.                 {
  50.                         if(pr->rh!=NULL)
  51.                                 pr->rtag=0;
  52.                         else
  53.                         {
  54.                                 pr->rtag=1;
  55.                                 pr->rh=p;
  56.                         }//前趋节点PR建立左线索，指向节点P
  57.                 }
  58.                 pr=p;//pr跟上p,以便p向后移动
  59.                 inthread(p->rh);
  60.         }
  61. }*/
  62.  
  63. void inthread ( struct node *t ) { //非递归算法
  64.         int top,bools;
  65.         struct node *p;
  66.         pr=NULL;
  67.         p=t;
  68.         top=0;
  69.         bools=1;
  70.         do {
  71.                 while ( p!=NULL ) {
  72.                         top++;
  73.                         s[top]=p;
  74.                         p=p->lh;
  75.                 }
  76.                 if ( top==0 ) bools=0;
  77.                 else {
  78.                         p=s[top];
  79.                         top--;
  80.                         printf ( "%6d",p->data );
  81.                         if ( p->lh!=NULL )
  82.                                 p->ltag=0;
  83.                         else {
  84.                                 p->ltag=1;
  85.                                 p->lh=pr;
  86.                         } //建立P节点的左线索，指向前趋节点PR
  87.                         if ( pr!=NULL ) {
  88.                                 if ( pr->rh!=NULL )
  89.                                         pr->rtag=0;
  90.                                 else {
  91.                                         pr->rtag=1;
  92.                                         pr->rh=p;
  93.                                 }//前趋节点PR建立左线索，指向节点P
  94.                         }
  95.                         pr=p;//pr跟上p,以便p向后移动
  96.                         p=p->rh;
  97.                 }//END else
  98.         } while ( bools );
  99.         pr->rh=NULL;
  100. }
  101.  
  102. main() {
  103.         pr=NULL;
  104.         t=creat();
  105.         inthread ( t );
  106.         pr->rh=NULL;
  107. }

Reply to "Linearization of binary tree"

Here you can reply to the paste above

captcha

https://burned.cc - Burn After Reading Website
Powered by Pastebin.vip paste tool since 2022!