首页 > 代码库 > 树的层序遍历:

树的层序遍历:

层次遍历:即每一层从左向右输出

元素需要储存有先进先出的特性,所以选用队列存储。

队列的定义:

 
  1. #define MAX 1000  
  2.   
  3. typedef struct seqqueue{  
  4.     bintree data[MAX];  
  5.     int front;  
  6.     int rear;  
  7. }seqqueue;  
  8.   
  9.   
  10. void enter(seqqueue *q,bintree t){  
  11.     if(q->rear == MAX){  
  12.         printf("the queue is full!\n");  
  13.     }else{  
  14.         q->data[q->rear] = t;  
  15.         q->rear++;  
  16.     }  
  17. }  
  18.   
  19. bintree del(seqqueue *q){  
  20.     if(q->front == q->rear){  
  21.         return NULL;  
  22.     }else{  
  23.         q->front++;  
  24.         return q->data[q->front-1];  
  25.     }  
  26. }  


遍历实现 :

 
    1. void level_tree(bintree t){  
    2.     seqqueue q;  
    3.     bintree temp;  
    4.     q.front = q.rear = 0;  
    5.     if(!t){  
    6.         printf("the tree is empty\n");  
    7.         return ;  
    8.     }  
    9.     enter(&q,t);  
    10.     while(q.front != q.rear){  
    11.         t=del(&q);  
    12.         printf("%c ",t->data);  
    13.         if(t->lchild){  
    14.             enter(&q,t->lchild);  
    15.         }  
    16.         if(t->rchild){  
    17.             enter(&q,t->rchild);  
    18.         }  
    19.     }  
    20. }  

树的层序遍历: