写在前面：博主是一位普普通通的19届双非软工在读生，平时最大的爱好就是听听歌，逛逛B站。博主很喜欢的一句话花开堪折直须折，莫待无花空折枝：博主的理解是头一次为人，就应该做自己想做的事，做自己不后悔的事，做自己以后不会留有遗憾的事，做自己觉得有意义的事，不浪费这大好的青春年华。博主写博客目的是记录所学到的知识并方便自己复习，在记录知识的同时获得部分浏览量，得到更多人的认可，满足小小的成就感，同时在写博客的途中结交更多志同道合的朋友，让自己在技术的路上并不孤单。

目录:
1.二叉树的先序遍历
        先序遍历思想
        先序遍历递归实现
        先序遍历非递归实现
2.二叉树的中序遍历
        中序遍历思想
        中序递归实现
        中序非递归实现
3.二叉树的后序遍历
        后序遍历思想
        中序递归实现
        中序非递归实现
4.二叉树的层序遍历
        代码实现

博客中的二叉树存储方式如下

typedef struct BiTNode{TElemType data;//数据域struct BiTNode *lchild,*rchild;//左右孩子指针 }BiTNode,*BiTree;

1.二叉树的先序遍历

1.1二叉树先序遍历的实现思想是：

访问根节点；

访问当前节点的左子树；

若当前节点无左子树，则访问当前节点的右子树；

上图先序遍历结果为：1 2 4 5 3 6 7

1.2先序遍历递归实现

void PreOrderTraverse(BiTree T){if (T) {printf("%d ",T->data);PreOrderTraverse(T->lchild);//访问该结点的左孩子PreOrderTraverse(T->rchild);//访问该结点的右孩子}//如果结点为空，返回上一层return; }

1.3先序遍历非递归实现

而递归的底层实现依靠的是栈存储结构，因此，二叉树的先序遍历既可以直接采用递归思想实现，也可以使用栈的存储结构模拟递归的思想实现

//先序遍历非递归算法 int top=-1;//top变量时刻表示栈顶元素所在位置 //前序遍历使用的进栈函数 void push(BiTNode** a,BiTNode* elem){a[++top]=elem; } //弹栈函数 void pop( ){if (top==-1) {return ;}top--; } //模拟操作结点元素的函数，输出结点本身的数值 void displayElem(BiTNode* elem){printf("%d ",elem->data); } //拿到栈顶元素 BiTNode* getTop(BiTNode**a){return a[top]; } void PreOrderTraverse(BiTree Tree){BiTNode* a[20];//定义一个顺序栈BiTNode * p;//临时指针push(a, Tree);//根结点进栈while (top!=-1) {p=getTop(a);//取栈顶元素pop();//弹栈while (p) {displayElem(p);//调用结点的操作函数//如果该结点有右孩子，右孩子进栈if (p->rchild) {push(a,p->rchild);}p=p->lchild;//一直指向根结点最后一个左孩子}} }

2.二叉树的中序遍历

2.1二叉树中序遍历思想

访问当前节点的左子树；

访问根节点；

访问当前节点的右子树

上图中遍历结果：4 2 5 1 6 3 7

2.2中序遍历递归实现

//中序遍历 void INOrderTraverse(BiTree T){if (T) {INOrderTraverse(T->lchild);//遍历左孩子printf("%d ",T->data);INOrderTraverse(T->rchild);//遍历右孩子}//如果结点为空，返回上一层return; }

2.3中序遍历非递归实现

而递归的底层实现依靠的是栈存储结构，因此，二叉树的先序遍历既可以直接采用递归思想实现，也可以使用栈的存储结构模拟递归的思想实现。
中序遍历的 非递归方式实现思想 是：从根结点开始，遍历左孩子同时压栈，当遍历结束，说明当前遍历的结点没有左孩子，从栈中取出来调用操作函数，然后访问该结点的右孩子，继续以上重复性的操作。除此之外， 还有另一种实现思想：中序遍历过程中，只需将每个结点的左子树压栈即可，右子树不需要压栈。当结点的左子树遍历完成后，只需要以栈顶结点的右孩子为根结点，继续循环遍历即可。

第一种非递归思路：

int top=-1;//top变量时刻表示栈顶元素所在位置 //前序和中序遍历使用的进栈函数 void push(BiTNode** a,BiTNode* elem){a[++top]=elem; } //弹栈函数 void pop( ){if (top==-1) {return ;}top--; } //模拟操作结点元素的函数，输出结点本身的数值 void displayElem(BiTNode* elem){printf("%d ",elem->data); } //拿到栈顶元素 BiTNode* getTop(BiTNode**a){return a[top]; } //中序遍历非递归算法 void InOrderTraverse1(BiTree Tree){BiTNode* a[20];//定义一个顺序栈BiTNode * p;//临时指针push(a, Tree);//根结点进栈while (top!=-1) {//top!=-1说明栈内不为空，程序继续运行while ((p=getTop(a)) &&p){//取栈顶元素，且不能为NULLpush(a, p->lchild);//将该结点的左孩子进栈，如果没有左孩子，NULL进栈}pop();//跳出循环，栈顶元素肯定为NULL，将NULL弹栈if (top!=-1) {p=getTop(a);//取栈顶元素pop();//栈顶元素弹栈displayElem(p);push(a, p->rchild);//将p指向的结点的右孩子进栈}} }

第二种非递归思路:

//中序遍历实现的另一种方法 void InOrderTraverse2(BiTree Tree){BiTNode* a[20];//定义一个顺序栈BiTNode * p;//临时指针p=Tree;//当p为NULL或者栈为空时，表明树遍历完成while (p || top!=-1) {//如果p不为NULL，将其压栈并遍历其左子树if (p) {push(a, p);p=p->lchild;}//如果p==NULL，表明左子树遍历完成，需要遍历上一层结点的右子树else{p=getTop(a);pop();displayElem(p);p=p->rchild;}} }

3.二叉树的后序遍历

3.1后序遍历思想

从根节点出发，依次遍历各节点的左右子树，直到当前节点左右子树遍历完成后，才访问该节点元素。

上图后序遍历的结果为：4 5 2 6 7 3 1

3.2后序遍历的递归实现

void PostOrderTraverse(BiTree T){if (T) {PostOrderTraverse(T->lchild);//遍历左孩子PostOrderTraverse(T->rchild);//遍历右孩子printf("%d ",T->data);}//如果结点为空，返回上一层return; }

3.2后序遍历的非递归实现

后序遍历是在遍历完当前结点的左右孩子之后，才调用操作函数，所以需要在操作结点进栈时，为每个结点配备一个标志位。当遍历该结点的左孩子时，设置当前结点的标志位为 0，进栈；当要遍历该结点的右孩子时，设置当前结点的标志位为 1，进栈。
这样，当遍历完成，该结点弹栈时，查看该结点的标志位的值：如果是 0，表示该结点的右孩子还没有遍历；反之如果是 1，说明该结点的左右孩子都遍历完成，可以调用操作函数。

int top=-1;//top变量时刻表示栈顶元素所在位置 //弹栈函数 void pop( ){if (top==-1) {return ;}top--; } //模拟操作结点元素的函数，输出结点本身的数值 void displayElem(BiTNode* elem){printf("%d ",elem->data); } //后序遍历非递归算法 typedef struct SNode{BiTree p;int tag; }SNode; //后序遍历使用的进栈函数 void postpush(SNode *a,SNode sdata){a[++top]=sdata; } //后序遍历函数 void PostOrderTraverse(BiTree Tree){SNode a[20];//定义一个顺序栈BiTNode * p;//临时指针int tag;SNode sdata;p=Tree;while (p||top!=-1) {while (p) {//为该结点入栈做准备sdata.p=p;sdata.tag=0;//由于遍历是左孩子，设置标志位为0postpush(a, sdata);//压栈p=p->lchild;//以该结点为根结点，遍历左孩子}sdata=a[top];//取栈顶元素pop();//栈顶元素弹栈p=sdata.p;tag=sdata.tag;//如果tag==0，说明该结点还没有遍历它的右孩子if (tag==0) {sdata.p=p;sdata.tag=1;postpush(a, sdata);//更改该结点的标志位，重新压栈p=p->rchild;//以该结点的右孩子为根结点，重复循环}//如果取出来的栈顶元素的tag==1，说明此结点左右子树都遍历完了，可以调用操作函数了else{displayElem(p);p=NULL;}} }

4.二叉树的层序遍历

照二叉树中的层次从左到右依次遍历每层中的结点。具体的实现思路是：通过使用队列的数据结构，从树的根结点开始，依次将其左孩子和右孩子入队。而后每次队列中一个结点出队，都将其左孩子和右孩子入队，直到树中所有结点都出队，出队结点的先后顺序就是层次遍历的最终结果。

上图层序遍历结果：1 2 3 4 5 6 7

#include <stdio.h> #define TElemType int //初始化队头和队尾指针开始时都为0 int front=0,rear=0; typedef struct BiTNode{TElemType data;//数据域struct BiTNode *lchild,*rchild;//左右孩子指针 }BiTNode,*BiTree; void CreateBiTree(BiTree *T){*T=(BiTNode*)malloc(sizeof(BiTNode));(*T)->data=1;(*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));(*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));(*T)->lchild->data=2;(*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));(*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));(*T)->lchild->rchild->data=5;(*T)->lchild->rchild->lchild=NULL;(*T)->lchild->rchild->rchild=NULL;(*T)->rchild->data=3;(*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));(*T)->rchild->lchild->data=6;(*T)->rchild->lchild->lchild=NULL;(*T)->rchild->lchild->rchild=NULL;(*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));(*T)->rchild->rchild->data=7;(*T)->rchild->rchild->lchild=NULL;(*T)->rchild->rchild->rchild=NULL;(*T)->lchild->lchild->data=4;(*T)->lchild->lchild->lchild=NULL;(*T)->lchild->lchild->rchild=NULL; } //入队函数 void EnQueue(BiTree *a,BiTree node){a[rear++]=node; } //出队函数 BiTNode* DeQueue(BiTNode** a){return a[front++]; } //输出函数 void displayNode(BiTree node){printf("%d ",node->data); } int main() {BiTree tree;//初始化二叉树CreateBiTree(&tree);BiTNode * p;//采用顺序队列，初始化创建队列数组BiTree a[20];//根结点入队EnQueue(a, tree);//当队头和队尾相等时，表示队列为空while(front<rear) {//队头结点出队p=DeQueue(a);displayNode(p);//将队头结点的左右孩子依次入队if (p->lchild!=NULL) {EnQueue(a, p->lchild);}if (p->rchild!=NULL) {EnQueue(a, p->rchild);}}return 0; }

本篇博客转载C语言中文网

总结

以上是生活随笔为你收集整理的二叉树的四种遍历方式(递归和非递归双重实现)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。