二叉树层次遍历算法

自上而下，从左到右遍历自下而上，从右到左遍历

typedef struct BiTNode{ ElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree;

利用队列

#define MaxSize 30 typedef struct { ElemType data[MaxSize]; int front, rear; }SqQueue; //初始化队列 void InitQueue(SqQueue &Q){ Q.front = Q.rear = 0; } //判队列空 bool IsEmpty(SqQueue Q){ if（Q.rear==Q.front） return true; else return false; } //入队 bool EnQueue(SqQueue &Q, ElemType x){ if((Q.rear+1)%MaxSize==Q.front) //队满 return false; Q.data[Q.rear]=x; Q.rear=(Q.rear+1)%MaxSize; return true; } //出队 bool DeQueue(SqQueue &Q, ElemType &x){ if(IsEmpty) return false; x=Q.data[Q.front]; Q.front=(Q.front+1)%MaxSize; return true; }

自上而下，从左到右遍历

void LevelOrder(BiTree T){ InitQueue(Q); BiTree p; EnQueue(Q, T); //先将根结点入队 while(!IsEmpty(Q)){ DeQueue(Q, p); visit(p); //访问出队结点 if(p->lchild!=NULL) EnQueue(Q, p->lchild); //如果该出队结点左子树存在，则该左子树的根结点入队 if(p->rchild!=NULL) EnQueue(Q, p->rchild); //如果该出队结点右子树存在，则该右子树的根结点入队 } }

自下而上，从右到左遍历

其实就是将上面的层次遍历倒过来，可以将出队的元素依次入栈，然后再依次出栈。前一篇二叉树先中后序遍历算法里面已经写过栈，这里就不重复了

void LevelOrder2(BiTree T){ InitQueue(Q); InitStack(S); BiTree p; EnQueue(Q, T); while(!IsEmpty(Q)){ DeQueue(Q, p); Push(S, p); visit(p); if(p->lchild!=NULL) EnQueue(Q, p->lchild); if(p->rchild!=NULL) EnQueue(Q, p->rchild); } while(!IsEmpty(S)){ Pop(S, p); visit(p); } }