寫在前面：博主是一位普普通通的19屆雙非軟工在讀生，平時(shí)最大的愛好就是聽聽歌，逛逛B站。博主很喜歡的一句話花開堪折直須折，莫待無花空折枝：博主的理解是頭一次為人，就應(yīng)該做自己想做的事，做自己不后悔的事，做自己以后不會(huì)留有遺憾的事，做自己覺得有意義的事，不浪費(fèi)這大好的青春年華。博主寫博客目的是記錄所學(xué)到的知識(shí)并方便自己復(fù)習(xí)，在記錄知識(shí)的同時(shí)獲得部分瀏覽量，得到更多人的認(rèn)可，滿足小小的成就感，同時(shí)在寫博客的途中結(jié)交更多志同道合的朋友，讓自己在技術(shù)的路上并不孤單。

目錄:
1.二叉樹的先序遍歷
???? ?? 先序遍歷思想
???? ?? 先序遍歷遞歸實(shí)現(xiàn)
???? ?? 先序遍歷非遞歸實(shí)現(xiàn)
2.二叉樹的中序遍歷
???? ?? 中序遍歷思想
???? ?? 中序遞歸實(shí)現(xiàn)
???? ?? 中序非遞歸實(shí)現(xiàn)
3.二叉樹的后序遍歷
???? ?? 后序遍歷思想
???? ?? 中序遞歸實(shí)現(xiàn)
???? ?? 中序非遞歸實(shí)現(xiàn)
4.二叉樹的層序遍歷
???? ?? 代碼實(shí)現(xiàn)

博客中的二叉樹存儲(chǔ)方式如下

typedef struct BiTNode{TElemType data;//數(shù)據(jù)域struct BiTNode *lchild,*rchild;//左右孩子指針 }BiTNode,*BiTree;

1.二叉樹的先序遍歷

1.1二叉樹先序遍歷的實(shí)現(xiàn)思想是：

訪問根節(jié)點(diǎn)；

訪問當(dāng)前節(jié)點(diǎn)的左子樹；

若當(dāng)前節(jié)點(diǎn)無左子樹，則訪問當(dāng)前節(jié)點(diǎn)的右子樹；

上圖先序遍歷結(jié)果為：1 2 4 5 3 6 7

1.2先序遍歷遞歸實(shí)現(xiàn)

void PreOrderTraverse(BiTree T){if (T) {printf("%d ",T->data);PreOrderTraverse(T->lchild);//訪問該結(jié)點(diǎn)的左孩子PreOrderTraverse(T->rchild);//訪問該結(jié)點(diǎn)的右孩子}//如果結(jié)點(diǎn)為空，返回上一層return; }

1.3先序遍歷非遞歸實(shí)現(xiàn)

而遞歸的底層實(shí)現(xiàn)依靠的是棧存儲(chǔ)結(jié)構(gòu)，因此，二叉樹的先序遍歷既可以直接采用遞歸思想實(shí)現(xiàn)，也可以使用棧的存儲(chǔ)結(jié)構(gòu)模擬遞歸的思想實(shí)現(xiàn)

//先序遍歷非遞歸算法 int top=-1;//top變量時(shí)刻表示棧頂元素所在位置 //前序遍歷使用的進(jìn)棧函數(shù) void push(BiTNode** a,BiTNode* elem){a[++top]=elem; } //彈棧函數(shù) void pop( ){if (top==-1) {return ;}top--; } //模擬操作結(jié)點(diǎn)元素的函數(shù)，輸出結(jié)點(diǎn)本身的數(shù)值 void displayElem(BiTNode* elem){printf("%d ",elem->data); } //拿到棧頂元素 BiTNode* getTop(BiTNode**a){return a[top]; } void PreOrderTraverse(BiTree Tree){BiTNode* a[20];//定義一個(gè)順序棧BiTNode * p;//臨時(shí)指針push(a, Tree);//根結(jié)點(diǎn)進(jìn)棧while (top!=-1) {p=getTop(a);//取棧頂元素pop();//彈棧while (p) {displayElem(p);//調(diào)用結(jié)點(diǎn)的操作函數(shù)//如果該結(jié)點(diǎn)有右孩子，右孩子進(jìn)棧if (p->rchild) {push(a,p->rchild);}p=p->lchild;//一直指向根結(jié)點(diǎn)最后一個(gè)左孩子}} }

2.二叉樹的中序遍歷

2.1二叉樹中序遍歷思想

訪問當(dāng)前節(jié)點(diǎn)的左子樹；

訪問根節(jié)點(diǎn)；

訪問當(dāng)前節(jié)點(diǎn)的右子樹

上圖中遍歷結(jié)果：4 2 5 1 6 3 7

2.2中序遍歷遞歸實(shí)現(xiàn)

//中序遍歷 void INOrderTraverse(BiTree T){if (T) {INOrderTraverse(T->lchild);//遍歷左孩子printf("%d ",T->data);INOrderTraverse(T->rchild);//遍歷右孩子}//如果結(jié)點(diǎn)為空，返回上一層return; }

2.3中序遍歷非遞歸實(shí)現(xiàn)

而遞歸的底層實(shí)現(xiàn)依靠的是棧存儲(chǔ)結(jié)構(gòu)，因此，二叉樹的先序遍歷既可以直接采用遞歸思想實(shí)現(xiàn)，也可以使用棧的存儲(chǔ)結(jié)構(gòu)模擬遞歸的思想實(shí)現(xiàn)。
中序遍歷的 非遞歸方式實(shí)現(xiàn)思想 是：從根結(jié)點(diǎn)開始，遍歷左孩子同時(shí)壓棧，當(dāng)遍歷結(jié)束，說明當(dāng)前遍歷的結(jié)點(diǎn)沒有左孩子，從棧中取出來調(diào)用操作函數(shù)，然后訪問該結(jié)點(diǎn)的右孩子，繼續(xù)以上重復(fù)性的操作。除此之外， 還有另一種實(shí)現(xiàn)思想：中序遍歷過程中，只需將每個(gè)結(jié)點(diǎn)的左子樹壓棧即可，右子樹不需要壓棧。當(dāng)結(jié)點(diǎn)的左子樹遍歷完成后，只需要以棧頂結(jié)點(diǎn)的右孩子為根結(jié)點(diǎn)，繼續(xù)循環(huán)遍歷即可。

第一種非遞歸思路：

int top=-1;//top變量時(shí)刻表示棧頂元素所在位置 //前序和中序遍歷使用的進(jìn)棧函數(shù) void push(BiTNode** a,BiTNode* elem){a[++top]=elem; } //彈棧函數(shù) void pop( ){if (top==-1) {return ;}top--; } //模擬操作結(jié)點(diǎn)元素的函數(shù)，輸出結(jié)點(diǎn)本身的數(shù)值 void displayElem(BiTNode* elem){printf("%d ",elem->data); } //拿到棧頂元素 BiTNode* getTop(BiTNode**a){return a[top]; } //中序遍歷非遞歸算法 void InOrderTraverse1(BiTree Tree){BiTNode* a[20];//定義一個(gè)順序棧BiTNode * p;//臨時(shí)指針push(a, Tree);//根結(jié)點(diǎn)進(jìn)棧while (top!=-1) {//top!=-1說明棧內(nèi)不為空，程序繼續(xù)運(yùn)行while ((p=getTop(a)) &&p){//取棧頂元素，且不能為NULLpush(a, p->lchild);//將該結(jié)點(diǎn)的左孩子進(jìn)棧，如果沒有左孩子，NULL進(jìn)棧}pop();//跳出循環(huán)，棧頂元素肯定為NULL，將NULL彈棧if (top!=-1) {p=getTop(a);//取棧頂元素pop();//棧頂元素彈棧displayElem(p);push(a, p->rchild);//將p指向的結(jié)點(diǎn)的右孩子進(jìn)棧}} }

第二種非遞歸思路:

//中序遍歷實(shí)現(xiàn)的另一種方法 void InOrderTraverse2(BiTree Tree){BiTNode* a[20];//定義一個(gè)順序棧BiTNode * p;//臨時(shí)指針p=Tree;//當(dāng)p為NULL或者棧為空時(shí)，表明樹遍歷完成while (p || top!=-1) {//如果p不為NULL，將其壓棧并遍歷其左子樹if (p) {push(a, p);p=p->lchild;}//如果p==NULL，表明左子樹遍歷完成，需要遍歷上一層結(jié)點(diǎn)的右子樹else{p=getTop(a);pop();displayElem(p);p=p->rchild;}} }

3.二叉樹的后序遍歷

3.1后序遍歷思想

從根節(jié)點(diǎn)出發(fā)，依次遍歷各節(jié)點(diǎn)的左右子樹，直到當(dāng)前節(jié)點(diǎn)左右子樹遍歷完成后，才訪問該節(jié)點(diǎn)元素。

上圖后序遍歷的結(jié)果為：4 5 2 6 7 3 1

3.2后序遍歷的遞歸實(shí)現(xiàn)

void PostOrderTraverse(BiTree T){if (T) {PostOrderTraverse(T->lchild);//遍歷左孩子PostOrderTraverse(T->rchild);//遍歷右孩子printf("%d ",T->data);}//如果結(jié)點(diǎn)為空，返回上一層return; }

3.2后序遍歷的非遞歸實(shí)現(xiàn)

后序遍歷是在遍歷完當(dāng)前結(jié)點(diǎn)的左右孩子之后，才調(diào)用操作函數(shù)，所以需要在操作結(jié)點(diǎn)進(jìn)棧時(shí)，為每個(gè)結(jié)點(diǎn)配備一個(gè)標(biāo)志位。當(dāng)遍歷該結(jié)點(diǎn)的左孩子時(shí)，設(shè)置當(dāng)前結(jié)點(diǎn)的標(biāo)志位為 0，進(jìn)棧；當(dāng)要遍歷該結(jié)點(diǎn)的右孩子時(shí)，設(shè)置當(dāng)前結(jié)點(diǎn)的標(biāo)志位為 1，進(jìn)棧。
這樣，當(dāng)遍歷完成，該結(jié)點(diǎn)彈棧時(shí)，查看該結(jié)點(diǎn)的標(biāo)志位的值：如果是 0，表示該結(jié)點(diǎn)的右孩子還沒有遍歷；反之如果是 1，說明該結(jié)點(diǎn)的左右孩子都遍歷完成，可以調(diào)用操作函數(shù)。

int top=-1;//top變量時(shí)刻表示棧頂元素所在位置 //彈棧函數(shù) void pop( ){if (top==-1) {return ;}top--; } //模擬操作結(jié)點(diǎn)元素的函數(shù)，輸出結(jié)點(diǎn)本身的數(shù)值 void displayElem(BiTNode* elem){printf("%d ",elem->data); } //后序遍歷非遞歸算法 typedef struct SNode{BiTree p;int tag; }SNode; //后序遍歷使用的進(jìn)棧函數(shù) void postpush(SNode *a,SNode sdata){a[++top]=sdata; } //后序遍歷函數(shù) void PostOrderTraverse(BiTree Tree){SNode a[20];//定義一個(gè)順序棧BiTNode * p;//臨時(shí)指針int tag;SNode sdata;p=Tree;while (p||top!=-1) {while (p) {//為該結(jié)點(diǎn)入棧做準(zhǔn)備sdata.p=p;sdata.tag=0;//由于遍歷是左孩子，設(shè)置標(biāo)志位為0postpush(a, sdata);//壓棧p=p->lchild;//以該結(jié)點(diǎn)為根結(jié)點(diǎn)，遍歷左孩子}sdata=a[top];//取棧頂元素pop();//棧頂元素彈棧p=sdata.p;tag=sdata.tag;//如果tag==0，說明該結(jié)點(diǎn)還沒有遍歷它的右孩子if (tag==0) {sdata.p=p;sdata.tag=1;postpush(a, sdata);//更改該結(jié)點(diǎn)的標(biāo)志位，重新壓棧p=p->rchild;//以該結(jié)點(diǎn)的右孩子為根結(jié)點(diǎn)，重復(fù)循環(huán)}//如果取出來的棧頂元素的tag==1，說明此結(jié)點(diǎn)左右子樹都遍歷完了，可以調(diào)用操作函數(shù)了else{displayElem(p);p=NULL;}} }

4.二叉樹的層序遍歷

照二叉樹中的層次從左到右依次遍歷每層中的結(jié)點(diǎn)。具體的實(shí)現(xiàn)思路是：通過使用隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，從樹的根結(jié)點(diǎn)開始，依次將其左孩子和右孩子入隊(duì)。而后每次隊(duì)列中一個(gè)結(jié)點(diǎn)出隊(duì)，都將其左孩子和右孩子入隊(duì)，直到樹中所有結(jié)點(diǎn)都出隊(duì)，出隊(duì)結(jié)點(diǎn)的先后順序就是層次遍歷的最終結(jié)果。

上圖層序遍歷結(jié)果：1 2 3 4 5 6 7

#include <stdio.h> #define TElemType int //初始化隊(duì)頭和隊(duì)尾指針開始時(shí)都為0 int front=0,rear=0; typedef struct BiTNode{TElemType data;//數(shù)據(jù)域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; } //入隊(duì)函數(shù) void EnQueue(BiTree *a,BiTree node){a[rear++]=node; } //出隊(duì)函數(shù) BiTNode* DeQueue(BiTNode** a){return a[front++]; } //輸出函數(shù) void displayNode(BiTree node){printf("%d ",node->data); } int main() {BiTree tree;//初始化二叉樹CreateBiTree(&tree);BiTNode * p;//采用順序隊(duì)列，初始化創(chuàng)建隊(duì)列數(shù)組BiTree a[20];//根結(jié)點(diǎn)入隊(duì)EnQueue(a, tree);//當(dāng)隊(duì)頭和隊(duì)尾相等時(shí)，表示隊(duì)列為空while(front<rear) {//隊(duì)頭結(jié)點(diǎn)出隊(duì)p=DeQueue(a);displayNode(p);//將隊(duì)頭結(jié)點(diǎn)的左右孩子依次入隊(duì)if (p->lchild!=NULL) {EnQueue(a, p->lchild);}if (p->rchild!=NULL) {EnQueue(a, p->rchild);}}return 0; }

本篇博客轉(zhuǎn)載C語言中文網(wǎng)

總結(jié)

以上是生活随笔為你收集整理的二叉树的四种遍历方式(递归和非递归双重实现)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。