[C++知识库]二叉树的层序遍历（c语言版）

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

struct node 
{
 struct node *l,*r;//left child and right child
 int data;
};
//定义一个队列的节点
typedef struct dqueen
{
 struct dqueen *next;
 struct node *data;

}dqueen;
//队列的管理
typedef struct
{
 int size;
 dqueen *head,*tail;
}dqueenManager;
struct node* create_node(int data);
void load(struct node *root,struct node *leaf,int flag);
//先序遍历
void preorder(struct node *root);
void inorder(struct node *root);
void postorder(struct node *root);
dqueen* create_dqnode(void);
//层序遍历
void layerorder(dqueenManager *dm,struct node *root);
//入队列
void dqeen_in(dqueenManager *dm,struct node *root);
//出队列
dqueen* dqeen_out(dqueenManager *dm);


int main(void) 
{
 struct node* a=create_node(1);
 struct node* b=create_node(2);
 struct node* c=create_node(3);
 struct node* d=create_node(4);
 struct node* e=create_node(5);
 struct node* f=create_node(6);
 struct node* g=create_node(7);
 struct node* h=create_node(8);
 struct node* i=create_node(9);
 struct node* j=create_node(10);
 struct node* k=create_node(11);
 struct node* l=create_node(12);
 load(a,b,1);load(a,c,0);
 load(b,d,1);load(b,e,0);
 load(c,f,1);load(c,g,0);
 load(d,h,1);load(d,i,0);
 load(e,j,1);load(e,k,0);
 load(f,l,1);
 //创建队列的管理
 dqueenManager dm;
 dm.size=0;dm.head=NULL;dm.tail=NULL;
 dm.head=create_dqnode();
 dm.tail=create_dqnode();
 dm.head->next=dm.tail;
 dm.tail->next=dm.head;
 layerorder(&dm,a);
}

struct node* create_node(int data) 
{
 struct node* temp=malloc(sizeof(*temp));
 assert(temp!=NULL);
 temp->data=data;temp->l=NULL;temp->r=NULL;
 return temp;
}
void load(struct node *root,struct node *leaf,int flag) 
{
 assert(root!=NULL);assert(leaf!=NULL);
 if(flag){
  root->l=leaf;}else{root->r=leaf;}
}

void preorder(struct node *root)
{
 if(!root){return;}
 printf("%d ",root->data);
 preorder(root->l); preorder(root->r);
}
void inorder(struct node *root)
{
 if(!root){return;}inorder(root->l);printf("%d ",root->data);inorder(root->r);
}
void postorder(struct node *root)
{
 if(!root){return;}
 postorder(root->l);
 postorder(root->r);
 printf("%d ",root->data);
}
dqueen* create_dqnode(void)
{
 dqueen *t=NULL;
 t=malloc(sizeof(*t));
 assert(t!=NULL);
 t->next=NULL;t->data=NULL;
 return t;

}
void layerorder(dqueenManager *dm,struct node *root)
{
 assert(root !=NULL);
 //首次应该吧root添加进入队列
 dqeen_in(dm,root);
 dqueen *data=NULL;
 for(;;)
 {
  //先出队列，然后左右子树再次入队列
  data=dqeen_out(dm);
  printf("%d ",data->data->data);
  //左子树，右子树入队列
  if(data)
  {
   if(data->data->l){dqeen_in(dm,data->data->l);}
   if(data->data->r){dqeen_in(dm,data->data->r);}
  }
  //判断结束的条件
  if(dm->size ==0)
  {
   break;
  }
  //!!!free,data=NULL必须放到最后，否则，会出现想不到的bug哦，比如，数据打印不完全
  free(data);
  data=NULL;

 }//for

}
void dqeen_in(dqueenManager *dm,struct node *root)
{
 dqueen* t=create_dqnode();
 t->data=root;

 dqueen *pre = dm->tail->next;
 pre->next=t;
 dm->tail->next=t;
 t->next=dm->tail;
 dm->size++;
 return; 
}
dqueen* dqeen_out(dqueenManager *dm)
{
 if(dm->size == 0)
 {
  return NULL;
 }
 dqueen *temp=dm->head->next;
 dm->head->next=temp->next;
 if(dm->size==1)
 {
  dm->tail->next=dm->head;
 }
 dm->size--;
 return temp;

}

利用队列，对二叉树进行层序遍历，代码直接copy可以运行，无bug.
队列使用的链式队列，没有使用数组作为队列。

输出结果为：
1 2 3 4 5 6 7 8 9 10 11 12
上述也实现了前序、中序、后序遍历
函数的申明如下：

void preorder(struct node *root);
void inorder(struct node *root);
void postorder(struct node *root);