二叉树层序遍历

时间：2009-07-21 来源：ubuntuer

    输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。例如输入
   8
/  \
6 10
  /\    /\
5  7 9  11
输出8 6 10 5 7 9 11。
分析：这曾是微软的一道面试题。这道题实质上是要求遍历一棵二元树，只不过不是我们熟悉的前序、中序或者后序遍历

曾是...现在这些都是小儿科了,也确实如果你连这个都写不出来,那就真要扪心自问了...这个work系列写了这么多,没有debug过的还真没有几题。这个就是其中之一

我这里的队列使用链表实现的

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 10

int count = 0;

typedef struct tree
{
  int num;
  struct tree* lchild;
  struct tree* rchild;
}TREE;

typedef struct queue
{
  TREE* tree;
  struct queue* next;
}QUEUE;

void init_queue(QUEUE** Q)
{
  *Q = (QUEUE*)malloc(sizeof(QUEUE));
  (*Q)->next = NULL;
}

void push_queue(QUEUE* Q, TREE* T)
{
  QUEUE* p = Q->next;
  QUEUE* q = Q;
  while(p!=NULL)
   {
     q = p;
     p = p->next;
    }
  p = (QUEUE*)malloc(sizeof(QUEUE));
  p->tree = T;
  p->next = NULL;
  q->next = p;
}

TREE* pop_queue(QUEUE* Q)
{
  QUEUE* p = Q->next;
  TREE* ret;
  if(p==NULL)
    return NULL;
  else
   {
    Q->next = p->next;
    ret = p->tree;
    free(p);
   }
   return ret;
}

void add_tree(TREE** T, int num)
{
  if(*T == NULL)
   {
     *T = (TREE*)malloc(sizeof(TREE));
     (*T)->num = num;
     (*T)->lchild = NULL;
     (*T)->rchild = NULL;
   }
  else if((*T)->num < num)
    add_tree(&((*T)->rchild), num);
  else
    add_tree(&((*T)->lchild), num);
}

void mid_walk_tree(TREE* T)
{
  if(T!=NULL)
   {
     mid_walk_tree(T->lchild);
     if(++count%5 == 0)
       printf("%d\n",T->num);
     else
       printf("%d\t",T->num);

     mid_walk_tree(T->rchild);
   }
}

void layer_walk(TREE* T,QUEUE* Q)
{
  if(T==NULL)
    return;

  if(++count%5 == 0)
    printf("%d\n",T->num);
  else
    printf("%d\t",T->num);

  if(T->lchild!=NULL)
    push_queue( Q, T->lchild);

  if(T->rchild!=NULL)
    push_queue( Q, T->rchild);

  T = pop_queue(Q);
  layer_walk( T, Q);
}

int main(int argc, char *argv[])
{
  int i = 0;
  int num;
  TREE* T = NULL;
  QUEUE* Q = NULL;

  srand((unsigned)time(NULL));

  for(; i<N; i++)
   {
     num = rand()%100+1;
     add_tree(&T, num);
   }

  printf("mid walk is:\n");
  mid_walk_tree(T);

  count = 0;
  init_queue(&Q);

  printf("layer walk is:\n");
  layer_walk(T,Q);
  free(Q);
  Q=NULL;

  system("PAUSE");
  return 0;
}