二叉树的遍历（traversing binary tree）是指从根节点触发，按照某种次序依次访问二叉树中的所有结点，使得每个结点都被访问一次且仅被访问一次。

1 先（前）序遍历

若二叉树为空，则空操作返回；否则

（1）访问根节点；

（2）先序遍历左子树；

（3）先序遍历右子树。

void PreOrderTraverse(BiPTree T,void(*Visit)(BiPTree)) { /* 先序递归遍历二叉树T */   if(T)   {     Visit(T); /* 先访问根结点 */     PreOrderTraverse(T->lchild,Visit); /* 再先序遍历左子树 */     PreOrderTraverse(T->rchild,Visit); /* 最后先序遍历右子树 */   } }

2 中序遍历

若二叉树为空，则空操作返回；否则

（1）中序遍历左子树；

（2）访问根节点；

（3）中序遍历右子树。

void InOrderTraverse(BiPTree T,void(*Visit)(BiPTree)) { /* 中序递归遍历二叉树T */   if(T)   {     InOrderTraverse(T->lchild,Visit); /* 中序遍历左子树 */     Visit(T); /* 再访问根节点 */     InOrderTraverse(T->rchild,Visit); /* 最后中序遍历右子树 */   } }

3. 后序遍历

若二叉树为空，则空操作返回；否则

（1）后序遍历左子树；

（2）后序遍历右子树；

（3）访问根节点。

void PostOrderTraverse(BiPTree T,void(*Visit)(BiPTree)) { /* 后序递归遍历二叉树T */   if(T)   {     PostOrderTraverse(T->lchild,Visit); /* 后序遍历左子树 */     PostOrderTraverse(T->rchild,Visit); /* 后序遍历右子树 */     Visit(T); /* 最后访问根节点 */   } }

4. 层序遍历

若二叉树为空，则空操作返回；否则

从树的第一层，从上而下逐层遍历，在每一层中，按照从左到右的顺序逐个访问结点。

二叉树的层序遍历也就是二叉树的广度优先遍历。

算法思想：

1初始化一个队列，并把根结点入列队；

2当队列为非空时，循环执行步骤3到步骤5，否则执行步骤6；

3出队列取得一个结点，访问该结点；

4若该结点的左子树为非空，则将该结点的左子树入队列；

5若该结点的右子树为非空，则将该结点的右子树入队列；

6结束。

void LevelOrderTraverse(BiPTree T,void(*Visit)(BiPTree)) { /* 层序遍历二叉树T(利用队列) */   LinkQueue q;   QElemType a;   if(T)   {     InitQueue(&q);     EnQueue(&q,T);     while(!QueueEmpty(q))     {       DeQueue(&q,&a);       Visit(a);       if(a->lchild!=NULL)         EnQueue(&q,a->lchild);       if(a->rchild!=NULL)         EnQueue(&q,a->rchild);     }   } }

---

Reference:

[1] 《大话数据结构》

[2] 《数据结构 严蔚敏》

[3] wikipedia(二叉树)：http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%A0%91

[4] wikipedia(广度优先搜索)：

http://zh.wikipedia.org/wiki/%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2

[5] 博客园()