二叉树的建立

时间：2010-06-11 来源：returnx

已知二叉树的先序和中序构造二叉树. 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<n;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<n;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<distance/4*2;i++)
  {
   printf("\n");
  }
} while(tree_queue_pop(&t_queue));
}