二叉树的建立

已知二叉树的先序和中序构造二叉树.

struct bin_tree_node
{
 struct bin_tree_node *l;
 struct bin_tree_node *r;
 int data;
};

void create_bin_tree(struct bin_tree_node** root)
{
 char c;
 if( (c=getchar())==' ')
  *root=NULL;
 else
 {
  *root=(struct bin_tree_node*)malloc(sizeof(struct bin_tree_node));
  (*root)->data=c;
  create_bin_tree(&(*root)->l);
  create_bin_tree(&(*root)->r);
 }
}

void traversal_bin_tree(struct bin_tree_node * root,int n)
{
 if ( root)
 {
  int i;
  for (i=0;i  {
   printf(" ");
  }
  printf("%c\n",root->data);
  traversal_bin_tree(root->l,n+1);
  traversal_bin_tree(root->r,n+1);
 }
}

char before_order[] ={"abcdefghij"};
char mid_order[] ={"cdbfeaihgj"};

void create_bin_tree_of_input(struct bin_tree_node ** root,char before[],char mid[],int n)
{
 if (n==0)
 {
  *root=NULL;
 }
 else
 {
  int i;
  *root=(struct bin_tree_node*)malloc(sizeof(struct bin_tree_node));
  (*root)->data=before[0];
  for (i=0;i  {
   if (mid[i]==before[0])
   {
    break;
   }
  }
  create_bin_tree_of_input(&(*root)->l,before+1,mid,i);
  create_bin_tree_of_input(&(*root)->r,before+1+i,mid+1+i,n-i-1);
 }
}

int main(int argc,char* argv[])
{
 struct bin_tree_node * root=NULL;
 create_bin_tree_of_input(&root,before_order,mid_order,sizeof(before_order));
 traversal_bin_tree(root,0);
 getchar();
 getchar();
 return;
}

 

//按层次打印二叉树

//按层次遍历二叉树。
struct node_queue
{
 struct node_queue * next;
 struct bin_tree_node * t_node;
};
struct tree_queue
{
 struct node_queue head;
 struct node_queue * tail;
};

void tree_queue_init(struct tree_queue * q_tree)
{
 q_tree->head.next=NULL;
 q_tree->tail=&q_tree->head;
}

void tree_queue_push(struct tree_queue * q_tree,struct bin_tree_node * t_node)
{
 struct node_queue * nd=(struct node_queue*)malloc(sizeof(struct node_queue));
 nd->next=NULL;
 nd->t_node=t_node;

 q_tree->tail->next=nd;
 q_tree->tail=nd;
}

struct bin_tree_node * tree_queue_pop(struct tree_queue * q_tree)
{
 struct bin_tree_node * ret;
 struct node_queue * del;
 if (q_tree->head.next==NULL)
 {
  return NULL;
 }

 del=q_tree->head.next;
 ret=del->t_node;
 q_tree->head.next=del->next;
 free(del);
 if (q_tree->head.next==NULL)
 {
  q_tree->tail=&q_tree->head;
 }
 return ret;
}

void dump_tree(struct bin_tree_node * tree)
{
 struct tree_queue t_queue;
 struct bin_tree_node * tree_node;
 int distance=64;
 tree_queue_init(&t_queue);
 tree_queue_push(&t_queue,tree);
 tree_queue_push(&t_queue,0xFFFFFFFF);

 while (1)
 {
  int tag=0,i;
  for (i=0;i<0+distance;i++)
  {
   printf(" ");
  }

  while (1)
  {
   tree_node=tree_queue_pop(&t_queue);
   
   if (tree_node==0xffffffff)
   {
    break;
   }
   
   if ( tree_node==NULL)
   {
    printf("^");
   }
   else
   {
    tag=1;
    //printf("\033[31m%d\033[m",tree_node->data);
    printf("%c",tree_node->data);
   }
   for(i=0;i<2*distance-1;i++)
    printf(" ");

   if (tree_node)
   {
    
    tree_queue_push(&t_queue,tree_node->l);
    tree_queue_push(&t_queue,tree_node->r);
   }
   else
   {
    tree_queue_push(&t_queue,0);
    tree_queue_push(&t_queue,0);
   }
  }
  printf("\n");
  if ( tag ==0)
  {
   break;
  }
  tree_queue_push(&t_queue,0xFFFFFFFF);

  distance/=2;

  for (i=0;i  {
   printf("\n");
  }
 }

 while(tree_queue_pop(&t_queue));
}