【思路】：按从顶向下，从左至右的顺序来逐层訪问每一个节点，层次遍历的过程中须要用队列。
//层次遍历 void LevelOrder(BiTree T){ BiTree p = T; //队列 queue<BiTree> queue; //根节点入队 queue.push(p); //队列不空循环 while(!queue.empty()){ //对头元素出队 p = queue.front(); //訪问p指向的结点 printf("%c ",p->data); //退出队列 queue.pop(); //左子树不空，将左子树入队 if(p->lchild != NULL){ queue.push(p->lchild); } //右子树不空，将右子树入队 if(p->rchild != NULL){ queue.push(p->rchild); } } }測试用例：
输入：
ABC##DE#G##F###
输出：
代码：
#include<iostream> #include<stack> #include<queue> using namespace std; //二叉树结点 typedef struct BiTNode{ //数据 char data; //左右孩子指针 struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //按先序序列创建二叉树 int CreateBiTree(BiTree &T){ char data; //按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树 scanf("%c",&data); if(data == \'#\'){ T = NULL; } else{ T = (BiTree)malloc(sizeof(BiTNode)); //生成根结点 T->data = data; //构造左子树 CreateBiTree(T->lchild); //构造右子树 CreateBiTree(T->rchild); } return 0; } //输出 void Visit(BiTree T){ if(T->data != \'#\'){ printf("%c ",T->data); } } //先序遍历 void PreOrder(BiTree T){ if(T != NULL){ //訪问根节点 Visit(T); //訪问左子结点 PreOrder(T->lchild); //訪问右子结点 PreOrder(T->rchild); } } //中序遍历 void InOrder(BiTree T){ if(T != NULL){ //訪问左子结点 InOrder(T->lchild); //訪问根节点 Visit(T); //訪问右子结点 InOrder(T->rchild); } } //后序遍历 void PostOrder(BiTree T){ if(T != NULL){ //訪问左子结点 PostOrder(T->lchild); //訪问右子结点 PostOrder(T->rchild); //訪问根节点 Visit(T); } } /* 先序遍历(非递归) 思路：訪问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。 */ void PreOrder2(BiTree T){ stack<BiTree> stack; //p是遍历指针 BiTree p = T; //栈不空或者p不空时循环 while(p || !stack.empty()){ if(p != NULL){ //存入栈中 stack.push(p); //訪问根节点 printf("%c ",p->data); //遍历左子树 p = p->lchild; } else{ //退栈 p = stack.top(); stack.pop(); //訪问右子树 p = p->rchild; } }//while } /* 中序遍历(非递归) 思路：T是要遍历树的根指针，中序遍历要求在遍历完左子树后，訪问根，再遍历右子树。 先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，訪问T->data，再中序遍历T的右子树。 */ void InOrder2(BiTree T){ stack<BiTree> stack; //p是遍历指针 BiTree p = T; //栈不空或者p不空时循环 while(p || !stack.empty()){ if(p != NULL){ //存入栈中 stack.push(p); //遍历左子树 p = p->lchild; } else{ //退栈，訪问根节点 p = stack.top(); printf("%c ",p->data); stack.pop(); //訪问右子树 p = p->rchild; } }//while } //后序遍历(非递归) typedef struct BiTNodePost{ BiTree biTree; char tag; }BiTNodePost,*BiTreePost; void PostOrder2(BiTree T){ stack<BiTreePost> stack; //p是遍历指针 BiTree p = T; BiTreePost BT; //栈不空或者p不空时循环 while(p != NULL || !stack.empty()){ //遍历左子树 while(p != NULL){ BT = (BiTreePost)malloc(sizeof(BiTNodePost)); BT->biTree = p; //訪问过左子树 BT->tag = \'L\'; stack.push(BT); p = p->lchild; } //左右子树訪问完成訪问根节点 while(!stack.empty() && (stack.top())->tag == \'R\'){ BT = stack.top(); //退栈 stack.pop(); BT->biTree; printf("%c ",BT->biTree->data); } //遍历右子树 if(!stack.empty()){ BT = stack.top(); //訪问过右子树 BT->tag = \'R\'; p = BT->biTree; p = p->rchild; } }//while } //层次遍历 void LevelOrder(BiTree T){ BiTree p = T; //队列 queue<BiTree> queue; //根节点入队 queue.push(p); //队列不空循环 while(!queue.empty()){ //对头元素出队 p = queue.front(); //訪问p指向的结点 printf("%c ",p->data); //退出队列 queue.pop(); //左子树不空，将左子树入队 if(p->lchild != NULL){ queue.push(p->lchild); } //右子树不空，将右子树入队 if(p->rchild != NULL){ queue.push(p->rchild); } } } int main() { BiTree T; CreateBiTree(T); printf("先序遍历：\n"); PreOrder(T); printf("\n"); printf("先序遍历(非递归)：\n"); PreOrder2(T); printf("\n"); printf("中序遍历：\n"); InOrder(T); printf("\n"); printf("中序遍历(非递归)：\n"); InOrder2(T); printf("\n"); printf("后序遍历：\n"); PostOrder(T); printf("\n"); printf("后序遍历(非递归)：\n"); PostOrder2(T); printf("\n"); printf("层次遍历：\n"); LevelOrder(T); printf("\n"); return 0; }