1 #include <stdio.h> 2 #include <stdlib.h> 3 #define MAX  10 4  5  6 //二叉树存储结构定义 7 typedef char Item; 8 typedef struct node *link; 9 struct node {Item item; link l, r;};10 11 int  Create(link *tp);12 void show(link h);13 void tranverse(link h, void (*visit)(link));14 15 //队列存储结构定义16 typedef link QItem;17 static QItem *q;18 static int    N, head, tail;19 20 void  QUEUEinit(int maxN);21 int   QUEUEempty();22 void  QUEUEput(QItem item);23 QItem QUEUEget();24 25 26 int main()27 {28     link tree;29 30     Create(&tree);31     tranverse(tree, show);32 33     return 0;34 }35 36 void QUEUEinit(int maxN)37 {38     q = (QItem *)malloc(maxN * sizeof(QItem));39     if (!q) return;40     N = maxN + 1; head = N; tail = 0;41 }42 43 int QUEUEempty()44 {45     return head % N == tail;46 }47 48 void QUEUEput(QItem item)49 {50     q[tail++] = item;51     tail = tail % N;52 }53 54 QItem QUEUEget()55 {56     head = head % N;57     return q[head++];58 }59 60 int Create(link *tp)61 {62     //构造方法，或者说构造顺序：中序遍历构造63     char x;64     scanf("%c",&x);65     if(x==‘#‘)66     {67         *tp=NULL;//指针为空，树节点中的某个指针为空68         return 0;69     }70     *tp=(link)malloc(sizeof(**tp));//将树节点中指针指向该地址空间71     if(*tp==NULL)72         return 0;73     (*tp)->item=x;74     Create(&((*tp)->l));75     Create(&((*tp)->r));76     return 1;77 }78 79 void show(link h)80 {81     printf(" %c ", h->item);82 }83 84 //层序遍历85 void tranverse(link h, void (*visit)(link))86 {87     QUEUEinit(MAX); QUEUEput(h);88     while (!QUEUEempty()){89         (*visit)(h = QUEUEget());90         if (h->l != NULL) QUEUEput(h->l);91         if (h->r != NULL) QUEUEput(h->r);92     }93 }